코테 | 그래프 섹션 - 다익스트라, 위상정렬 문풀
🟩 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.
![코테 | 그래프 섹션 - 다익스트라 문풀](http://i1.daumcdn.net/thumb/C120x120/?fname=https://blog.kakaocdn.net/dn/mN4zP/btsrCS9xKLd/jzrmdix0quG2zaVOlRnBIk/img.png)
코테 | 그래프 섹션 - 다익스트라 문풀
⬛ 그래프 알고리즘 🟩 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)](http://i1.daumcdn.net/thumb/C120x120/?fname=https://blog.kakaocdn.net/dn/dElZyI/btsq1boqpwa/2EdeqDhZMami0QCHWBqhY0/img.png)
코테 | 강의 - 깊이 우선 탐색 - 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)](http://i1.daumcdn.net/thumb/C120x120/?fname=https://blog.kakaocdn.net/dn/clP5Du/btsqFrYg88k/5nCGJJpwT3TBDStX6MYTk1/img.png)
코테 | 강의 - 깊이 우선 탐색 - 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.