알고리즘과 자료구조 썸네일형 리스트형 [파이썬 알고리즘 Tip] 반복문 안에서는 리스트에 절대 원소를 추가/삭제하지 않는다 알고리즘 문제가 아주 쉽든, 어려든 간에 for 문으로 리스트의 원소를 순회하는 코드는 항상 쓸 수밖에 없다. N = 100 arr = [i for _ in range(N)] to_be_removed = [1, 5, 7, 10] for item in arr: if item in to_be_removed: # 조건에 따라 어떤 명령을 실행 그런데 여기서 치명적인 실수를 종종 할 때가 있다. 바로 순회하는 iterable 객체(리스트)의 원소를 직접 건드리는 것이다. 이런 간단한 상황을 생각해보자. arr = [1, 2, 3, 6, 7, 9] for item in arr: if item % 3 == 0: arr.remove(3) 주어진 리스트(arr)에서 어떤 조건(3으로 나눈 나머지가 0)을 만족하면, 그.. 2024. 3. 12. 16:51 ㆍ 알고리즘과 자료구조 코드트리(codetree) x 글또 블로그 챌린지 1차 후기: 코딩 테스트 준비에 최적화된 서비스, 코드트리 저번 1월 말, 글또 채널에서 공지가 하나 올라왔다. 코드트리라는 플랫폼에서 글또랑 협업하는 차원에서 신청자들에게 커리큘럼 무료 혜택을 제공한다는 내용이었다. 사실 코딩 테스트 플랫폼이라고 하면 백준, 프로그래머스밖에 모르던 나라 낯선 플랫폼을 선뜻 이용하기 망설여졌다. 그래도 '속는 셈 치고 한번 신청해볼까?'라는 맘으로 신청했고, 정말 잘했다는 생각을 하고 있다. 중간중간 바빠서 많이 쉰 게 너무 아쉽지만, 코드트리를 한 달동안 이용하면서 느꼈던 점을 정리해보려고 한다. 장점 1: UI/UX 장점 2: 문제 풀이 해설과 가이드 장점 3: 유형별/주제별로 잘 구분된 커리큘럼 장점 4: 기타 기능 (기업별 커리큘럼, 실전 훈련 등) 개선점 총평 1. 크고 아름다운(?) UI ( + 계속 사용할 수밖에 없.. 2024. 3. 2. 21:25 ㆍ 알고리즘과 자료구조 BFS 1: BFS 동시 탐색 유형 (백준 2146번 파이썬) 백준 2146번: 다리 만들기 일반적인 BFS를 생각해보자. 한 출발점을 기준으로 상하좌우 최단경로를 탐색하면 된다. 기본만 짚고 넘어가자면, BFS는 그래프의 모든 간선의 가중치가 동일할 때에만 최단 경로를 구할 수 있다. 2차원 배열이 나오면 BFS를 주로 쓰는 이유도 그 때문이다. 2차원 배열은 각 칸 (i, j)이 정점이고 간선의 가중치가 1로 동일한 그래프로 생각할 수 있다. BFS 1: 한 출발점과 도착점이 정해져 있는 경우 따라서 2차원 배열에 어떤 한 출발점과 어떤 한 도착점이 정해져 있다면 BFS를 써서 아주 답을 쉽게 구할 수 있다. 2206번(벽 부수고 이동하기)이 그 예다. 물론 이건 다른 조건이 붙어서 어려워지지만... 2146번도 저 아이디어를 활용하면 풀 수 있다. 우선 모든 .. 2023. 4. 3. 15:34 ㆍ 알고리즘과 자료구조/Graph Traversal Dynamic Programming 5: DP 배열 설정의 중요성 (백준 14238, 17404, 12969번) 백준 14238번: 출근 기록 문제 설정은 간단하다. 각 알파벳 A, B, C에 대해서 아래 조건을 금방 파악할 수 있다. 그렇지만 문제 조건을 잘 파악했다 하더라도 다음이 문제다. 기존 문제처럼 dp 배열이 1차원 또는 2차원이라고 가정하고 접근해보자. DP 배열이 1차원이라면? dp[n] = V : 길이가 n인 문자열 중 올바른 출근 기록인 경우의 수(또는 문자열들의 배열?) 점화식을 세울 때 dp[n]과 dp[n-1] 사이 관계를 어떻게 정의할 수 있는가? 길이가 n-1인 문자열 오른쪽 끝에 A를 추가했을 때, B를 추가했을 때 그리고 C를 추가했을 때 매번 기존 문자열의 끝에 어떤 문자가 오느냐에 따라 추가할 수 있는지 없는지가 달라진다. 또는 dp[n]에 길이가 n인 가능한 모든 문자열들을 배열.. 2023. 4. 3. 14:21 ㆍ 알고리즘과 자료구조/Dynamic Programming Dynamic Programming 5: DP 배열 설정의 중요성 (백준 14238, 17404, 12969번 파이썬) 백준 14238번: 출근 기록 문제 설정은 간단하다. 각 알파벳 A, B, C에 대해서 아래 조건을 금방 파악할 수 있다. 그렇지만 문제 조건을 잘 파악했다 하더라도 다음이 문제다. 기존 문제처럼 dp 배열이 1차원 또는 2차원이라고 가정하고 접근해보자. DP 배열이 1차원이라면? dp[n] = V : 길이가 n인 문자열 중 올바른 출근 기록인 경우의 수(또는 문자열들의 배열?) 점화식을 세울 때 dp[n]과 dp[n-1] 사이 관계를 어떻게 정의할 수 있는가? 길이가 n-1인 문자열 오른쪽 끝에 A를 추가했을 때, B를 추가했을 때 그리고 C를 추가했을 때 매번 기존 문자열의 끝에 어떤 문자가 오느냐에 따라 추가할 수 있는지 없는지가 달라진다. 또는 dp[n]에 길이가 n인 가능한 모든 문자열들을 배열.. 2023. 3. 29. 17:29 ㆍ 알고리즘과 자료구조/Dynamic Programming Dynamic Programming 4: 배낭 문제 (백준 7579, 2629번 파이썬) Dynamic programming 개념을 설명할 때 피보나치 수열 말고도 가장 흔하게 언급되는 예시가 배낭 문제(knapsack problem)이다. 어느 정도 난이도가 있는 배낭 문제는 DP로 푸는 게 대부분이다. 배낭 문제를 처음 접해본 사람은 올바른 풀이를 떠올리기 정말 어렵다. 그러나 배낭 문제는 결국 사소한 문제 설정에서 차이가 있을 뿐 비슷한 유형의 문제를 풀다보면 동일한 패턴을 발견하게 된다. 결국 배낭 문제는 풀이 방식이 비슷하기 때문에 아예 풀이를 외울 정도까지 익숙해지는 게 좋다고 생각한다. 배낭 문제에 속하는 예시 몇 가지를 아래에서 살펴보자. 백준 7579번: 앱 문제 설정은 앞서 살펴본 11066번(파일 합치기)와 11049번(행렬 곱셈 순서)와는 다르다. 이전 문제는 어떤 연속.. 2023. 3. 29. 15:35 ㆍ 알고리즘과 자료구조/Dynamic Programming Dynamic Programming 3: 재귀(top-down)를 이용한 풀이 (백준 11049번 파이썬) 2번째 글에 이어서 재귀를 이용한 top-down 방식의 풀이를 소개하려고 한다. 백준 11049번: 행렬 곱셈 순서 언뜻 다른 것처럼 보이지만 백준 11066번(파일 합치기) 문제와 매우 비슷하다. 두 문제는 아래와 같은 공통점이 있다. 어떤 연속된 값들을 하나씩 더하거나 곱해간다. 두 개를 합쳐 하나로 만드는 과정을 반복한다. 최종 행렬 곱셈 결과를 이미 구했다고 가정했을 때 그 값은 결국 어떤 두 행렬을 곱한 결과고, 각 두 행렬을 더 작은 문제(행렬의 곱셈 결과)로 쪼개나간다는 컨셉은 11066번과 판박이다. 다만 11066번과 다른 점은 단순 합을 구하는 게 아니라 행렬의 곱을 구한다는 점이다. 여기서 dp 배열 말고도 메모이제이션을 통해 재활용해야 하는 값이 생긴다. 아래 코드를 살펴보자. 재.. 2023. 3. 29. 14:15 ㆍ 알고리즘과 자료구조/Dynamic Programming Dynamic Programming 2: 재귀(top-down) vs. DP(bottom-up) (백준 11066, 1520, 1937번 파이썬) Dynamic Programming(DP) 개념을 처음 소개할 때 빠지지 않고 등장하는 게 피보나치 수열이다. 설명 글을 요악하면 다음과 같다. 1) 피보나치 수열을 재귀함수를 이용해 구한다. 2) 재귀함수로 구할 때 중복된 계산이 발생한다. 어차피 같은 답을 내놓는 연산을 여러 번 반복하니 불필요하고 비효율적이다. 3) 불필요한 연산을 방지하기 위해 memoization, 즉 DP 개념을 도입한다. 여기에 핵심이 있다. 우리는 같은 DP 문제에 대해 재귀로 풀 수도 있고, DP로도 풀 수 있다. 이유는 애초에 DP 문제가 다음 성질을 지니기 때문이다. 1) 큰 문제(마지막 항, f(n), 구하고자 하는 답, 현재 상태)를 작은 문제(초기값, 이전 상태, 직전 단계)에 의존하는 관계식으로 표현할 수 있다.. 2023. 3. 28. 15:42 ㆍ 알고리즘과 자료구조/Dynamic Programming 이전 1 2 다음 목록 더보기
