완점 탐색 방식에서 시간초과가 발생하면, 대안으로 누적합, 투포인터, meet in the middle 방식을 사용할 수 있다.
-
문제를 절반으로 나눠서 양쪽 절반에 모든 경우를 다 해보는 방법이다.
-
탐색의 크기가 많이 줄어든다.
문제의 크기가 N인 경우 2N 에서 2N/2+2N/2 으로 줄어들게 된다. = O(2n/2)
| 번호 | 날짜 | 문제 번호 | 풀이법 | 주의사항 | 새롭게 배운 내용 | 다시 풀어보기 |
|---|---|---|---|---|---|---|
| 1 | 24.07.29 | BOJ 16917 | 반반치킨이 0마리 ~ 최대마리수 인 모든 경우를 고려하여 최소 가격 구하기 | 반반치킨이 비싼 경우는 가지치기 (반반치킨 무시한 결과 출력 후 바로 종료) | - max(0, 어떤값) : 음수 방지 - 내가 구해야 하는 값, 답을 구하는 데 계속 변화하는 값에 집중하자! |
|
| 2 | 24.07.29 | BOJ 16968 | 쉽고 간단한 브루트 포스 문제 | |||
| 3 | 24.07.29 | BOJ 16922 | 식1) a+b+c+d = 인풋! 식2) a+5b+10c+50d = (만들 수 있는 숫자) 식 세워서 구함 | 4중 for문 사용,, 더 나은 풀이법 찾기! | ||
| 4 | 24.07.30 | BOJ 16936 | 입력받은 리스트에서 숫자 하나씩 가져와서 정답 리스트 맨앞 or 맨뒤에 하나씩 붙이기 | 나눗셈으로 조건 따지면 (1. 나눠 떨어지는가 -> 2. 그 때의 몫) 계산이 길어져서, 그냥 모두 곱셈으로 구현 | list.pop() 의 파라미터에는 값(x) 인덱스(o) 가 들어가야한다. |
|
| 5 | 24.07.31 | BOJ 16943 | A 배열로 만들 수 있는 모든 숫자열 만들기 -> 모두 B랑 비교해서 그 중 가장 큰 수 출력 | 파이썬의 메서드 잘 활용하자! | from itertools import permutations -> permutations(arr) : 입력된 iterable의 요소들로 만들 수 있는 모든 순열을 생성 |
|
| 6 | 24.08.01 | BOJ 16924 | '*' 인 모든 부분을 십자가의 중심이라 생각하며 반복하기 | 브루트 포스를 풀 때에는 모든 요소에 일관되게 적용할 수 있는 조건이 무엇인지 고민해보기! | list(input()) 이렇게 입력 받으면 이어진 문자열을 리스트에 한 글자씩 저장할 수 있다. |
✅ |
| 7 | 24.08.02 | BOJ 1476 | 구해야 하는게 뭔지!! 항상 생각해 | |||
| 8 | 24.08.03 | BOJ 2003 | ||||
| 9 | 24.08.04 | BOJ 10974 | ||||
| 10 | 24.08.05 | BOJ 16937 | 두 스티커를 붙이는 방법 8가지 -> 모든 스티커에 대해 이 경우를 모두 고려 | |||
| 11 | 24.08.05 | BOJ 16938 | 파이썬 itertools.combination 함수를 써서 모든 경우를 고려함 | PYTHON IS GOD..🙇🏻♀️ | ||
| 12 | 24.08.06 | BOJ 16637 | 하.. 진짜 어렵다.. 그래도 브루트 포스는 고려할 경우의수가 적으니까 정 안되면 노가다라도 하자!!! | 배열을 계속 얕은 복사 해서 여러 상황들 간에 충돌이 발생했다.. 근데 매번 깊은복사 하는거 말고 더 효율적인 방법이 없을까ㅠ | 괄호의 역할 = 우선 계산!! 괄호를 직접 넣을 생각을 하지 말고, 미리 계산하고 (계산한 값)+0 으로 치환하라! |
|
| 13 | 24.08.07 | BOJ 17088 | 등차수열의 개념에서 '첫항 & 공차 만 있으면 구할 수 있다.'는 점을 이용한 풀이 | 입력된 리스트의 길이가 1인 경우 바로 끝내게 처리 (예외처리) | 문제에 나온 소재(등차수열)의 개념에 접근하면 더 쉽게 풀 수 있다! | |
| 14 | 24.08.08 | BOJ 15686 | 배열은 입력 받을 때에만 사용, 이후 계산은 모두 저장한 1,2의 위치 좌표만 사용 | 배열 사용X, 좌표만 사용! | 알고리즘도 수능 수학 문제랑 똑같다! 문제에서 풀이법을 제시하니까 잘 따라가기!!! | |
| 15 | 24.08.08 | BOJ 2210 | 모든 위치를 시작 위치로 두고, dfs를 통해 길이 6짜리 수 만들기 | 또 배열 얕은복사 문제,,😤매번 dfs를 호출할 때마다 깊은 복사를 해서 호출하기!! | ||
| 16 | 24.08.09 | BOJ 3019 | 모든 형태의 블럭을 고려해야 하는 노가다 구현 | |||
| 17 | 24.08.09 | BOJ 2422 | 제거조건 조합을 2차원 배열로 저장 -> 해당 조건이 포함되는지 확인할 때, 반복문을 사용하는게 아니라 조건문만 쓰면 됨 (for문 개수 -1) | 반복문을 없애기 위해 2차원 배열 형태로 나타낸다는 것이 새로웠다! 많이 써먹어야지~ | ||
| 18 | 24.08.09 | BOJ 17089 | 위 문제의 2차원 배열 활용법 + 가지 치기를 통해 삼중 for문에서 마지막 for문이 실행되는 횟수 줄이기! 시간 복잡도가 N3에서 (N2+M*N) 이 됨 | 친구 수를 매번 구하면 시간초과 될 수 있음. 입력 받을 때 따로 저장해두자~ | 삼중 for문(N3)은 500이하만 가능! | |
| 19 | 24.08.10 | BOJ 9944 | 모든 빈칸을 시작점으로 하여 그래프 탐색 | 매번 탐색이 끝난 후에는 arr를 원상복구 해야한다! | 풀었어도 잘 모르겠다.. 다시 풀어보기 (๑و•̀Δ•́)و | ✅ |
| 20 | 24.08.11 | BOJ 17070 | dfs를 통해 이동 방법에서의 모든 경우의 수를 고려 | 파이썬이라서 dfs로 하면 시간초과가 났다. Pypy3로 간신히 통과.. | Pypy를 사용할 때, recursion limit을 너무 크게 설정하면 실행 하자마자 메모리 초과가 뜬다. Pypy3 할 때는 그 부분 삭제하기! | |
| 21 | 24.08.12 | BOJ 16638 | dfs(재귀)&백트래킹을 통해 괄호가 올 수 있는 모든 경우의 수를 고려하여 식 계산하기 | 16637문제와 비슷하지만 곱셈 우선 연산 조건이 추가됨 -> 괄호를 우선 계산할 때 +0 대신 *1로 모두 변경! |
완전 탐색에 좀 익숙해진듯~ ☆٩(｡•ω<｡)و 코드를 더 효율적으로 짜는 연습을 하자! |
|
| 22 | 24.08.12 | BOJ 17406 | 모든 회전 순서를 고려하여 배열의 값을 구하고, 그 중 최솟값을 출력 | 또 얕은 복사, 깊은 복사 때문에 틀렸다. - 얕은 복사 : arr[:]- 깊은 복사 : copy.deepcopy(arr) |
배열 회전 구현할 때 헷갈림,, 어느 행이 어느 방향으로 회전하는지 명시한 다음에 구현하니까 더 편했다~ | |
| 23 | 24.08.13 | BOJ 17085 | 6중 for문을 통해 모든 경우 고려하기.. 이렇게 복잡한 코드는 처음이네 | 곱의 최댓값을 구하는거기 때문에 십자가의 크기가 최대일 때에만 고려하면 답을 구할 수 없다. 모오오든 경우를 고려해야만함! | ||
| 24 | 24.08.13 | BOJ 16987 | dfs 백트래킹 방법을 통해 계란을 치는 모든 순서 고려하기 | 🌟dfs 재귀로 그래프 탐색 시 함수 호출 후 배열 원상복구 필수!!! 그리고 종료 조건 꼼꼼히 확인하기!!🌟 | sum(),all() 함수 안에 for문을 사용해서 모든 원소 검증하는거 배웠다! |
|
| 25 | 24.08.14 | BOJ 16988 | 1. 브루트 포스로 바둑돌 놓는 모든 경우의 수 고려 2. 모든 1의 경우에 bfs로 죽은 바둑돌 수 구하기 |
bfs 탐색 시 if 문 하나가 있고 없고에 따라 오답과 정답이 나눠짐.. if문 쓸 때 항상 조심해야지 | 정답?이랑 같은 방식으로 풀어서 기분이 좋다~ (๑'ᵕ'๑)⸝* (2단계로 나눠서 풀기) | |
| 26 | 24.08.15 | BOJ 16945 | 문제의 조건에 부합하는 모든 배열을 생성해서 비교한다!! 배열의 크기가 너무 작아서 어떤 방법이든 다 가능했을듯~ | 문제를 잘 읽자! | ||
| 27 | 24.08.15 | BOJ 14939 | 1. 첫번째 줄에서 전구를 바꾸는 모든 경우의 수 고려 2. 아래 줄에서는 위의 줄에 따라 바꿀지 말지가 결정된다. |
비트 연산자가 오랜만이라 좀 신기했다. 다시 공부하자~ 혼자 플래를 거뜬히 푸는 그날까지 화이팅~~ (๑˃̵ᴗ˂̵)و | ||
| 28 | 24.08.16 | BOJ 15683 | dfs처럼 재귀함수를 통해 존재하는 cctv의 방향에 따른 모든 조합을 고려해서 풂 | 코드가 길어서 무식한 방법처럼 보이지만, 때론 무식한게 가장 간단한 해결방법 같다 | ||
| 29 | 24.08.17 | BOJ 15684 | 최대 3번 다리를 추가할 수 있으니까 dfs 재귀를 통해 다리를 놓고 -> 조건에 만족하는지 확인 을 반복함 | deepcopy()는 시간이 매우 오래 걸린다! 최대한 사용을 지양하고 리스트 수정사항을 복구하는 방식을 사용하자! |
||
| 30 | 24.08.17 | BOJ 4902 | 배열의 부분합 방법을 사용하여 연산 시간 단축 & 모든 좌표를 꼭대기(중심) 삼각형으로 정한 후, 각 경우에 대해 계산한다 | 삼각형 합의 최댓값이 음수가 될 수 있으므로, 처음 ans의 값을 음의 무한대 float('-INF)로 선언해야 한다!!! |
단위 삼각형의 위치를 2차원 배열로 나타내서 편리한 연산ㄱㄱ (이 방법을 사용하려면 그림을 그려서 좌표의 위치를 이해해야함) | ✅ |
| 31 | 24.08.18 | BOJ 1182 | 진짜 무식한 방법. 만들 수 있는 모든 부분수열의 조합을 다 구해서 합을 구하고, 그중에서 일치하는 경우만 count 한다. | |||
| 32 | 24.08.19 | BOJ 1208 | [meet_in_the_middle] 수열을 절반으로 나눠서, 절반에서 나올 수 있는 부분수열을 모두 구함 -> 두 집합의 부분수열을 조합하여 경우의수 세기 | O(2N)은 시간초과가 발생하지만 O(2N/2+1) 은 괜찮을 때 이 방법 사용하자! | 아직 중간에서 만나기 방법을 잘 모르겠다.. | ✅ |
| 33 | 24.08.19 | BOJ 2143 | [meet_in_the_middle] 1208번의 풀이법과 비슷하지만 배열을 직접 쪼갤 필요X (배열 a, b를 쪼개진 배열이라 생각하면 된다) | 1208번보다 수열의 크기는 훨씬 크지만, 연속된 수들의 합만 고려하기 때문에 부분수열의 경우의 수는 그렇게 많지 않다. + 연속된 부분수열의 합을 구할 땐 누적합을 쓰자! | Counter 모듈을 사용하면 리스트에서 해당 원소의 개수가 몇개인지 구할 수 있다 -> 투포인터 방식이 아니라 counter로 구할 수도 있다! |
|
| 34 | 24.08.20 | BOJ 1759 | 만들 수 있는 모든 순열을 만든 후, 조건에 부합하는 배열만 답 배열에 넣어서 출력! | |||
| 35 | 24.08.21 | BOJ 7453 | [meet_in_the_middle] 배열을 나누는게 아니라, 답을 구하는 조건을 나눠서 N4을 2*N2으로 바꿈! | i in arr 연산은 생각보다 많은 연산시간이 길다! |
Counter 를 사용하면 in 연산 없이도 사용 가능하다! |
|
| 35 | 25.07.29 | BOJ 1062 | 가르칠 수 있는 모든 조합을 생성 → 그 때마다 읽을 수 있는 단어 개수 카운트하기 | combinations(arr, r) 에서 len(arr) < r 이면 빈 배열을 반환한다!!! 이 경우 조건문을 통해 미리 걸러야한다. |
ord('a')을 통해 문자들의 아스키코드를 구할 수 있다. 'a'의 아스키코드는 97 |