난이도: Lv.2유형: bfs / dfs해결 여부:오답아이디어2차원 리스트에서 인접한 값들의 합을 리스트로 뽑아라 라는 문제다. 문제 자체는 간단하다.. 오답 이유 혹은 알게 된것파이썬으로 bfs 하는 문제에 대한 자각이 없어서 for문으로 아래방향, 오른쪽 방향으로 쭉 돌리면 되겠지 생각했다가 그렇지 않은 모양도 있다는 걸 깨달았다.처음에는 똑같은 2차원 리스트를 하나 더만들어서 방문여부를 확인하려 했다. 근데 그냥 방문하면서 해당 위치를 'X'로 바꾸는게 공간복잡도 적으로도 훨씬 효율적이었다. 2차원 배열의 합은 numpy 모듈사실 문제 자체에 주어진건 1차원 배열이고 그 안의 문자열이라서 따로 처리를 해주어야 했다. 그냥 arr[i][j] 이런식으로 문자열 바꾸려고 하면 에러가 났다. maps = ..
Algorithm
난이도: Lv. 3유형: DP, 수학, 부분합해결 여부: 오답아이디어홀수는 들어올 수 없다. 애초에 0으로 잡아야 한다.짝수가 들어올때 이전에 있던 모양에서 가로 2줄씩 3가지 경우가 붙는다고 봐야 한다.. 하지만 여기에 특수한 형태가 있다. 오답 이유 혹은 알게 된것DP로 접근하는 것 까지는 맞았으나, 이후 점화식에서 틀렸다. f(n)은 항상 f(n-2) 에서 도출되며 3*f(n-2) +2 로 잡았는데 f(n-4) 에서도 도출되는 경우를 생각해야 했다. 만약 하나만 세로로 하고 그 옆을 3줄짜리 가로로 주르륵 채운다면 그건 f(n-2) 에서는 얻을 수 없는 형태가 된다. 그래서 f(n) = 3f(n-2) -> f(n-2) 에서 3칸 붙이기 뿐만 아니라 2f(n-4), 2*f(n-6) ...2f(0) ..
서문학교에서 알고리즘 수업을 듣는데 이해가 안 되는 부분은 GPT가 짠 예시 코드를 보면서 해결했다. 그런데 그 과정에서 GPT는 곧잘 쓰지만 나는 잘 쓰지 않았던 문법들이 있어서 정리해 보았다. 코딩테스트에서 유용하게 쓰일 것이다.자료구조 자료구조 안에 자료형을 명시한다. 자료'구조'와 자료'형'의 차이 때문에 매번 어디에 어떤 게 들어가야 할지 자주 헷갈렸던 문법이다.자료구조 안에 자료형을 명시한다.예를 들어 vector는 정수형 벡터이다.vector> matrix; // 2차원 정수 벡터static_cast이런 자료형은 static_cast로 형을 변환할 수 있다.문법: static_cast(바뀌는 변수명)예:double num = 3.14;int intNum = static_cast(num); ..
이전 내용 [알고리즘] 7. Backtracking1. Brute force2. Divide and conquer3. Decrease and conquer4. Transform and conquer5. Greedy Method6. Dynamic Programming7. Backtracking8. Branch and Bound여기서는 Backtracking에 대해 다룬다. Backtracking이란DFS인데 조건이 있어juneforpay.tistory.com 1. Brute force2. Divide and conquer3. Decrease and conquer4. Transform and conquer5. Greedy Method6. Dynamic Programming7. Backtracking8. B..
이전 내용 [알고리즘] 6. Dynamic Programming1. Brute force2. Divide and conquer3. Decrease and conquer4. Transform and conquer5. Greedy Method6. Dynamic Programming7. Backtracking8. Branch and Bound여기서는 Dynamic Programming 에 대해 다룬다.Dynamic Programming이란DP는 반복juneforpay.tistory.com 1. Brute force2. Divide and conquer3. Decrease and conquer4. Transform and conquer5. Greedy Method6. Dynamic Programming7. ..
이전 내용 [알고리즘] 5. Greedy Method 내용 정리1. Brute force2. Divide and conquer3. Decrease and conquer4. Transform and conquer5. Greedy Method6. Dynamic Programming7. Backtracking8. Branch and Bound여기서는 Greedy Method 에 대해 다룬다. Greedy method란그리디 알고리juneforpay.tistory.com 1. Brute Force2. Divide and conquer3. Decrease and conquer4. Transform and conquer5. Greedy Method6. Dynamic Programming7. Backtracki..
이전 내용 [알고리즘] 4. Transform and Conquer 내용 정리1. Brute force2. Divide and conquer3. Decrease and conquer4. Transform and conquer5. Greedy Method6. Dynamic Programming7. Backtracking8. Branch and Bound여기서는 Transform and conquer 에 대해 다룬다.Transform and Conquer란문제를juneforpay.tistory.com 1. Brute force2. Divide and conquer3. Decrease and conquer4. Transform and conquer5. Greedy Method6. Dynamic Program..
이전 내용 [알고리즘] 3. Decrease and Conquer 내용 정리1. Brute force2. Divide and conquer3. Decrease and conquer4. Transform and conquer5. Greedy Method6. Dynamic Programming7. Backtracking8. Branch and Bound여기서는 Decrease and conquer에 대해 다룬다.Decrease and Conquer란주어진 문juneforpay.tistory.com 1. Brute force2. Divide and conquer3. Decrease and conquer4. Transform and conquer5. Greedy Method6. Dynamic Programmin..
