문제NxM 크기의 격자 미로 안에서 출발지 (x, y)에서 도착지 (r, c)로 가는 경로를 알파벳으로 표기했을 때, 사전 순으로 가장 빠른 경로를 찾는 문제이다.미로를 탈출하기 위해서 이동하는 거리는 k여야 한다. ( 이동거리 = 이동 횟수 = 경로 문자열 길이 )경로는 u(상), d(하), l(좌), r(우) 로 표현 가능하며 사전 순으로 가장 빠른 경로를 선택한다. 풀이깊이 우선 탐색(DFS) 알고리즘을 활용하여 경로를 찾을 수 있다.DFS 알고리즘은 LIFO(Last In First Out)의 특징을 갖고 있기 때문에 사전순으로 앞서는 알파벳을 뒤에서 탐색한다면 항상 사전순으로 빠른 문자열을 먼저 탐색할 수 있다.탐색 방향을 u, r, l, d 순으로 설정한다.한 노드에서 상하좌우로 이동할 때 u..
[코드트리 챌린지] 일곱번째 학습진단
오늘도 +1 -1 유형에서 틀렸다. 이 유형에서 틀린 것은 이번이 두번째인데, 조건이 조금 복잡하게 들어가면 이렇게 헤매는 것 같다. 같은 유형을 다양한 형태로 만나는 것도 필요한 과정이란 생각이 든다. 오늘 고른 문제는 코드트리의 학습하기 과정에서 알고리즘 기본에서 고른 문제이다. 유사 문제 풀이 https://www.codetree.ai/missions/8/problems/computer-hours?&utm_source=clipboard&utm_medium=text 문제 n명의 사람들의 컴퓨터 사용 시작시간과 종료시간이 주어진다.선착순으로 맨 앞 번호부터 채워 앉는다고 했을 때, (자리가 나면 또 맨 앞부터 다시 채움)n명의 사람들이 차지했던 컴퓨터 번호를 출력하는 문제이다. 코드 import hea..
[코드트리 챌린지] 여섯번째 학습진단
이번엔 최고점을 찍었는데 또 Parametric Search 문제를 만나서 틀려버렸다. 이번까지 세 번째 장렬한 패배를 했는데 처음엔 정말 접근조차 못했는데 이제는 '아 Parametric Search 접근인 것 같은데?'라는 생각이 들긴 하는 것 같다. 그래도 아직 해를 찾는 방법을 찾는데 취약하고, 매번 문제가 색달라서 헷갈리는 것 같다. 아래 문제는 코드트리에서 제공해주는 문제은행에서 가져왔다. 유사 문제 풀이 코드트리 문제 https://www.codetree.ai/training-field/search/problems/painting-the-grid?&utm_source=clipboard&utm_medium=text 문제 0부터 1,000,000 의 숫자로 이루어진 n*n 격자가 주어지고, 임의..
[코드트리 챌린지] 다섯번째 학습진단
오늘은 학습진단에서 +1 -1 Technique 문제를 만났다. 여러 길이의 선분이 주어졌을 때, 겹치는 선분들의 점수의 합이 k 점을 넘는 구간의 총 길이를 구하는 문제였다. 이전에 이번 문제와 유사한 겹치는 선분의 개수를 구하는 문제를 접했을 때 priority queue를 활용했던 것을 기억해서 heapq를 사용하여 접근했다. 하지만 k 점을 넘는 구간의 총 길이를 어떻게 구해야 하는지 고민하다가 결국 시간 초과로 틀렸다. 덕분에 코드트리에서 "진단에서 부족했던 유형"으로 +1 -1 Technique 개념을 소개한 내용을 보았는데, 겹치는 선분의 개수 문제에 대한 새롭고 심플한 풀이 방법을 만날 수 있어서 굉장히 흥미로웠다. 상황에 맞게 +1 과 -1을 활용하여 문제를 해결하는 방법으로 구간의 시작..
[코드트리 챌린지] 네번째 학습진단
오늘은 학습진단 중에 다른 일이 생겨서 시간이 부족했다. 그래서 6번째 문제를 다 풀지 못했다. 특히 문제만 보고 DFS로 풀면 되겠네 생각했다가 시간 초과로 틀렸었다. 아마 구현했던 방법의 시간 복잡도는 순열의 개수를 구하는 문제와 같은 O((2n)!/(n!*n!)) 일 것으로 보인다. DP로 다시 풀려고 하다가 중단하게 되었는데, DP로 풀면 O(n^2) 이므로 더 빠르다 처음부터 DP로 접근해야겠다는 생각이 들도록 머릿속에 넣으면 좋을 것 같다. 유사 문제 풀이 https://www.codetree.ai/landing/level-test/6630/result/4?&utm_source=clipboard&utm_medium=text 문제 오른쪽 혹은 아래쪽으로만 이동하여 (1,1)에서 (n,n)로 가는..
이번엔 시간 문제로 836점에 머물렀다. 그래도 바로 전 두번째 학습진단에서 틀렸던 문제와 동일한 문제를 만났었는데, 다행이 맞춰서 넘어갈 수 있었다. 틀린 문제는 Parametric Search 문제였는데 기준 세우는 연습이 필요할 것 같다. 이분탐색을 활용하면 좋을 것 같다는 생각이 들지만 막상 안의 메서드를 세우는 방법이 어렵다고 느껴진다. 오늘은 Parametric Search 한 문제를 풀어보며 익숙해지자. https://www.codetree.ai/landing/level-test/6441/result/4?&utm_source=clipboard&utm_medium=text 문제 이차원 배열 A에 각각의 행과 열을 곱한 값이 입력되어 있는데 (인덱스는 1부터), 오름차순으로 정렬하였을 때, k번..
틀렸던 문제는 두 수의 합과 유사하지만 조금 더 복잡한 문제였다. 먼저 기초가 되는 두 수의 합 문제를 풀어보면서 응용할 수 있도록 공부해서 다음엔 풀 수 있도록 연습하자. 문제 두 수의 합 문제는 다음과 같다. n개의 정수로 이루어진 수열이 입력되었을 때, 서로 다른 위치의 두 수를 뽑아 더한 값이 k가 되는 경우의 수를 구하는 문제이다. 풀이 모든 두 수 조합을 비교하는 것은 매우 시간이 오래 걸린다. 딕셔너리에 중복 값을 넣어주고, 중복 값을 제외한 뒤 비교하는 것도 마찬가지로 시간이 오래 걸린다. 5달 전에도 같은 문제를 풀었는데 습관처럼 위와 같은 방법을 사용했었다. 하지만 앞의 숫자부터 k값을 만들 수 있는 짝꿍이 있는지 비교하면서 경우의 수를 세어주는 것이 가장 빠른 방법이다. 이번엔 머릿속..