코딩 테스트/개념34 CCW CCW (counter-clockwise) 평면상의 3개의 점과 관련된 점들의 위치관계를 파악하는 알고리즘(= 벡터의 외적) 2024. 8. 31. 동적 계획법 동적 계획법 dynamic programming 복잡한 문제를 여러개의 간단한 문제로 분리하여 부분의 문제들을 해결하여 최종적으로 복잡한 문제의 답을 구하는 방법 구현 방법1. 큰 문제를 작은 문제로 나눌 수 있어야 함2. 작은 문제들이 반복해서 나타나고 사용되며, 이 작은 문제들의 결과값은 항상 같아야 함3. 모든 작은 문제들을 한 번만 계산해 dp테이블에 정리(추후 재사용시 dp 테이블 이용: "memorization")4. 동적 계획법은 top-down 방식과 bottom-up 방식이 있다. 2024. 8. 25. 조합 조합 combination 동적 계획법 순열, 조합을 코드화하지 않고 점화식을 이용조합의 점화식 만드는 방법1. 특정 문제 가정하기2. 모든 부분 문제가 해결된 상황이라고 가정하고 지금 문제 생각하기3. 특정 문제 해결을 바탕으로 일반 점화식 도출하기 2024. 8. 24. 최소 공통 조상 최소 공통 조상 LCA (Lowest Common Ancestor) 임의의 두 노드를 선택했을 때, 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모노드 탐색 시 처음 공통으로 만나게 되는 부모노드 - BFS, DFS 사용- 선택된 두 노드의 깊이가 다른 경우, 더 깊은 노드의 노드를 부모 노드로 1개씩 올리면서 같은 길이로 맞춤(이때 두 노드가 같으면 탐색 종료)최소 공통 조상 빠르게 구하기 서로 깊이를 맞춰주거나 같아지는 노드를 찾을 때(2**k) 씩 올라가 비교하느 방식 -> (2**k)번쨰 위치의 부모 노드까지 저장해야 함 1. 부모 노드 저장 리스트 만들기정의: P[k][n] = n번 노드의 (2**k)번쨰 부모 노드 번호점화식: P[k][n] = P[k-1]P[[k-1][n]]- n의 (2.. 2024. 8. 18. 세그먼트 트리 세그먼트 트리 주어진 데이터의 구간 합, 데이터 업데이트를 빠르게 하기 위해 고안- 구간 합 구하기- 최대, 최소 구하기과정 - 토리 초기화 하기1. 리프 노드의 개수가 데이터의 개수(n) 이상이 되도록 트리 리스트 만들기(2**k) >= n 을 만족하는 k의 최소값을 구한 후(2**k) * 2 를 트리 리스트의 크기로 정의 2. 리프 노드에 원본 데이터 입력하기리프 노드의 시작 위치를 트리 리스트의 인덱스로 구함((2**k)를 시작 인덱스로 취함) 3. 1 ~ (2**k)-1 구간 채우기 (by. 질의)> 구간 합: A[n] = A[2n] + A[2n+1]> 최대: A[n] = max(A[2n], A[2n+1])> 최소: A[n] = min(A[2n], A[2n+1])의 방식으로 앞 리스트 채우기 - .. 2024. 8. 17. 이진트리 이진트리 binary tree 각 노드의 자식 노드(차수)의 개수가 2개 이하로 구성되어 있는 트리 - 평향 이진 트리노드들이 한쪽으로 편향되어 생성된 이진 트리- 포화 이진 트리트리의 높이가 모두 일정하며, 리프 노트가 꽉 찬 이진 트리- 완전 이진 트리마지막 level을 제외하고 완전하게 노드들이 채워지고, 마지막 level은 왼쪽부터 채워진 트리트리의 노드와 리스트의 인덱스 사이 상관관계이동 목표 노드인덱스 연산제약 조건 (n=노드개수)루트 노드Index=1 부모 노드Index= index/2현재 루트노드 아님왼쪽 자식 노드Index= index*2Index*2오른쪽 자식 노드Index= index*2+1Index*2+1 2024. 8. 11. 이전 1 2 3 4 ··· 6 다음 728x90
