코테 | 그래프 섹션 - 다익스트라, 위상정렬 문풀
🟩 4번. 방향 바꾸기 4방향으로 갈수 있기 때문에 cost[][] 2차원 배열 생성하여 최대한 방향 적게 바꾸면서 갈 수 있는 방식 고안 PriorityQueue에 좌표 담아가면서 가중치 적은 거 우선 정렬 int dir 변수가 순서대로 dx, dy 순회하면서 방향 안바꾼 상태로 더 적은 값 갱신 가능하면 갱신 방향 바꾼 상태로 더 적은 값 갱신 가능하면 갱신 정답 출력 package to_0822_6; //다익스트라 - 방향 바꾸기 RE 풀이 import java.util.*; class Solution { static int N, M; static int[][] cost; static PriorityQueue pQ; //4방향 static int[] dx = {0, 0, 1, -1}; static ..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 8. 22.
코테 | 그래프 섹션 - 다익스트라 문풀
⬛ 그래프 알고리즘 🟩 1번. 최소 비행료 문제 처음에는 one-to-all 단순히 다익스트라로 접근하는 문제인 줄 알았는데, 문제 조건에 있는 정해진 ‘환승 횟수’로 제한되어 있기 때문에 레벨 탐색을 해야 한다. 다익스트라는 우선순위큐로 무조건 최소비용을 구하는 게 단순 목적인데, 여기서 레벨탐색으로 풀어야 각 레벨(거쳐갈) 당 최소 비용이 구해지기 때문에 주의 ditance[c_v]가 아닌, c_val 값으로 거리 처리 해야 답이 나온다 왜지 ? //직전 Q에서 꺼낸 값 c_val 으로 접근해야 한다. for문을 돌면서 내부에서 nx_val 값을 업데이트 하는 중이라 distance[c_v]로만 접근하게 된다면 직전에 뽑아놨던 c_val 값이 아니라 새로 갱신된 distance[c_v]로 접근하게 되..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 8. 21.
코테 | 강의 - 너비 우선 탐색 - BFS 섹션 - (2)
🟩 4번. 미로의 최단거리 통로 | BFS 레벨 탐색 문제이다. 출발지점 (0, 0)에서 도착점 (6,6) 까지 갈 건데 갈 때마다 lv++처리하여 dist 배열에 해당 방문한 lv들을 담아가며 처리하면 된다. 4방향 탐색할 때 변수 주의해서 사용할 것 package to_0818_2; //미로의 최단거리 통로 import java.util.*; class Solution { static int[][] dist;//거리용 //4방향 static int[] dx = {0, 0, 1, -1}; static int[] dy = {1, -1, 0, 0}; public int solution(int[][] board){ //초기화 dist = new int[7][7]; Queue Q = new LinkedList..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 8. 18.
코테 | 강의 - 너비 우선 탐색 - BFS 섹션 - (1)
⬛ 너비 우선 탐색 | BFS 🟩 1번. 타일 점프 | BFS 풀이 이 문제는 레벨 탐색 문제이다. 각 레벨에서 방문 가능한 정점들을 큐에 담아서 차례로 방문하는 방식으로 인접 정점 우선으로 처리한다. Q에는 각 레벨별로 닿을 수 있는 정점들이 존재할 것이므로 for문으로 그 정점들을 순회한다. 해당 정점 x에 대하여 다시 for 문을 돌면서 x가 가진 최대 점프 횟수까지를 차례로 순회한다. nx 정점이 우리가 찾는 도착지 직전값이면 return lv++ 하여 리턴하면 되고 nx 정점이 아직 n보다 작으면서 방문한 적 없을 경우에는 방문 처리하면 된다. → 이 사이클에 대하여 lv++ 처리하면서 각 레벨에 대해 방문 가능한 인접 정점들을 우선 방문하면서 최소 점프횟수로 도착지에 갈 수 있는 방법을 찾는 ..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 8. 16.
코테 | 강의 - 깊이 우선 탐색 - DFS 섹션 - (2)
🟩 4번. 팰린드롬의 경우 수 풀이 Deque 자료구조를 사용하여 팰린드롬 만들 것 1) 애초에 입력으로 들어온 String 구성이 팰린드롬을 만들 수 있는 구성인지 확인 (1) 문자별 빈도수가 모두 짝수 → 팰린드롬 만들기 가능 (2) 문자별 빈도수가 홀수인 경우 → 홀수인 문자 1개만 있으면 가능, 1개 이상이면 불가능 2) HashMap 사용하여 각 문자별 빈도수 체크 3) map을 keySet()으로 순회하면서 해당 키의 빈도수가 홀수인 문자를 odd변수로 카운팅한다. 4) 만약 odd > 1 이면 빈 String 배열을 곧장 리턴해준다. (팰린드롬 못 만들기 때문) 5) odd가 1개 or 0개여서 팰린드롬이 가능하다면. DFS() 시작 6) DFS에서는 Deque를 활용하여 각 깊이에서 순회할..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 8. 14.
코테 | 강의 - 깊이 우선 탐색 - DFS 섹션 - (1)
⬛ 깊이 우선 탐색 | DFS 🟩 1번. 가장 가까운 큰 수 풀이 일단 입력된 n의 구성을 잘라서 ArrayLIst에 담아주고 오름차순 정렬한다. 오름차순 정렬해두어야 작은값부터 차례로 순회하기 때 import java.util.ArrayList; import java.util.Collections; /*가장 가까운 큰 수 */ class Solution { static int answer, target;//최초 숫자 담기 static ArrayList num; static boolean[] visited;//방문용 static boolean flag; static int len; //길이 //DFS static void DFS(int lv, int number) { if(flag == true) ret..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 8. 9.
섹션 3. 코딩테스트 [실전편] - 11. 동적 계획법
섹션 3. 코딩테스트 [실전편] - 11. 동적 계획법 ⬛ 11. 동적 계획법 ⬛ 11-1. 동적 계획법 DP 🟦 동적 계획법 복잡한 문제를 여러 개의 단순한 문제로 분리하여, 부분 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방식 🟧 동적계획법 원리와 구현 1) 큰 문제를 작은 문제로 나눌 수 있어야 한다. 2) 작은 문제들이 반복되어 나타나고, 이 작은 문제들의 결과값이 항상 같아야 한다. 3) 메모이제이션 기법을 사용 : 모든 작은 문제들을 한 번만 계산하여 미리 DP 테이블에 저장해놓고, 추후 재사용 시 DP 테이블을 이용하는 방식 4) 동적 계획법 구현 방식 2가지 : (1) 톱 다운 방식 (2) 바텀 업 방식 🟦 예시 : 피보나치 수열 문제 피보나치 수열은 규칙성이 존재하는데 그..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 7. 11.
![섹션 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.