알고리즘

LeetCode에 Grind75라는 것이 있다. 1월 이후, 거의 매일 백준을 풀고 코딩테스트를 치르면서, 코테의 벽을 넘기가 힘들다는 것을 느끼게 되었고 어떻게 해야할지 고민을 하다가 LeetCode의 Grind75를 알게 되었다. 사실 Grind 75는 8주를 기준으로 잡았을때 75문제이고 26주까지 늘리게 되면 169문제까지 늘어나게 된다. 우선 내 생각에 LeetCode의 장점은 아래와 같다. 어떤 테스트 케이스에서 오답이 되었는지 알려준다. 에디토리얼이 있어서 어떤 의도로 문제를 냈는지 알수 있다. 사람들이 자신의 솔루션을 올리고 이를 투표하여 좋은 코드를 보기 좋다. 알고리즘 PS 뿐만 아니라 다른 컨텐츠도 있다. 물론 위의 모든 컨텐츠를 이용하기 위해서는 프리미엄이 필요하고 리트 코드를 사용..

분류 구현, (우선순위 큐) 혼자 힘으로 해결 했는가? O 느낀 점 상어....만 보면 머리가 아파진다. 이 문제를 이번에 처음 푸려고 시도한 것은 아니다. 약 6개월 전에 해결을 해보고자 문제를 읽었지만 너무 머리가 복잡해져서 포기했다. 다시 도전하니 한번에 해결을 해서 기분이 좋았다. 이 문제에서 조건이 많아서 귀찮다. 어렵지는 않지만 귀찮고 과연 이게 될까? 라는 생각에 풀이를 시작하기가 꺼려진다. 이 문제에서 제일 짜증났던 부분은 아래와 같다. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그..

분류 완전 탐색 혼자 힘으로 해결 했는가? △ (엄청난 삽질을 해서 애매함) 느낀 점 이번 문제를 직접 모두 백트래킹으로 구현을 하려고 하니 너무 실수가 잦았다. 우선 각 칼럼마다 가능한 조합을 만들고 (백트래킹 + for문) 각 조합마다 다시 겹치는지 검사를 위해 다시한번 완전탐색을 사용하고 (2중 for) 만들어진 조합이 최소성을 충족하는지 따지기 위해 다시 백트래킹을 사용했다. 이렇게 구현을 하니 너무 힘이들었다. 이후 다른 분은 어떻게 해결했는지 참고했고 itertools와 set을 활용하는 인사이트를 얻을 수 있었다. 우선 각 칼럼마다 가능한 조합 자체를 itertools로 만들고 (물론 순수 백트래킹으로 만드는 방법도 알아야 한다고 생각한다.) 이후 하나의 칼럼의 조합이 유일성을 만족하는지 체..

분류 BFS 혼자 힘으로 해결 했는가? O 느낀 점 BFS 유형의 문제는 여러가지 유형이 존재한다. 가장 기본 유형은 하나번의 BFS만을 이용하는 경우이며 이런 경우는 대개 그래프가 연결이 되었는지를 체크할 때 주로 사용이 된다. 그러나 해당 유형은 난이도가 낮아서 BFS 익힐 때 푸는 정도이다. 이 문제는 BFS를 여러번 시도를 해야 하는 경우에 대한 인사이트를 제공하는 것 같다. 문제 난이도가 그렇게 높지 않기 때문에 무의식적으로 잘 해결을 할 수 있지만 한번 고민을 해볼 필요는 있다고 생각한다. BFS를 여러번 수행하는 경우에도 아래와 같이 나눌 수 있다고 생각한다. 각각의 BFS를 따로 진행해도 된다. 그리고 서로에게 어떠한 영향도 없다. 각각의 BFS를 따로 진행해도 되지만 서로에게 영향이 있다..

분류 스택 혼자 힘으로 해결 했는가? O 느낀 점 앞서 2493번을 통해 monotone 스택 문제에 대한 감을 잡은 뒤 도전했다. 등급은 골드4로 2493보다 한단계 더 높지만 둘 다 난이도가 똑같이 느껴졌다. 다만 이 문제는 2493과 달리 검사의 대상이 되는 숫자가 담긴 배열의 역순으로 진행을 해야했다. 아마 현재 값의 우측 값에 관심이 있기 때문에 우측부터 시작해서 현재 값을 기준으로 선행 된 값 중 나보다 큰 값이 처음으로 나오는가? 이렇게 문제를 해결하기 때문인 것 같다. 그리고 이 문제에서 중요한 키워드는 현재 값을 기준으로 오른쪽 값 중에서 가장 왼쪽에 있는 큰 값 이라고 생각한다. 위의 말을 다시 풀어서 쓰면 나보다 우측에 있는 값 중에 처음으로 발견되는 큰 값 따라서 스택을 써서 처음으..

분류 스택 혼자 힘으로 해결 했는가? X 느낀 점 스택 문제를 많이 풀지 않았기 때문에 억지로 스택을 활용하려고 하다가 시간 초과를 맞이했고 결국 실패했다. 스택 하나만으로 이 문제를 어떻게 해결해야하는지 감이 오지 않아 구글링을 해 보았고 Monotone 스택 유형임을 알게 되었다. 그와 동시에 이 문제에서 제시하는 사고 흐름은 반드시 익혀야겠다는 생각을 했다. 내가 작성한 코드 오답 import sys from collections import deque N = int(input()) tower = list(map(int, sys.stdin.readline().rstrip().split())) stack = deque() for i in range(N): tower[i] = (tower[i], i +..