![섹션 3. 코딩테스트 [실전편] - 10. 조합](http://i1.daumcdn.net/thumb/C120x120/?fname=https://blog.kakaocdn.net/dn/cig3Td/btsm2Hq97et/cmfyyxQdC9yX2Xx2CraJaK/img.jpg)
섹션 3. 코딩테스트 [실전편] - 10. 조합
섹션 3. 코딩테스트 [실전편] - 10. 조합 ⬛ 10. 조합 동적 계획법을 이해하는 기초가 됨 조합 점화식 도출 방법을 제대로 이해하자. ⬛ 10-1. 조합 알아보기 🟦 조합 Combination | nCr 조합 : n개의 숫자에서 r개를 뽑는 경우의 수 cf. 순열 : n개의 숫자에서 r개를 뽑고, 그 순서를 나열 일반적으로 조합을 구현할 때는 점화식을 이용 🟧 조합 구현하는 방식 1. 특정 문제를 가정하기 예를 들어. 5개의 데이터 중 3개를 선택하는 경우의 수를 구한다고 가정해보자. 2. 모든 부분 문제가 해결됐다고 가정하고, 지금 문제만 생각하기 5개 중에서 4개의 데이터들의 선택 여부를 모두 고려했다고 생각하고. 지금 시점은 가장 마지막 (5번째) 데이터의 선택 여부를 고려하는 중이라고 생각..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 7. 10.
섹션 3. 코딩테스트 [실전편] - 09. 트리 - (3) 세그먼트 트리
⬛ 09-4. 세그먼트 트리 🟦 세그먼트 트리 주어진 데이터들의 **‘구간 합’과 ‘데이터 업데이트’**를 빠르게 수행하기 위해 고안해낸 자료구조 세그먼트 트리의 종류 : 1) 구간합, 2) 최대/최소 구하기 구현 단계 : (1) 트리 초기화 하기 (2) 질의값(요구사항) 구하기 (3) 데이터 업데이트 🟧 세그먼트 트리의 구현 단계 1) 트리 초기화 하기 (1) 리프 노드의 개수가 데이터 개수 N 이상이 되도록 2^k ≥ N을 만족하는 k의 최솟값 구한 뒤 2^k * 2를 트리 배열의 크기로 정의 ex) 샘플 데이터 = {5, 8, 4, 3, 7, 2, 1, 6} : N = 8 2^3 = 8 따라서 배열크기는 2^3 X 2 = 16 크기로 정의 (2) 리프 노드에 원본 데이터를 입력한다. 이때 리프 노드..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 7. 10.
섹션 3. 코딩테스트 [실전편] - 09. 트리 - (2) 이진 트리
⬛ 09-3. 이진 트리 🟦 이진 트리 (binary tree) 각 노드와 자식 노드의 개수(차수)가 2 이하로 구성되어 있는 트리 종류 : 편향 이진 트리, 완전 이진 트리, 포화 이진 트리 보통 1차원 배열의 형태로 표현 🟧 트리의 노드와 배열 인덱스 간 상관 관계 루트 노드 : index = 1; 부모 노드 : index = index / 2;// 현 인덱스 상위로 이동 왼쪽 자식 노드 : index = index*2; 오른쪽 자식 노드 : index = index*2 + 1; 🟧 트리의 순회 전위 순회 : U L R 중위 순회 : L U R 후위 순회 : L R U 🟦 백준 1991번. 트리 순회하기 문제 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorde..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 7. 7.
섹션 3. 코딩테스트 [실전편] - 09. 트리 - (1) 트리, 트라이
섹션 3. 코딩테스트 [실전편] - 09. 트리 🏓 선형 vs 비선형 자료구조 1) 선형 자료구조 : 현재 자료와 뒤 자료가 1:1 관계 2) 비선형 자료구조 : 현재 자료와 뒤 자료가 1:n 관계 ⬛ 09. 트리 ⬛ 09-1. 트리 사이클 X. 1개의 루트 노드만 가지고 있는 원소들 간의 1대 n 관계를 갖는 비선형 자료구조 상위 원소 → 하위 원소로 확장되는 구조 사이클X, 간선 N-1개 연결 그래프 🟧 트리의 구성요소 루트 노드 : 트리 가장 상위의 노드 부모 노드 : 두 노드 사이 관계에서 상위 노드 자식 노드 : 두 노드 사이 관계에서 하위 노드 리프 (단말) 노드 : 트리 가장 하위의 말단에서 자식 없는 노드 서브 트리 : 전체 트리에 속해있는 작은 하위 트리 각각의 노드는 자식 노드의 수만큼..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 7. 7.
섹션 3. 코딩테스트 [실전편] - 08. 그래프 - (6) 최소 비용 신장 트리
⬛ 08-7. 최소 신장 트리 🟦 신장 트리 n개 정점. 무방향 그래프에서 (사이클 없이) 간선 n-1 개로 이루어진 부분 그래프 🟦 최소 비용 신장 트리 정점 n개, 간선 n-1개. 사이클 X . 연결 그래프인 신장 트리의 조건을 만족하면서 총 간선의 가중치의 합이 최소인 트리 그래프의 모든 노드들을 연결하는 부분 그래프 중 가중치 합이 최소인 트리를 의미 🟧 1) 크루스칼 알고리즘 - (I) 가중치 ‘높은’ 간선 제거하여 최소비용 만듬 (1) 그래프의 모든 간선들 가중치 내림차순 정렬 (2) 사이클 X, 단절 X 가장 큰 간선 제거 (3) 간선 n-1개 남을 때까지 반복 후 종료 🟧 1) 크루스칼 알고리즘 - (II) 가중치 ‘낮은’ 간선 삽입하며 최소비용 만듬 (1) 그래프의 모든 간선들 가중치 오..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 7. 6.
섹션 3. 코딩테스트 [실전편] - 08. 그래프 - (5) 플로이드 워샬
🔎 벨만-포드 알고리즘이란? 그래프 최단 거리 구하는 알고리즘 1. 다익스트라(Dijkstra) : 특정 한 정점 -> 다른 모든 정점의 최단 거리 2. 벨만-포드(Bellman-Frod) : 특정 한 정점 -> 다른 모든 정점의 최단 거리 3. 플로이드-와샬(Floyd-Wrasahll) : 모든 정점들 간의 최단 거리 ⬛ 08-6. 플로이드-워셜 🟦 플로이드-워셜 알고리즘 플로이드-워셜 : 모든 노드 간에 최단 경로 탐색 알고리즘 음수 가중치 엣지 존재해도 수행 가능 DP 동적계획법 원리 이용하여 접근 전체 경로의 최단 경로는 부분 경로의 최단경로 조합이다. //점화식 // s -> E까지의 최단 경로 vs s-> k, k->e 를 껴서 가는 경로 // 중 작은 값으로 업데이트한다. D[S][E] = ..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 7. 5.
섹션 3. 코딩테스트 [실전편] - 08. 그래프 - (4) 벨만-포드
🔎 벨만-포드 알고리즘이란? 그래프 최단 거리 구하는 알고리즘 1. 다익스트라(Dijkstra) : 특정 한 정점 -> 다른 모든 정점의 최단 거리 2. 벨만-포드(Bellman-Frod) : 특정 한 정점 -> 다른 모든 정점의 최단 거리 3. 플로이드-와셜(Floyd-Wrasahll) : 모든 정점들 간의 최단 거리 ⬛ 08-5. 벨만-포드 알고리즘 🟦 벨만- 포드 알고리즘 벨만-포드 : 특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색 알고리즘 cf. 다익스트라와 다른 점 : 음수 가중치 엣지 있어도 수행 가능 ! 보통 음수 사이클 존재 여부 판별하는 문제가 多 출제 🟧 벨만-포드 핵심 이론 1) 에지 리스트로 그래프 구현 후, 최단 경로 배열 초기화 2) 모든 엣지 확인하며 정답 배열 업데..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 7. 5.
섹션 3. 코딩테스트 [실전편] - 08. 그래프 - (3) - 다익스트라
🔎다익스트라 알고리즘이란? 그래프 최단 거리 구하는 알고리즘 1. 다익스트라(Dijkstra) : 특정 한 정점 -> 다른 모든 정점의 최단 거리 2. 벨만-포드(Bellman-Frod) : 특정 한 정점 -> 다른 모든 정점의 최단 거리 3. 플로이드-와샬(Floyd-Wrasahll) : 모든 정점들 간의 최단 거리 ⬛ 08-4. 다익스트라 🟦 다익스트라 (one - to - All) 다익스트라 알고리즘 : 그래프에서 최단 거리 구하는 알고리즘 특정 노드에서 다른 노드들 간의 최단 거리를 구하는 탐색 알고리즘 엣지가 모두 양수 (cf. 벨만-포드의 경우 엣지 음수도 가능) 시간 복잡도 : O(ElogV) 🟧 다익스트라 알고리즘의 핵심 이론 1) 인접 리스트로 그래프 표현 2) 최단 거리 D[] 배열 초..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 7. 3.
섹션 3. 코딩테스트 [실전편] - 08. 그래프 - (2) -위상정렬
⬛ 08-3. 위상 정렬 🟦 위상 정렬 사이클이 없는 방향 그래프에서 노드 간의 순서 결정하는 알고리즘 사이클이 없어야 한다.(사이클 존재 시, 명확하게 순서 결정 불가능) 🟧 위상 정렬 수행 과정 1) 진입 차수가 0인 노드를 큐에 저장 2) 큐에서 데이터 poll() 후, 결과에 추가. 해당 노드가 가리키는 인접 정점의 진입차수 D[] 의 값 1씩 뺌 3) 감소한 상태의 진입 차수가 0인 경우 다시 Q에 add() 4) 큐가 빌때까지 1~3 반복 🟦 백준 2252번. 줄 세우기 문제 N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 6. 28.
![섹션 3. 코딩테스트 [실전편] - 08. 그래프 - (1) 이분 그래프, 유니온 파인드](http://i1.daumcdn.net/thumb/C120x120/?fname=https://blog.kakaocdn.net/dn/n1Bbt/btslmUfxOGN/by8oYHE3FxFQK9Nm2ZTRKk/img.png)
섹션 3. 코딩테스트 [실전편] - 08. 그래프 - (1) 이분 그래프, 유니온 파인드
섹션 3. 코딩테스트 [실전편] - 08. 그래프 ⬛ 08. 그래프 그래프는 노드와 엣지로 구성된 집합. 노드는 데이터 표현 단위, 에지는 노드를 연결 ⬛ 08-1. 그래프의 표현 그래프 구현 방식은 크게 3가지가 있다. 🟦 1. 에지 리스트 에지 중심으로 그래프 표현하는 방식이다. 🟧 1) 가중치 X 그래프 표현 배열의 행 2개로 출발노드, 도착노드 표현한다. 🟧 2) 가중치 O 그래프 표현 배열 행 3개로 출발노드 도착노드, 가중치 표현한다. 🟦 2. 인접 행렬 2차원 배열 이용하여 노드 중심으로 표현하는 방식이다. 다만, 에지 탐색 시, N번 접근해야 하므로 노드 개수에 비해서 에지가 적을 때는 공간 효율성 떨어진다. 🟧 1) 가중치 X 그래프 표현 i행 j열에 i → j 표현 🟧 2) 가중치 O ..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 6. 21.
섹션 2. 코딩테스트 - 07. 정수론 -(1) 소수, 오일러 피, 유클리드 호제법
섹션 2. 코딩테스트 - 07. 정수론 ⬛ 07. 정수론 정수론 : 수의 성질 탐구하고 공부하는 이론 분야 실제 코테에서는 모든 정수론 분야가 나오는 것은 아니므로, 가장 많이 등장하는 ‘소수 부분’과 ‘호제법’ 부분을 집중적으로 다뤄보자. ⬛ 07-1. 소수 구하기 🟦 소수 1과 자기 자신 외에 약수가 존재하지 않는 수 소수 판별 방식을 묻는 ‘소수 구하기 문제’ 종종 출제 🟦 대표적인 소수 판별 방식 | ‘에라토스테네스의 체’ 시간 복잡도 : O(N2) 이중 for문 사용하므로.. 🟧 에라토스테네스의 체 방식 구하고자 하는 소수 범위만큼의 1차원 배열[] 생성 for(2~N) : 현재 i의 숫자 선택 → (첫 수 제외) 현재 선택된 i의 배수를 배열 끝까지 탐색하면서 모두 지움 그 다음 지워지지 않은..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 6. 15.
섹션 2. 코딩테스트 - 06. 그리디 알고리즘
섹션 2. 코딩테스트 - 06. 그리디 ⬛ 06. 그리디 알고리즘 ⬛ 06-1. 그리디 알고리즘 🟦 그리디(Greedy) 알고리즘 현재 상태에서 볼 수 있는 최적해가 전체의 최적해라고 가정하며 근시안적으로 보는 알고리즘 전체를 보지 않고, 근시안적 선택(현 상황에서의 부분적 최적해)가 최종 문제의 최적해를 얻는 일이라고 가정하며 답을 찾아가는 알고리즘 항상 최적해를 보장하지는 못한다. 🟧 그리디 알고리즘 수행 과정 1) 해 선택 : 현재 상태의 부분적 최적해 선택 2) 적절성 검사 : 그 최적해가 전체 문제 제약 조건 벗어나지 않는지 검사 3) 해 검사 : 현재까지 선택한 해 집합들이 전체 문제 해결 가능한지 검사. 만약 전체 문제 해결 못한다면 다시 1)로 돌아가 이 과정을 반복 🟦 백준 11047번...
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 6. 14.