문제주어진 문제는 N×M 크기의 격자에서 빙하(1)와 물(0)의 상태를 표현하는 배열을 통해, 빙하가 전부 녹는 데 걸리는 시간과 마지막으로 녹은 빙하의 크기를 계산하는 것이다. 빙하는 매 초마다 상하좌우로 인접한 물과 접촉하여 동시에 녹는데, 빙하로 둘러싸여 있는 물의 경우에는 붙어 있는 빙하를 녹이지 못한다. 최종적으로 빙하가 모두 녹을 때까지의 시간과 마지막으로 녹은 빙하의 크기를 출력해야 한다. 풀이바깥쪽에 있는 물이 빙하와 접촉하면 해당 빙하가 녹지만, 안쪽에 있는 물은 빙하에 영향을 미치지 않는다는 점이 중요하다.이를 해결하기 위해 BFS 알고리즘을 사용하여 바깥쪽 물을 중심으로 탐색하면서 빙하를 만나면 녹이도록 한다.이 과정에서 빙하가 녹은 자리는 물의 영역으로 간주될 수 있기 때문에, 기존..
오늘은 두 번째 학습진단을 진행하였다. 하지만 지난번 보다 일찍 문제를 틀려서 746점으로 내려갔는데, HashMap을 사용하는 문제였다. 문제 풀이 방향은 잘 잡은 것 같은데, 시간 초과가 나타나 결국 틀리고 말았다. 문제를 틀린 김에 HashMap 자료구조에 대한 개념을 다시 잡고 가야겠다. HashMap Python에서는 HashMap 자료구조가 dict라는 class로 구현되어 있다. HashMap은 key와 value 값으로 짝을 이루어 저장되는 구조이다. 따라서 key 를 통해 value를 빠르게 꺼내 쓸 수 있다. 순서 없이 저장되며, 삽입, 삭제, 탐색의 시간 복잡도는 O(1)이다. (1) Dictionary 선언 python에서는 dict() 함수를 호출하거나 {} 괄호를 통해 딕셔너리를..
오늘 새로운 학습진단을 시도했다. 매우 쉬운 문제부터 풀어 나갔는데 쉬운 문제를 빠르게 풀 수 있다는 것에서도 나름 성취감을 느낄 수 있었다. 9번째 문제였나 Parametric Search 문제에서 막힌 것을 확인할 수 있었다. 예전에도 이분탐색을 활용한 문제에서 많이 막혔어서 이분탐색을 좀 연습했었는데, 오늘에서야 그런 문제 유형이 Parametric Search에 해당되는 것을 알게 되었다. 이번 기회에 Parametric Search 개념에 대해 확실히 잡고 가야겠다. 최대 최소 값을 찾는 문제는 아닌지 먼저 판단하고, 주어진 조건에 맞는 값인지 아닌지 판단하는 함수를 짠다. 이후는 이분탐색과 마찬가지로 함수에 통과하는지의 여부에 따라 중간값 이후 값들을 조사할 것인지 이전 값들을 조사할 것인지 ..