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.