일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
- prototype 프로퍼티
- 시간
- 한글이 두 번 입력됨
- float: right
- dp
- javascript
- Tanstack Query
- 비동기
- 낙관적 업데이트
- 백준 9610번 파이썬 문제 풀이
- 파이썬
- 유클리드 호제법
- 알고리즘
- 최소공배수
- 9610
- 함수 객체의 프로퍼티
- 동적 계획법
- 백준
- css
- 자바스크립트
- python
- 한글 입력 시 이벤트 두 번 발생
- 백트래킹
- 프로그래밍
- C++
- 동기
- backtracking
- 2522
- 메타버스
- __proto__ 접근자 프로퍼티
- Today
- Total
목록알고리즘 (6)
염딩코
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/2LFY0/btsvqAX56pN/dszxKze7onVIwE3flkq2PK/img.png)
Longest Common Substring 과 Longest Common Subsequence 란? LCS는 주로 최장 공통 부분 수열(Longest Common Subsequence)을 말합니다만, 최장 공통 문자열(Longest Common Substring)을 말하기도 합니다. 문자열 ABCDEF와 GBCDFE를 이용하여 차이점을 예시로 들어보면 해당 예시에서 최장 공통 부분수열(Longest Common Subsequence)은 BCDF, BCDE가 될 수 있습니다. 부분수열이기 때문에 문자 사이를 건너뛰어 공통되면서 가장 긴 부분 문자열을 찾으면 됩니다. 최장 공통 문자열(Longest Common Substring)은 BCD입니다. 부분문자열이 아니기 때문에 한번에 이어져있는 문자열만 가능합..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/dvT1Vu/btstX1Khvye/I73h1Hxcjg1NetTNBqKavk/img.png)
풀이 function solution(numbers) { const arr = ['zero', 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine']; for (let i = 0; i < arr.length; i++) { numbers = numbers.split(arr[i]).join(i); } return Number(numbers); } arr로 각 숫자를 구분하기 위해서 나열하는 것은 필수의 과정인 것 같다. 다만, 이것을 객체로 할 것인지 혹은 배열로 할 것인지에 따라 풀이 과정이 달라진다. 배열로 푼다면 replaceAll 메서드를 활용할 수도 있다. function solution(numbers) { const word..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/cxlrg5/btr6TmXE0H7/zET2dS8LyKs9dujaeXawe0/img.jpg)
Merge sort Implementation Divide 하나의 배열을 반으로 나눠 2개의 배열로 만든다. Conquer Subarray가 충분히 작아졌다면, 정렬시킨다. Subarray가 충분히 작지 않다면, Recursion Merge 정렬된 subarray를 합쳐서 하나의 배열로 만든다. Pseudo code // 위의 그림과 함께 보면 이해하기 쉽다. public static void mergeSort(int n, keytype[] S) { if(n > 1) { // 1개일 때는 할 것이 없음. const int h = floor(n/2), m = n-h; // 반으로 나눔. keytype[] U = new keytype[1...h]; keytype[] V = new keytype[1...m];..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/xYIyF/btrYycokeBQ/nIV5LfsMBnYYk9ud9mm3PK/img.gif)
모든 경우의 수를 전부 고려하는 알고리즘. 백트래킹(backtracking)이란? : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다. 상태공간을 트리로 나타낼 수 있을 때 적합한 방식입니다. 일종의 트리 탐색 알고리즘이라고 봐도 됩니다. 방식에 따라서 * 깊이우선탐색(Depth First Search, DFS) * 너비우선탐색(Breadth First Search, BFS) * 최선 우선 탐색(Best First Search/Heuristic Search) (그냥 뇌없이 짤 수 있다는 것이 장점입니다.) DFS와 Backtracking * DFS(깊이 우선 탐색) : DFS는 가능한 모든 경로(후보)를 탐색합니다. 따..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/cv522w/btrWbtfrjSU/xRFMjnE4uB7KRMyNki3hXk/img.gif)
구현이란? 구현이란 말 그대로 문제를 파악하고 소스코드로 바꾸는 과정입니다. 사실 어떤 문제를 풀든 생각한 것을 소스코드로 바꾸는 과정은 필수입니다. 그렇기 때문에 구현 문제 유형은 모든 범위 코딩 테스트 유형을 포함하고 있는 개념입니다. [문제] 다음과 같이 문자열을 선언했다고 하고 아래의 문제를 풀어보겠습니다. Q1. 앞에서부터 3개의 문자열을 출력하라. Q2. 해당 문자열을 거꾸로 해서 출력하라. Q3. 해당 문자열 끝에 "Yeom"이란 문자열을 추가하라. 라고 하면 다음과 같이 코드를 구현할 것입니다. [풀이 1] 위의 코드에서는 크게 어려운 점이 없습니다. [풀이 2] 풀이 2와 풀이 1의 차이는 함수의 사용 여부입니다. 범위가 크거나 복잡한 문제였다면 풀이 2의 소스코드처럼 함수를 사용하는 것..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bfkHm7/btrV2PhRTTT/hkvKTKEtnLTSys56OvoNy0/img.gif)
누적합이란 누적합이란 요소들의 누적된 합의 의미로 어떠한 배열을 기반으로 앞에서 부터 요소들의 누적된 합을 저장해 새로이 배열을 만들어서 이를 활용하는 것을 말합니다. 항상 문제를 풀 때는 최대, 최소 범위를 확인하고 생각을 해봅시다. "구간 쿼리" 하면 2가지가 생각나야 합니다. 팬윅트리(동적 배열) pSum(정적 배열) [핵심] 처음과 끝의 합은 변하지 않습니다.(정적 배열이기 때문입니다.) 매번 더할 필요없이 각 구간에 맞게 뺄셈만 해주면 됩니다. [코드 1] 이 코드는 위의 핵심을 완전히 파악하지 못하고 작성한 코드입니다. 처음에 문제를 풀 때, 입력 받는 인덱스를 임의로 tempStart/tempEnd에 저장하고 다음에 입력받는 인덱스와 비교했을 때 경우를 나누어서 진행했습니다. 예를 들어, '..