Algorithm
BFS, DFS 탐색 팁
저는 항상 BFS 문제를 풀 때 구현을 다한 뒤 테스트 케이스를 다 통과하고 맞왜틀을 정말 많이 겪었습니다. 한 번 갇힌 사고에서는 탈출하기 정말 어려운 게 알고리즘 문제이고 이러한 경우를 어떻게 하면 줄일 수 있을까 정말 많이 고민했습니다. 그래서 저의 안좋은 습관을 찾고자 노력하였고 치명적이 안 좋은 습관을 한 가지 찾았습니다. 안 좋은 습관은 BFS 탐색의 조건절에서 저는 "찾고자 하는 경우"를 조건으로 넣어주는 습관을 가지고 있었습니다. "이게 뭔소리냐 찾고자 하는 경우를 조건으로 넣는 게 왜 안 좋은 습관이냐?"라고 하실 수 있습니다. 하지만 찾고자 하는 경우를 찾는 것보다는 안 되는 경우를 찾는 게 더 쉽고 정확합니다. 밑에 문제로 예시를 들어보겠습니다. 백준 https://www.acmicp..
이분탐색 구현 팁 및 반환값 줄이기(부제: 공부하며 정리하는 생각들)
공부하면서 참조한 자료 1.종만북 2. https://blog.naver.com/jinhan814/222156334908 이분 탐색, 파라메트릭 서치 안 헷갈리는 TIP 예전에 종만북을 읽으면서 아래 글을 쓴 적이 있습니다. 아래 글에는 반복문 불변식을 이용해 lower_bound,... blog.naver.com 이분탐색은 문제에서 주어지는 탐색 값의 기준을 찾는 것이 문제이다. 예를 들어 1부터 10억cm의 길이의 자를 분할해서 최소 5개의 개수로 나누고 싶은데 이 때 "분할하는 경우에 가장 큰 분할 길이를 구하시오" 같은 문제에서 분할하는 길이를 구하면 되는 문제이다. 알고리즘에 관련된 설명과 강의는 나보다 뛰어나신 분도 너무 많고 작성하시는 분도 너무 많기에 넘어가고 이분탐색을 구현할 때 구현의 ..