PS(Problem Solving)
1.알고리즘 문제 오답노트 양식
알고리즘 오답노트 양식
2.[오답노트] LeetCode #5 Longest Palindrome Substring
반복 연산은 한번 한번이 소중하다. 한번 했을 때, 최대한 많은 정보를 구하고 다음으로 넘어가자.
3.[오답노트] LeetCode #238 Product of Array Except Self
이걸 생각해낸 사람은 천잰가?
4.[오답노트] LeetCode #328 Odd Even Linked List
편법 부릴 생각 말고 정석으로 조금만 더 고민해봐라.
5.[오답노트] LeetCode #17 Letter Combinations of a Phone Number
dfs가 미숙하면 생기는 일
6.[오답노트] 백준 #1931 회의실 배정 (파이썬)
회의를 시작하자마자 끝내버리는 게 무슨 회의인진 모르겠다만...
7.[오답노트] 백준 #1202 보석 도둑 (파이썬)
뭔가 heapq를 쓰면 시간복잡도가 줄어든다는 내용
8.[알고리즘] 다이나믹 프로그래밍 中 점화식 찾는 문제
그렇게 난이도가 높은 것 같지는 않은데, 막막하면 점화식일 가능성 매우 높음!
9.백준 #9019 DSLR (파이썬)
내 수준에서는 어려운 문제(골드 4)인데, 아이디어가 금방 생각났고, 막힘없이 풀어서 통과까지 한 기념으로 뿌듯해서 코드를 올려본다.
10.[오답노트] 백준 #11403 경로 찾기 (파이썬) : 플로이드-워셜
플로이드-와샬 알고리즘 문제 중에 가장 쉬운 문제가 이거 아닐까?
11.백준 #16236 아기상어 (파이썬)
가독성을 챙기려고 BabyShark 클래스까지 별도로 만들었습니다! 코딩 테스트에 클래스 선언이 웬말이냐
12.[오답노트] 백준 #1629 곱셈 (파이썬) : 나머지 연산의 분배법칙
결과값이 어차피 나머지라면, 굳이 나머지 연산하기 이전의 그 큰 수를 다 계산할 필요 없다.
13.최단 경로 알고리즘 : 다익스트라 VS 벨만-포드 VS 플로이드-워셜
솔브닥 CLASS 4의 난관이자 코딩테스트를 위해 반드시 넘어야 하는 벽인 최단 경로 알고리즘에 대해 소개한다. 눈으로 보지만 말고, 반드시 직접 파이썬으로 구현해보자!
14.다익스트라, 벨만-포드, 플로이드-워셜 함수 핵심부만 모아보기
위 글이 너무 길어서 구현 부분을 따로 보면서 외우기가 힘드니까 구현부만 발췌한 글을 새로 작성한다. 알고리즘에 대한 설명은 따로 하지 않겠다.
15.[오답노트] 백준 #13549 숨바꼭질 3 (파이썬) : 0-1 BFS
0-1 BFS는, 0의 가중치를 가진 정점을 왼쪽에 추가하는 것만 빼면 그냥 BFS랑 똑같습니다... 겁먹지 마세요
16.[오답노트] 백준 #12851 숨바꼭질 2 (파이썬)
레퍼런스 도움 안 받고 5트만에 풀어낸 문제!
17.백준 #2609 최대공약수와 최소공배수(파이썬) : 유클리드 호제법
최대공약수, 최소공배수 구하기도 어렵네;;
18.백준 #17144 미세먼지 안녕! (파이썬)
알고리즘 분류가 구현이라는 말은, 그냥 말그대로 빡구현하면 된다는 거다. 시간 복잡도를 줄일 만한 독특한 기법 같은건 없다. Off-By-One Error를 조심하자.
19.백준 #9663 N-Queen (파이썬)
백트래킹의 가장 대표격 문제라 할 수 있는 N-Queen 문제다. 너무 클리셰고 최적화 기법도 많이 들어있으니, 시간 나면 외우자.
20.[오답노트] 백준 #1238 파티 (파이썬)
그래프 간선 방향을 역으로 바꾸면 생기는 일
21.[오답노트] 백준 #2206 벽 부수고 이동하기 (파이썬)
벽을 제거할 수 있는 BFS 최단거리 문제... 3차원 visited 배열로 해결한다?
22.백준 #10844 쉬운 계단 수 (파이썬)
dp 배열을 사용하지 않았던 다이나믹 프로그래밍 문제
23.백준 #1007 벡터 매칭 (파이썬)
신기하게도 Gold 2인데, 브루트 포스 문제다! 하지만 그런 이유가 있지. 굳이 문제를 '그대로' 구현할 필요는 없는 법! 이 문제에서도 진짜 일일이 N!개를 다 매칭시킬 필요는 없었다.
24.백준 #17298 오큰수 (파이썬)
오큰수 = 오른쪽에 있는 수 중에 처음으로 나오는 나보다 큰 수
25.백준 #14503 로봇 청소기 (파이썬)
단순 구현 문제다. raise를 활용하여 깔끔하게 코딩된 것 같아 올린다.
26.백준 #1025 제곱수 찾기 (파이썬) : 과감한 4중 for문
제한이 매우 작으면, 4중 for문도 쓸 수 있구나~ 플로이드-워셜처럼
27.투 포인터를 푸는 기본적인 발상 : 백준 #2467 용액, #1806 부분합, #1644 소수의 연속합
투 포인터 문제를 풀 때는, 1. 이분 탐색과 헷갈리지 말 것. 2. left, right 초깃값에 대해 신중히 생각할 것.
28.백준 #2042 구간 합 구하기 (파이썬) : 세그먼트 트리, 펜윅 트리 두가지 풀이
세그먼트 트리까지는 그렇다 쳐도, 펜윅 트리 생각해낸 사람은 진짜 천재가 아닌가 싶다. 너무 코드가 깔끔하다.
29.백준 #3653 영화 수집 (파이썬) : 세그먼트 트리의 활용
세그먼트 트리 활용 문제는, 세그먼트 트리 문제인줄 모르게 나온다.
30.백준 #1006 습격자 초라기 (파이썬)
원형 2xn 타일링(하지만 1x1 블럭도 쓸 수 있는...)
31.백준 #2098 외판원 순회 (파이썬) : 2022.08. 최신 풀이
테스트케이스가 추가되면서, 그동안 떠돌아다니던 외판원 순회 풀이의 허점이 발견되었다.