![섹션 7. DFS, BFS 기초 섹션 - (1) 재귀 함수와 DFS](http://i1.daumcdn.net/thumb/C120x120/?fname=https://blog.kakaocdn.net/dn/eAAwqv/btsA20XO7oQ/iGbRjw7kN9niCk4j1weOt1/img.png)
섹션 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.
HashMap, TreeSet - (2)
HashMap, TreeSet - (2) 4-3. [Re] 매출액의 종류 import java.util.ArrayList; import java.util.HashMap; import java.util.Scanner; /* 04-03. 매출액의 종류 Re [입력] 첫 줄에 N(5
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 3. 7.
HashMap, TreeSet - (1)
📍 섹션4.HashMap, TreeSet (해쉬, 정렬 지원 Set) HashMap, TreeSet - (1) HashMap (해쉬 맵) 이란? HashMap은 Key-Value가 1:1로 Mapping 되는 자료구조 Mapping으로 인해 삽입, 삭제, 검색이 평균적으로 O(1)인 자료구조 Key는 중복을 허용하지 않지만, Value는 중복을 허용한다. [관련 주요 메소드] //특정 key 존재 여부 확인 map.containsKey('A'); //중복 key 없게 각 키에 해당하는 값(없으면 기본값) 가져오기 map.getOrDefault('A', 0); //해쉬맵 크기 가져오기 map.size(); //해쉬맵 key값 기준으로 전체 탐색 map.keySet(); //특정 키 삭제 map.remove..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 3. 6.
효율성[O(n2) -> O(n)] 섹션 - (2)
효율성[O(n2) -> O(n)] 섹션 - (2) 3-5-(1). 연속된 자연수의 합 (two pointers) • 연속된 자연수의 합으로 정수 N을 표현할 때는~ N/2 + 1 까지의 범위 내에서만 확인하면 된다. import java.util.Scanner; /* 3-5. 연속된 자연수의 합 [설명] N입력으로 양의 정수 N이 입력되면 2개 이상의 연속된 자연수의 합으로 정수 N을 표현하는 방법의 가짓수를 출력하는 프로그램을 작성하세요. */ public class Main1 { //솔루션 함수 public int solution (int N) { int answer = 0, sum = 0, lt= 0; int m = N/2+1; int[] arr = new int[m]; for(int i = 0; ..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 3. 3.
효율성[O(n2) -> O(n)] 섹션 - (1)
📍 섹션 3.Two pointers, sliding window [효율성 O(n2) -> O(n)] 효율성[O(n2) -> O(n)] 섹션 - (1) 3-1. 두 배열 합치기 | Two Pointers 알고리즘 사용 /* 3-1. 두 배열 합치기 [설명] 효율성 오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램을 작성하세요. */ public class Main1 { //솔루션 함수 public ArrayList solution(int n, int m, int[]a, int[]b) { ArrayList answer = new ArrayList(); int p1 =0, p2 = 0; //두 개의 포인터 선언 //각각 지칭할 배열 크기 안에서만 돌도록 조건 넣고 whi..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 3. 2.
배열(Array) 섹션 - (2)
배열(Array) 섹션 - (2) 2-5. 소수(에라토스테네스 체) • 소수 : 1보다 큰 자연수 중 1과 자기 자신만을 약수로 갖는 수 import java.util.Scanner; /* 2-5. 소수(에라토스테네스 체) * * [설명] * 자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요. * */ public class Main1 { //솔루션 함수 public int solution(int n) { int answer = 0; //int [] 배열 타입은 처음 생성시 기본값 0으로 세팅되어 있다. int[] ch = new int[n+1]; for(int i = 2; i
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 2. 28.
배열(Array) 섹션 - (1)
📍 섹션2. Array(1, 2차원 배열) 섹션 배열(Array) 섹션 - (1) 2-1. 큰 수 출력하기 첫 번째 수는 반드시 출력할 것. + 앞수보다 크면 answer에 이어붙임 import java.util.ArrayList; import java.util.Scanner; /* 2-1. 큰 수 출력하기 * 설명 N개의 정수를 입력받아, '자신의 바로 앞 수'보다 큰 수만 출력하는 프로그램을 작성하세요. (첫 번째 수는 무조건 출력한다) * */ public class Main1 { //솔루션 함수 public ArrayList solution(int n, int[] arr) { ArrayList answer = new ArrayList(); answer.add(arr[0]); //첫수 무조건 넣기 ..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 2. 27.