동적 계획 알고리즘 -(2)
동적 계획 알고리즘 -(2) 10-3. 최대 부분 증가수열 dy[i] 에 올 수 있는 값 = 자기 보다 앞에있는 애들 中 자기보다 작으면서 최댓값 갖는 애 찾고 +1 import java.util.Scanner; /* 10-3. 최대부분증가수열 LIS */ public class Main1 { static int[] dy; //솔루션 함수 static int solution(int [] arr) { int answer = 0; dy = new int[arr.length]; dy[0]=1; //최초값은 길이 1 answer = dy[0];//길이1 짜리 들어오는 것 대비 //dy[i]에 담을 길이 = 처음 ~ i 직전까지 앞배열 탐색 아며 //현재 arr[i]보다 값은 작으면서 길이 dy[]는 최대 갖는 ..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 4. 6.
동적 계획 알고리즘 -(1)
📍 섹션10. DP (동적 계획 알고리즘) 동적 계획 알고리즘 -(1) 🟪 동적 계획(DP) 알고리즘 문제를 부분 문제로 나누어서, 가장 작은 부분문제로부터 해를 구한 뒤, 부분해를 이용하여 점차 상위 문제의 최적해를 구한다. 10-1. 계단 오르기 -피보나치 수열과 유사하다. 앞의 두 계단 가짓 수 합이 세 번쨰 가짓 수 가 되기 때문 규칙성을 찾자 *** import java.util.Scanner; /* 10-1. 계단 오르기 */ public class Main3 { static int[] dy; //솔루션 public int solution(int n) { //앞의 두 계단 초기화 dy[1] = 1; dy[2] = 2; //피보나치처럼 가짓수 확장된다. for(int i=3; i
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 4. 3.
트리 관련 개념 정리
트리 관련 개념 정리 신장트리와 최소비용 신장 트리 🟦신장트리 : n개 정점 무방향 그래프에서 간선 n-1개로 이루어진 부분 그래프 정점 n개, 간선 n-1개, 사이클X, 연결그래프(단절X) 🟦최소비용 신장 트리 : 무방향 가중치 그래프에서 신장 트리 구성 간선의 가중치 합이 최소인 그래프 1) 크루스칼 알고리즘 (1) 가중치 높은 간선 제거하며 최소비용 만들기 (2) 가중치 낮은 간선 삽입하며 최소비용 만들기 2) 프림 알고리즘 (간선 정렬 X) 하나의 정점에서 시작하여 트리 확장해감 확장 정점들에 부속된 모든 간선들을 비교하며 가장 낮은 간선 연결 확장 🟪 최단 경로 🟦 최단 경로 (신장트리가 아닌) 가중치 그래프에서 정점u와 정점 v를 잇는 경로 중 가중치 합이 최소인 경로 1) 다익스트라 최단 경..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 4. 3.
그리디 알고리즘 섹션 - (2)
그리디 알고리즘 섹션 - (2) 🟪 PriorityQueue 우선순위 큐 일반적으로 스택은 LIFO 후입선출 구조를 갖고, 큐는 FIFO 선입선출 구조를 갖는다. 그 중에서도 우선순위 큐의 경우, 들어온 순서와는 상관없이 우선순위가 높은 요소를 먼저 처리하는 자료구조이다. 🟪 ‘자바’의 우선순위 큐 라이브러리 사용법 기본적으로 PriorityQueue를 생성하면 우선순위 낮은 순으로 객체가 생성되는데 , 그 역순으로 (우선순위 높은 순) 으로 생성하려면 생성 인자로 Collections.reverseOrder() 를 주면 된다. import java.util.PriorityQueue; //import //int형 priorityQueue 선언 (우선순위가 낮은 숫자 순) PriorityQueue prio..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 3. 31.
그리디 알고리즘 섹션 - (1)
📍 섹션9. Greedy 그리디 알고리즘 그리디 알고리즘 섹션 - (1) 🟪 그리디 알고리즘 현재 상태에서의 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘 매순간 최선의 선택지를 선택 단, 항상 최적의 해를 보장하지는 못한다. 9-1. 씨름 선수 🟪 객체 비교 | compareTo() 재정의 //A기준 오름차순 : this.A - 대상.A //A기준 내림차순 : 대상.A - this.A 1) 키 기준 내림차순 정렬된 상태에서, 2) 몸무게가 이전 max보다 작은 애가 나오면 (키 + 몸무게까지) 모두 미달인 것이므로 탈락임 3) 그러므로 max가 갱신될 때마다 선발생으로 카운팅 import java.util.ArrayList; import java.util.Collections; i..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 3. 30.
DFS, BFS 활용 섹션 -(5) | 복습
DFS, BFS 활용 섹션 -(5) | 복습 8-9. 조합 구하기 nCm | DFS 이해가 완벽히 안된 거 같아서 다시 풀었다. import java.util.Scanner; /* 8-9. 조합 구하기 nCm 조합 | DFS */ public class Main1 { static int[] combi; //조합 뽑은 애들 둘 배열 static int n, m; //DFS public void DFS(int L, int s) { //레벨 L, start 번호 s //즉, 각 L 의 단계에 combi[L]번째 수가 뽑혀야 하며 //중복없기 위해, s번호부터 시작해서 n까지 for문이 돌아야 함 if(L==m) { //m개 다 뽑아쓰니까 더 깊이 탐색 X for(int x : combi) System.out...
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 3. 29.
DFS, BFS 활용 섹션 -(4)
DFS, BFS 활용 섹션 -(4) 8-11. 미로의 최단거리 통로 (BFS) | RE import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; /* 8-11. 미로의 최단거리 통로 (BFS) RE 풀이 * */ class Point{ int x,y; Point(int x, int y){ this.x = x; this.y = y; } } public class Main1 { static int[][] board, dis; static int[] dx = {-1, 0, 1, 0}; static int[] dy = {0, 1, 0, -1}; //BFS public void BFS(int x, int y) { Queue Q =..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 3. 28.
DFS, BFS 활용 섹션 - (3)
DFS, BFS 활용 섹션 -(3) 8-8. 수열 추측하기 import java.util.Scanner; /*8-8. 수열 추측하기 | DFS *** 조금 어렵다. */ public class Main1 { static int[] b, p, ch; static int n, f; boolean flag = false; int[][] dy = new int[35][35]; //combi 조합 public int combi(int n, int r) { if(dy[n][r]>0) return dy[n][r]; if(n==r || r==0) return 1; else return dy[n][r] = combi(n-1, r-1)+ combi(n-1, r); } //dfs 함수 public void DFS(int L..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 3. 27.
DFS, BFS 활용 섹션 - (2)
DFS, BFS 활용 섹션 - (2) 8-5. 동전교환 | DFS DFS(L, sum) : 0개부터 시작해서 L개의 동전을 사용했을 때 sum이 문제의 m과 같아지는 경우, 더 작은 min(answer, L); 로 변경하면 된다. 동전의 종류는 arr[i]로 받을 건데, 각각의 DFS() 호출은 for문으로 arr[] 내부를 돌면서 각각의 L개 동전을 arr[i]의 동전 종류 사용한 후 sum 값을 보면서 뻗어나가면 된다. import java.util.Arrays; import java.util.Collections; import java.util.Scanner; /* 8-5. 동전교환 다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가?..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 3. 24.
DFS, BFS 활용 섹션 - (1)
📍 섹션8. DFS, BFS 활용 DFS, BFS 활용 섹션 - (1) 8-1. 합이 같은 부분집합 | DFS import java.util.Scanner; /* 8-1. 합이 같은 부분집합 (DFS) [입력] 첫 번째 줄에 자연수 N(1
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 3. 23.
그래프 관련 정리 -(1)
그래프 관련 정리 -(1) 그래프의 종류 ⬛ 1) 무방향 그래프 G = (V, E) 로 표시 ⬛ 2) 방향 그래프 G = 로 표시 ⬛ 3) 가중치 방향 그래프 그래프의 구현 ⬛ 1) 인접행렬 graph[a][b] 로 표현 ⬛ 2) 인접리스트 ArryList graph 로 표현각 정점에 연결된 정점들 정보를 ArrayList 하나에 표현하는데, 그 정점들을 모아 전체 그래프로 표현한 것 그래프의 순회 ⬛ 1) 깊이 우선 탐색 DFS ⬛ 2) 너비 우선 탐색 BFS 7-11. 경로 탐색 (인접 행렬) | DFS import java.util.Scanner; /* 7-12. 경로 탐색 (인접행렬) */ class Main1 { static int n, m, answer = 0; //입출력 변수 static i..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 3. 22.
DFS, BFS 개념 -(2)
DFS, BFS 개념 -(2) 7-6. 부분 집합 구하기 | DFS 전체 원소가 1~N까지인 집합의 부분집합 각 원소를 사용 O or 사용 X 각 2가지의 경우의 수 있다. /* 7-6. 부분집합 구하기 DFS */ public class Main1 { //집합 원소의 개수 static int n; //각 원소 부분집합 사용 여부 체크 배열 static int[] ch; //DFS 함수 public void DFS(int L) { if(L == n+1) { // 단말 노드까지 찍으면 종료 String tmp = ""; //전체 순회하면서 사용 체크된 원소만 String에 이어붙임 for(int i = 1; i0) System.out.println(tmp); }else { //각 원소에 대해서 재귀 호출 ..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 3. 21.
섹션 7. DFS, BFS 기초 섹션 - (2) DFS와 BFS
섹션 7. DFS, BFS 기초 섹션 - (2) 그래프의 순회, DFS 그래프 순회 ⬛ 1) 깊이 우선 순회 : DFS 한 정점에서 시작하여 깊이 탐색하다가 다시 직전(마지막 방문 정점)에 돌아와 [스택 사용] 깊이 탐색을 반복 ⬛ 2) 너비 우선 순회 : BFS 시작 정점에 대한 인접 정점들 모두를 차례로 방문하고, 다시 처음 방문했던 정점으로 되돌아와 [큐 사용] 너비 우선 탐색 반복 ◼️ 6번. 부분 집합 구하기 | DFS 🟦 문제 풀이 🟦 코드 /** * 부분집합 구하기 - DFS * @author MYLG * */ import java.util.*; class Main { static int n; static int[] ch; //DFS public void DFS(int L){ if(L==n+..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 3. 20.
섹션 7. DFS, BFS 기초 섹션 - (1) 재귀 함수와 DFS
재귀 함수 (Recursive Function) 특정 함수 내에서 자기 자신을 다시 호출하여 문제를 해결해나가는 함수 함수 내에서 자기 자신을 다시 호출하는 방식 [주의] 무한 루프에 빠지지 않도록 주의하며 작성할 것 ⬛ 스택 프레임 기반 재귀함수는 스택 프레임 DFS(n-1) 밑에 print 찍으면 다음과 같이 스택이 쌓이게 된다. ‘복귀 주소’ : DFS()의 함수내용을 전부 실행한 후 스택프레임이 사라지면서 자기가 호출되었던 주소로 복귀한다. ◼️ 1번. 재귀함수 (스택 프레임) | DFS 🟦 문제 풀이 N이 입력되면 DFS(N)을 호출한다. DFS()함수가 최초로 호출된 시점에서 N 부터 1씩 감소하면서 깊이 탐색을 한다. 만약 N값이 0이되면 return 해주는데, 반환 시점에서 출력해주면 차례..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 3. 20.
Sorting and Searching -(3) 이분 탐색
⬛ 탐색 = 검색 = Searching ‘탐색’ 은 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘 1) DFS : 깊이 우선 탐색 2) BFS : 너비 우선 탐색 3) Binary Seach : 이진 탐색(=이분 탐색) Binary Seach : 이진 탐색(=이분 탐색, 이진 검색) 데이터가 정렬된 상태에서 대상 데이터 중앙값 vs 찾는 키 값 비교하여‘결정 알고리즘’도 이분 검색을 기반으로 한다.**[과정] : 탐색 대상 데이터가 오름차순 정렬됐다고 가정**2) 중앙값 찾는 키값 : 왼쪽 영역에 대한 탐색 1) 중앙값 선택 시간 복잡도 O(log2n) : 검색 범위 ..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 3. 17.
Sorting and Searching -(2)
Sorting and Searching -(2) 6-3. 삽입 정렬 | 복습 import java.util.Scanner; /*6-3. 삽입 정렬| 복습*/ public class Main1 { public int[] solution(int n, int[] arr) { for(int i = 1; i=0; j--) { if(arr[j] > tmp) { //S집합 값을 U집합 쪽으로 밀기 arr[j+1] = arr[j]; }else break; //삽입 지점 찾았으면 break } //멈춘 지점에서 tmp 값도 세팅 arr[j+1] = tmp; } return arr; } public static void main(String[] args) { // TODO Auto-generated method stub ..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 3. 16.
Sorting and Searching -(1)
📍 섹션6. Sorting and Searching (정렬, 이분 검색과 결정 알고리즘) Sorting and Searching -(1) ⬛ 선택 정렬 | Selection Sorting 대상에서 가장 큰 or 작은 데이터 찾아 선택을 반복하며 정렬하는 방식 전체 원소들 중, 기준 위치(i)에 맞는 원소를, 남은 원소들 중에서 (j) 찾아 선택 후, 자리 맞교환 시간 복잡도 O(n2) 비효율적이라 사용 小 i번째 단계에서 i번째 자리 확정 n개 원소에 대해 n-1번 반복함 6-1. 선택 정렬 import java.util.ArrayList; import java.util.Scanner; /* 6-1. 선택 정렬 * N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요. * 정렬하는 ..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 3. 14.
Stack, Queue - (2)
Stack, Queue - (2) 5-5. 쇠막대기 | 스택 사용 1) 여는 괄호는 일단 push 2) 닫는 괄호 만나면 구분 a) 레이저인지: 바로 앞이 ( 여는 괄호일 때 stack.size() 만큼 answer에 누적 : 레이저 왼쪽 막대기가 잘려나간 부분이므로 b) 막대기 오른쪽인지 answer +1 ; //그래야 오른쪽 끝 막대기 부분(닫는 괄호 1개당) 잘림 처리 가능 import java.util.Scanner; import java.util.Stack; /* 5-5. 쇠막대기 [입력] 한 줄에 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 공백없이 주어진다. [출력] 잘려진 조각의 총 개수를 나타내는 정수를 한 줄에 출력한다. */ public class Main1 { //솔루션 함수 p..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 3. 13.
Stack, Queue - (1)
📍 섹션5.스택, 큐 (Stack, Queue) 자료구조 Stack, Queue - (1) 스택과 큐는 배열에서 발전된 형태의 자료구조 🟨스택 Stack 후입선출(LIFO : Last-In-First-Out) 삽입과 삭제 연산이 ‘한 쪽’에서만 일어난다 top ← 삽입과 삭제 일어날 위치 지칭 push : 데이터 삽입 연산 pop : 데이터 삭제 후 확인 연산 peek : top 데이터 단순 확인용 ⇒ 스택은 ‘DFS (깊이우선탐색)’ 과 백트랙킹 에서 多 사용 🟨큐 Queue 선입선출(FIFO : First-In-First-Out) 삽입과 삭제 연산 ‘양방향’에서 일어난다 먼저 들어온 데이터가 먼저 나감 rear ← 큐의 가장 끝 데이터 지칭 (데이터 삽입) front ← 큐의 가장 앞 데이터 지칭 (..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 3. 10.