✔ 동적 계획법 동적 계획법이란? 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법 동적 계획법은 다음을 만족할 때 사용 큰 문제를 작은 문제로 나눌 수 있어야 함 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결과값은 항상 같아야 함 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용함 (메모이제이션 기법) 톱-다운 방식과 바텀-업 방식으로 구현할 수 있어야 함 피보나치 수열이란? 각 항이 바로 앞의 두 항을 이루어진 수열 피보나치 수열로 동적 계획법 이해하기 동적 계획법으로 풀 수 있는지 확인하기 6번째 피보나치 수열은 5번째 피보나치 수열과 4번째 피보나치 수열의 합 즉..
✔ 이항 계수 1 [백준 11050] 문제 분석하기 조합에서 가장 기본이되는 문제이므로 일반 점화식을 이용하여 문제를 해결 손으로 풀어보기 N과 K의 값을 입력받고 DP 배열을 선언 D[N + 1][N + 1] DP 배열의 값을 초기화 i개 중 1개를 뽑는 경우의 수인 D[i][1] = i i개 중 0개를 뽑는 경우의 수인 D[i][0] = 1 i개 중 i개를 뽑는 경우의 수인 D[i][i] = 1 점화식으로 DP 배열의 값을 채움 D[i][j] = D[i - 1][j] + D[i - 1][j - 1] D[N][K]의 값을 출력함 슈도코드 작성하기 N(총 개수), K(선택 수) D(DP 배열) for(i -> N만큼 반복하기) { D 배열 초기화하기 D[i][1] = i D[i][0] = 1 D[i][i..
✔ 조합 조합이란? n개의 숫자에서 r개를 뽑는 경우의 수 nCr로 표현 nCr = n! / (n - r)! * r! (이때, r!는 순서가 다른 경우의 수를 제거하여 같은 경우로 취급하기 위한 것) 순열이란? n개의 숫자 중 r개를 뽑아 순서를 고려해 나열할 경우의 수 nPr로 표현 nPr = n! / (n - r)! 조합의 점화식 특정 문제를 가정하기 5개의 데이터에서 3개를 선택하는 조합의 경우의 수를 푸는 문제로 가정 모든 부분 문제가 해결된 상황이라고 가정하고 지금 문제 생각하기 먼저 5개의 데이터 중 4개를 이미 선택이 완료된 데이터라고 가정 마지막 데이터의 선택 여부에 따른 경우의 수를 계산 만약 마지막 데이터를 포함해 총 3개의 데이터를 선택하려면 선택이 완료됐다고 가정한 4개의 데이터에서..
✔ 최소 공통 조상 최소 공통 조상이란? 트리 그래프에서 임의의 두 노드를 선택했을 때 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할 때 처음 공통으로 만나게 되는 부모 노드 일반적인 최소 공통 조상 찾기와 최소 공통 조상 빠르게 찾기가 존재 트리의 높이가 크지 않을 때는 일반적인 최소 공통 조상 찾기 사용 (1개씩 올라가기) 트리의 높이가 커질 경우, 시간 제약 문제가 직면할 수 있으므로 최소 공통 조상 빠르게 찾기 사용 (2^K씩 올라가기) 일반적인 최소 공통 조상 구하기 부모 노드와 깊이 저장 배열 만들기 루트 노드에서 탐색을 시작해 각 노드의 부모 노드와 깊이를 저장함 이때 탐색은 DFS 또는 BFS를 이용 선택된 두 노드의 깊이가 다를 경우, 더 깊은 노드의 노드를 부모 노..
✔ 세그먼트 트리 세그먼트 트리란? 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조의 형태 더 큰 범위는 인덱스 트리라고 불림 코딩 테스트에서 구간 합만 수행할 경우 합 배열과 구간 합 사용, 구간 합과 데이터 업데이트를 둘 다 수행할 경우 세그먼트 트리 사용 세그먼트 트리의 종류는 구간 합, 최대 구하기, 최소 구하기로 나누어짐 구현 단계는 트리 초기화하기, 질의값 구하기 (구간 합, 최대, 최소), 데이터 업데이트하기로 나누어짐 세그먼트 트리 과정 트리 초기화하기 리프 노드의 개수가 데이터의 개수 이상이 되도록 트리 배열을 만듦 2^k ≥ N을 만족하는 k의 최솟값을 구한 후 2^k * 2를 트리 배열의 크기로 정의 리프 노드에 원본 데이터를 입력 리프 노드의 시작 위치를 트리 배..
✔ 이진 트리 이진 트리란? 각 노드의 자식 노드의 개수가 2 이하로 구성돼 있는 트리 이진 트리의 종류 편향 이진 트리 : 노드들이 한 쪽으로 편향돼 생성된 이진 트리 포화 이진 트리 : 트리의 높이가 모두 일정하며 리프 노드가 꽉찬 이진 트리 완전 이진 트리 : 마지막 레벨을 제외하고 완전하게 노드들이 채워져 있고, 마지막 레벨은 왼쪽부터 채워진 트리 데이터를 트리 자료구조에 저장할 때 편향 이진 트리의 형태로 저장하면 탐색 속도가 조하되고 공간이 많이 낭비 일반적으로 코딩 테스트에서 데이터를 트리에 담는다고 하면 완전 이진 트리 형태를 사용 이진 트리의 순차 표현 트리 자료 형태는 배열 이진 트리는 1차원 배열의 형태로 표현할 수 있음 트리의 노드와 배열의 인덱스 사이 상관 관계 루트 노드 : in..
✔ 트라이 트라이란? 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조 단어들을 사전의 형태로 생성한 후 트리의 부모 자식 노드 관계를 이용해 검색을 수행 문자 종류의 개수인 N에 따라 N진 트리가 결정됨 루트 노드는 항상 빈 문자열을 뜻하는 공백 상태를 유지 트라이 과정 루트 노드는 공백을 유지하고 첫 번째 단어의 각 알파벳에 해당하는 노드를 생성 두 번째 단어를 삽입할 때는 루트 노드에서부터 검색을 수행 검색 노드가 공백 상태이면 신규 노드를 생성하고, 아니면 이동
✔ 트리 트리란? 노드와 엣지로 연결된 그래프의 특수한 형태 그래프의 형태이므로 그래프의 표현으로도 트리를 표현할 수 있음 순환 구조를 지니고 있지 않고, 1개의 루트 노드가 존재함 루트 노드를 제외한 노드는 단 1개의 부모 노드를 가짐 트리에서 임의의 두 개의 노드를 연결하는 경로는 유일 트리의 부분 트리 역시 트리의 모든 특징을 따름 트리의 구성 요소 노드 : 데이터의 index와 value를 표현하는 요소 엣지 : 노드와 노드의 연결 관계를 나타내는 선 루트 노드 : 트리에서 가장 상위에 존재하는 노드 부모 노드 : 두 노드 사이의 관계에서 상위 노드에 해당하는 노드 자식 노드 : 두 노드 사이의 관계에서 하위 노드에 해당하는 노드 리프 노드 : 트리에서 가장 하위에 존재하는 노드 (자식 노드가 없..
