백준 | 그래프 순회 - 24445번. 너비 우선 탐색 2 풀이
24445번. 너비 우선 탐색 2 문제 오늘도 서준이는 너비 우선 탐색(BFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 너비 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자. 너비 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 내림차순으로 방문한다. bfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점 for each v ∈ V - {R} visited[v]
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 3. 22.
백준 | 그래프 순회 - 24444번. 너비 우선 탐색 1 풀이
24444번. 너비 우선 탐색 1 문제 오늘도 서준이는 너비 우선 탐색(BFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 너비 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자. 너비 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다. bfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점 for each v ∈ V - {R} visited[v]
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 3. 22.
백준 | 그래프 순회 - 24480번. 깊이 우선 탐색 2 풀이
24480번. 깊이 우선 탐색 2 문제 오늘도 서준이는 깊이 우선 탐색(DFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 깊이 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자. 깊이 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 ’내림차순’으로 방문한다. dfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점 visited[R]
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 3. 22.
백준 | 그래프 순회- 24479번. 깊이 우선 탐색 1 풀이
24479번. 깊이 우선 탐색 1 문제 오늘도 서준이는 깊이 우선 탐색(DFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 깊이 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자. 깊이 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 ’**오름차순’**으로 방문한다. dfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점 visited[R]
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 3. 22.
백준 | 그래프 순회 - 1260번. DFS와 BFS 풀이
1260번. DFS와 BFS 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 3. 22.
그래프 관련 정리 -(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.
백준 | 정렬 섹션 - 2751번. 수 정렬하기 2
2751번. 수 정렬하기 2 첫 시도는 Arrays.sort() 사용했는데 시간 초과가 떴다. 이 문제는 O(n)에 가까운 정렬 알고리즘을 사용해야 한다. 첫 시도 import java.util.Arrays; import java.util.Scanner; /* 2751번. 수 정렬하기 2 * */ public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Main T = new Main(); Scanner kb = new Scanner(System.in); int n =kb.nextInt(); int[] arr = new int[n]; for(int i=0; i
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 3. 20.
백준 | 정렬 섹션 - 2787번. 대푯값 2, 1427번. 소트인사이드
2787번. 대푯값 2 입력 첫째 줄부터 다섯 번째 줄까지 한 줄에 하나씩 자연수가 주어진다. 주어지는 자연수는 100 보다 작은 10의 배수이다. 출력 첫째 줄에는 평균을 출력하고, 둘째 줄에는 중앙값을 출력한다. 평균과 중앙값은 모두 자연수이다. 내 코드 중앙값은 정렬된 수의 나열에서 중앙에 위치하는 수여야 함 Arrays.sort() 사용 import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; /* 백준 2587번. 대푯값 2 */ public class Main { //솔루션 함수 public ArrayList solution(int[] arr){ ArrayList answer = new ArrayList(); ..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 3. 20.
백준| 문자열 섹션 - 27866번. 문자와 문자열
27866번. 문자와 문자열 입력 첫째 줄에 영어 소문자와 대문자로만 이루어진 단어가 주어진다. 단어의 길이는 최대 1000$1,000$이다. 둘째 줄에 정수가 주어진다. 내 코드 import java.util.Scanner; /* 27866번. 문자와 문자열 * */ public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Main T = new Main(); Scanner kb = new Scanner(System.in); String str= kb.nextLine(); int n = kb.nextInt(); System.out.println(str.charAt(n-1)); } }
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 3. 20.
백준 - 트리 섹션 | 1991번. 트리 순회 (전위, 중위, 후위) DFS
23.03.20 문풀 1991번. 트리 순회 (전위, 중위, 후위) DFS 입력 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다. 출력 첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다. 내 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /* 19..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 3. 20.
섹션 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.
백준 | 이분 탐색 섹션 - 1920번. 수 찾기
23.03.17 문풀 1920번. 수 찾기 | Binary Search 이분탐색 사용 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer st; int N = Integer.parseInt(bf.readLine()); st = new StringTokeni..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 3. 17.
Sorting and Searching -(3) 이분 탐색
⬛ 탐색 = 검색 = Searching ‘탐색’ 은 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘 1) DFS : 깊이 우선 탐색 2) BFS : 너비 우선 탐색 3) Binary Seach : 이진 탐색(=이분 탐색) Binary Seach : 이진 탐색(=이분 탐색, 이진 검색) 데이터가 정렬된 상태에서 대상 데이터 중앙값 vs 찾는 키 값 비교하여‘결정 알고리즘’도 이분 검색을 기반으로 한다.**[과정] : 탐색 대상 데이터가 오름차순 정렬됐다고 가정**2) 중앙값 찾는 키값 : 왼쪽 영역에 대한 탐색 1) 중앙값 선택 시간 복잡도 O(log2n) : 검색 범위 ..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 3. 17.
백준 | 정렬 섹션 - 11651번. 좌표 정렬하기 2
11651번. 좌표 정렬하기 2 문제 2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. 출력 첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다. 내 코드 import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; /* 백준 11651번. 좌표 정렬 하기 2 문제..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 3. 16.