- 하루에 한문제를 목표로 한다.
- 문제의 순서는 백준 온라인 강의 -> 코딩테스트 준비 기초와 알고리즘 스터디 커리큘럼을 따르도록 한다.
- 배운것에 대해 그 문제를 푼 당일 적어야한다.
- 이름은 문제번호_문제이름으로 한다. (ex)2309_일곱난쟁이)
back_tracking
| #문제 | #알고리즘 설명 | #배운점 | |
|---|---|---|---|
| 2022.09.06(화) | 부분수열의 합 | 재귀를 이용하여 현재 숫자를 더하는 경우, 더하지 않는 경우 모두 전개해주었다. 일종의 브루트포스라고 생각했음 |
|
| 2022.09.06(화) | 로또 | 재귀 함수 사용. 부분수열의 합과 비슷하게 풀었다. | 재귀함수에서 조건에 충족했는지 확인하기 위해 len(arr) == 6 이 식을 썼는데 arr가 []일때 에러가 발생했다. 다음번에 알고리즘 짤 때 유의해야 할 것 같다. |
| 2022.09.06(화) | 외판원순회2 | 재귀 | 재귀함수를 사용하고 난 후 정답 조건에 부합하는지 체크하는 부분이 미흡한 것 같다. (아직 방문하지 않은 도시가 있다 && 그 도시로 가는 길이 있다) 이 조건이 맞으면 재귀를 시작했고, 현재 도시에서 모든 도시가 저 조건을 만족하지 않으면 모든 도시를 돌았다고 생각하고 결과값과 비교했다. 하지만 현재 도시에서 다른 도시로 길이 없을 뿐, 방문하지 않은 도시가 있는 반례가 존재했다. 모든 도시를 돌았는지 확인한 후 다시 첫번째 도시로 가는 길이 있는지 체크하니 정답이었다. |
기초 - 브루트포스
| #문제 | #알고리즘 설명 | #배운점 | |
|---|---|---|---|
| 2022.01.09일(일) | 일곱난쟁이 | 아홉 난쟁이들의 키의 총 합을 구한 후 두 난쟁이의 키를 뺀다. 이때 값이 100이면 출력 |
del arr[1] or arr.remove(1) a.sort() or a = sorted(a) 파이썬 함수에 아직 익숙하지 않은 듯 하다.. |
| 2022.01.10일(월) | 사탕 게임 | 전체 맵에서 가장 긴 연속부분의 길이를 센다 칸 두개를 바꾸면서 해당 줄의 가장 긴 연속부분의 길이를 센다. 이때 row방향으로 칸 두개를 바꾸면, 해당 칸 두개의 column과 해당 row만 count해주면 된다. 마찬가지로 column방향으로 칸 두개를 바꾸면, 해당 칸 두개의 row와 해당 column만 count해주면 된다. |
|
| 2022.01.10일(월) | 날짜 계산 | 1씩 더해주며 입력으로 들어온 값과 비교해준다. | 변수 할당에도 if else문을 쓸 수 있어 편리했다. |
| 2022.01.11일(화) | 리모컨 | 고장난 버튼이 없으면 100에서 +-로 움직인것과 버튼 누른것의 최솟값 버튼이 모두 고장났으면 100을 빼준 값이 정답 9999999이하의 숫자중 고장난 버튼을 제외한 나머지 버튼으로 만들 수 있는 수의 경우를 다 만들어본다. min( abs(N-100)[시작점에서 N까지 +-버튼을 누른 횟수], len(수)[수를 만들기위해 버튼을 누른 횟수] + abs(수 - N)[+-버튼 누른 횟수])이 정답이된다. 0버튼을 눌러 0에서부터 횟수를 셀 수 있는데, 일의자리만 이 방법을 사용해서 틀렸었다. 10과 같은 수에도 유효하다. 조건문을 잘 보고 써야할 것 같다. |
for문, if문 한줄에 쓸 수 있어 코드가 간결해진다. global변수를 사용할 때 유의해야한다. |
| 2022.01.16일(일) | 카잉달력 | x,y변수에 1씩더하여 범위 비교를 해줬던 날짜계산문제와 달리, 이 문제에서는 똑같이 하면 시간초과가 난다. 그래서 이 문제를 풀때는 x의 값은 문제에서 주어진 값과 같게 맞춰놓고, y값을 더해서 범위 비교를 해주면서 cnt를 해주었다. 이때 한번 나왔던 y의 값이 다시 나온다면, 이는 날짜를 찾을 수 없는 경우이므로 -1을 출력하게 해주었다. |
반례를 생각할 때 좀 더 깊이 생각해야 할 것 같다. 알고리즘은 맞게 짠거같은데 자꾸 시간초과가 나서 보니, python은 input()으로 받아오면 느리기때문에 sys.stdin.readline()으로 받아오는것이 좋다는 것을 배웠다. 또, 백준에서 언어 설정을 Python3로 했을때는 시간초과가 났는데, PyPy3으로 언어설정을 한 후 채점을 하니 맞았다 c++은 통과하는 알고리즘을 파이썬으로 짜서 채점할 경우 시간초과가 나는 경우가 생긴다고 한다. 이때 PyPy3으로 채점한다고 한다. 이 블로그에서 위와 같은 점들을 배울 수 있었다. |
| 2022.01.16일(일) | 수 이어쓰기1 | 시간제한이 0.15초였다. 수를 다 이어붙여서 길이를 재는것은 무리라는 생각이 들었다. N이 101일때, 1-9까지는 자릿수가 1개이므로 9x1, 10-99까지는 자릿수가 2개이므로 2x90 그리고 +2 이런식으로 곱셈을 이용해 수를 이어붙인 값의 길이를 쟀다. |
|
| 2022.01.16일(일) | 1,2,3더하기 | 현재 수가 n이라고 할 때 n을 만드는 방법의 수가 R(n)이면 R(n) = R(n-1) + R(n-2) + R(n-3)으로 식을 만들 수 있다. R(n-1)의 방법들 뒤에 + 1을 붙인다면 n을 만드는 방법이 된다. 그렇기때문에 위 식을 세울 수 있다. |
기초 - Queue and Graph
| #문제 | #알고리즘 설명 | #배운점 | |
|---|---|---|---|
| 2022.06.11일(토) | DFS와 BFS | DFS와 BFS | edge = [[]] * (N + 1) 이렇게 해준다면 얕은 복사가 되어 N+1개의 1차원 배열이 모두 같은 값을 가지게 된다. 그래서 빈 배열에 for문과 append()함수를 이용해 빈 1차원 배열을 넣어주었다. 이를 코드 1줄로 간단히 할 수 있었는데, edge = [[] for _ in range(N+1)] 이렇게 해주면 됐다. |
| 2022.06.11일(토) | ABCDE | DFS | 1) 처음 풀었을 때 seen을 DFS함수의 매개변수로 넣었는데, 재귀를 사용하면서 전역변수인 seen의 배열의 값이 c++처럼 함수 내에서만 바뀌는게 아니라 전체적으로 바뀌어 문제가 됐었다. 2)깊은 복사 : arr = [[False]*n for _ in range(n)] 얕은 복사 : [[False] * n] * n ex) {a = [[1]*3]*2} == {a = [[1,1,1],[1,1,1]]} -> {if: a[0][0] = 3} => {a = [[3,1,1],[3,1,1]]} 3) sys.exit()를 사용했으나 오류가 났는데, 이는 VSCode에서 언어 인식에서 오류가 난 것이었음. 언어를 바꿔주니 해결. |
| 2022.06.11일(토) | 미로탐색 | BFS | 1) And와 & And : lazy evaluation. -> if the first statement is False, it does not check the second statement. and returns False immediately & : bitwise 참고 2)sys.stdin.readline() & input() input() : 입력이 주어질 때 "10101"이 주어진다면 저 값만 받아옴 sys.stdin.readline() : 그 줄을 읽어오는 것이기 때문에 줄바꿈값까지 받아오게 됨. list로 만든 후 int함수를 적용하면 '/n'에는 int함수를 적용할 수 없기때문에 에러가 난다. |
| 2022.06.11일(토) | 토마토 | BFS |
기초 - BFS
| #문제 | #알고리즘 설명 | #배운점 | |
|---|---|---|---|
| 2022.06.12일(일) | 숨바꼭질 | BFS | 1) seen배열의 크기를 고정되지 않은 값인 K,N으로 하니 인덱스 오류가 났다. 최대값으로 설정하는게 좋을 것 같다. 2) 위치가 음수의 값이 되는 경우를 생각을 못했다. 3) for nxt in [now+1. now-1, now*2] 이렇게 효율적으로 코드를 짤 수 있는 것을 배웠다.(이전에는 if문으로 3개의 케이스를 처리해주었다.) |
| 2022.06.12일(일) | 숨바꼭질3 | BFS | 이미 방문한 노드를 체크해주는 과정에서, *2연산이 0초가 걸리므로 먼저 체크해줬어야했는데, +1, -1과 같이 1초가 걸리는 연산을 먼저 하면서 체크해줘서 틀렸었다. |
| 2022.06.13일(월) | 알고스팟 | BFS | |
| 2022.08.30일(화) | 숨바꼭질4 | BFS | • a = a + [100001] ⇒ O(N) (a라는 배열에 100001을 더해 새 배열을 만드는거라서) • a.append(100001) ⇒ O(1) • a = a + [1,2,3] ⇒ O(N+K) • a.extend([1,2,3]) ⇒ O(K) • a += [4,5,6] ⇒ O(K) (extend취급)한 숫자를 방문할때마다 리스트에 그 숫자로 가는 루트를 저장했다. 그러니 메모리 초과와 extend, clear 함수 때문에 시간초과가 났다. 그래서 한 숫자를 방문할 때 그 이전 숫자를 배열에 저장해주었고, 역추적을 통해 답을 도출할 수 있었다. |
| 2022.09.06일(화) | 알파벳 | BFS | deque에 지나온 알파벳들을 넣고 다음 칸의 알파벳이 q에 있는지 board[ax][bx] not in q로 풀었다가 시간초과가 났다. 알파벳을 지나왔는지 체크해주는 배열을 만들어 O(1)로 체크를 해주니 통과할 수 있었다. |
기초 - Dynamic Programming
| #문제 | #알고리즘 설명 | #배운점 | |
|---|---|---|---|
| 2022.06.12일(일) | 1로 만들기 | DP | |
| 2022.06.12일(일) | 1,2,3 더하기 | DP | |
| 2022.06.12일(일) | 가장 긴 증가하는 부분수열 | DP | |
| 2022.06.12일(일) | 가장 긴 증가하는 부분수열4 | DP | |
| 2022.06.12일(일) | 이친수 | DP | |
| 2022.06.12일(일) | 퇴사 | DP | |
| 2022.06.13일(월) | 퇴사 | DP | |
| 2022.06.13일(월) | 1,2,3더하기3.py | DP | |
| 2022.09.06일(화) | 타일채우기 | DP | 점화식 : dp[n] = 3dp[n-2] + 2dp[n-4] + ... + 2*dp[0] 점화식을 만드는 부분이 제일 어려웠다. n=6일때 경우의 수를 잘 못 세서 처음 짰던 알고리즘 자체가 틀린 알고리즘이었다. 좀 더 익숙해져야 할 것 같음 |