문제주어진 문제는 N×M 크기의 격자에서 빙하(1)와 물(0)의 상태를 표현하는 배열을 통해, 빙하가 전부 녹는 데 걸리는 시간과 마지막으로 녹은 빙하의 크기를 계산하는 것이다. 빙하는 매 초마다 상하좌우로 인접한 물과 접촉하여 동시에 녹는데, 빙하로 둘러싸여 있는 물의 경우에는 붙어 있는 빙하를 녹이지 못한다. 최종적으로 빙하가 모두 녹을 때까지의 시간과 마지막으로 녹은 빙하의 크기를 출력해야 한다. 풀이바깥쪽에 있는 물이 빙하와 접촉하면 해당 빙하가 녹지만, 안쪽에 있는 물은 빙하에 영향을 미치지 않는다는 점이 중요하다.이를 해결하기 위해 BFS 알고리즘을 사용하여 바깥쪽 물을 중심으로 탐색하면서 빙하를 만나면 녹이도록 한다.이 과정에서 빙하가 녹은 자리는 물의 영역으로 간주될 수 있기 때문에, 기존..
[코드트리 챌린지] 일곱번째 학습진단
오늘도 +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값을 만들 수 있는 짝꿍이 있는지 비교하면서 경우의 수를 세어주는 것이 가장 빠른 방법이다. 이번엔 머릿속..