파이썬 코딩테스트 (18) 썸네일형 리스트형 알고리즘 스터디 22일차 [마지막] 목차 1. 동적 계획법 실전 문제 2. 알고리즘 스터디를 마치면서 출처 Do it! 알고리즘 코딩테스트 with Python 1. 동적 계획법 실전 문제 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 먼저 주어진 조건은 다음과 같다. (이친 수 = 0과 1로만 이루어진 수) 1) 이친수는 0으로 시작하지 않는다. 2) 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 동적계획법에서 점화식을.. 알고리즘 스터디 21일차 드디어 왔다 극악무도한 동적 계획법 녀석! 목차 1. 동적 계획법 핵심이론 2. 동적 계획법 실전 문제 출처 Do it! 알고리즘 코딩테스트 with Python 1. 동적 계획법 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결 동적 계획법의 원리와 구현 방식 1) 큰 문제를 작은 문제로 나눌 수 있어야 한다. 2) 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다. 3) 모든 작은 문제들은 한 번만 계산해 DP테이블에 저장하며 추후 재사용할 때는 이 DP테이블을 이용한다. (=메모이제이션 기법) 4) 동적 계획법은 톱-다운 방식과 바텀-업 방식으로 구현할 수 있다. 피보나치 수열을 통해 이해해보자 (D[N] = D[N-1] + D[N-2] 의 점화.. 알고리즘 스터디 20일차 목차 1. 조합 핵심 이론 2. 조합 실전 문제 출처 Do it! 알고리즘 코딩테스트 with Python 1. 조합 핵심 이론 조합 점화식은 DP(동적계획법)을 이용하는데 중요하다. 문제를 접근할 때 모든 부분 문제가 해결된 상황이라고 가정하고 지금 문제를 생각해야 한다. 무슨말이냐면 예를들어 5개중에 3개를 선택해야하는 조합문제에서 (데이터 1 2 3 4 5) 5를 선택해야 하는 경우의 수를 구한다. 단, 이때 나머지 데이터 1 2 3 4 에 대한 문제는 해결된 상황이라고 가정한다. 그럼 5를 선택하는경우와 선택하지 않는 경우로 나눌수 있고 두 경우는 각각 [이미 4개중 2개를 선택한경우]와 [이미 4개중 3개를 선택한경우]이다. 위의 내용을 점화식으로 나타내면 다음과 같다. D[5][3] = D[4.. 알고리즘 스터디 19일차 목차 1. 최소 공통 조상 (LCA) 2. LCA 응용 - 빠르게 구하기 출처 Do it! 알고리즘 코딩테스트 with Python 1. 최소 공통 조상 (LCA) 트리 그래프에서 임의의 두 노드를 선택했을 때 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할 때 처음 공통으로 만나게 되는 부모 노드 일반적인 최소 공통 조상 구하기 : 트리의 높이가 크지 않을 때 (시간제한의 제약이 없을 때) 2. LCA 응용 - 빠르게 구하기 일반적인 LCA는 한칸씩 노드를 올려가면서 확인했지만 빠르게 구하기는 2^k 씩 올라가 비교한다. 따라서 기존에 자신의 부모노드만 저장해 높던 방식에서 2^k번째 위치의 부모 노드까지 저장. 부모 노드 배열의 정의 : k[K][N] = N번 노드의 2^k 번째 .. 알고리즘 스터디 18일차 목차 1. 세그먼트 트리 출처 Do it! 알고리즘 코딩테스트 with Python 1. 세그먼트 트리 1. 트리 초기화하기 2² >= N을 만족하는 k의 최솟값을 구한 후 2² x2를 트리 배열의 크기로 정의 (문제를 풀면 더 쉽게 이해, 처음 리프노드를 해당 조건에 만족하게 만들어 놔야 합하면서 위로 올라갔을 때 노드가 부족하지 않음) 리프노드만 원본 배열이고 그 위는 전부 합배열(자식노드의 두 수를 합한 값 저장) 2. 질의값 구하기 주어진 질의 인덱스를 세그먼트 트리의 리프 노드에 해당하는 인덱스로 변경 3. 데이터 업데이트 하기 세그먼트 트리는 강의에서 강조한 것 처럼 코딩 테스트 문제를 풀면 많이 나오던데 이번에 공부를 해서 좋다. 문제를 풀때 트리는 크게 어렵단 생각을 못했지만 시간이 오래 .. 알고리즘 스터디 17일차 목차 1. 이진 트리 출처 Do it! 알고리즘 코딩테스트 with Python 1. 이진 트리 각 노드의 자식 노드(차수)의 개수가 2 이하로 구성된 트리 전 게시글의 트리 유형 2가지 중 일차원 배열 표현 에 해당함 (=>인덱스트리,LCA) 자식노드의 (인덱스 // 2) 해서 나오는 값이 부모 노드의 인덱스 이다. 위와 같은 인덱스 연산 방식은 세그먼트 트리와 LCA에서 기본이 되는 연산이다. 최근에 이진 트리 문제를 풀었는데 위의 밑줄친 연산과 배열 표현을 몰라서 직접 노가다로 했다. 알고보니 간단하고 이진 트리 문제에 대한 자신감이 생긴다. 오늘은 개념만 공부하고 짧게 끝나지만 내일 실전 문제를 푸는것이 기대된다. 알고리즘 스터디 16일차 목차 1. 트리 알아보기 2. [트리 알아보기 실전 문제] 출처 Do it! 알고리즘 코딩테스트 with Python 1. 트리 알아보기 노드와 에지로 연결된 그래프의 특수한 형태 순환 구조를 지니고 있지 않고, 1개의 루트 노드가 존재 루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖는다. 트리의 부분 트리 역시 트리의 모든 특징을 따름 트리에서 임의의 두 노드를 이어주는 경로는 유일 노드 : 데이터의 index와 value를 표현하는 요소 에지 : 노드와 노드의 연결 관계를 나타내는 선 루트 노드 : 트리에서 가장 상위에 존재하는 노드 부모 노드 : 두 노드 사이의 관계에서 상위 노드에 해당하는 노드 자식 노드 : 두 노드 사이의 관계에서 하위 노드에 해당하는 노드 리프 노드 : 트리에서 가장 하.. 알고리즘 스터디 15일차 목차 1. 최소 신장 트리 (MST) 2. [최소 신장 트리 실전 문제] 출처 Do it! 알고리즘 코딩테스트 with Python 1. 최소 신장 트리 (MST) 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리 사용 알고리즘 : 크루스칼, 프림 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다. 따라서 N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1개다. 2. [최소 신장 트리 실전 문제] https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 .. 이전 1 2 3 다음
