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.
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.
String(문자열) 섹션 - (3)
String(문자열) 섹션 - (3) 1-9. 숫자만 추출 | 아스키 번호로 구분 후 (1) answer 누적 or (2) isDigit() 구분 후 형변환 * 1-9.숫자만 추출 * * 문자와 숫자가 섞여있는 문자열이 주어지면 그 중 숫자만 추출하여 그 순서대로 자연수를 만듭니다. * 만약 “tge0a1h205er”에서 숫자만 추출하면 0, 1, 2, 0, 5이고 이것을 자연수를 만들면 1205이 됩니다. 추출하여 만들어지는 자연수는 100,000,000을 넘지 않습니다. ( 즉, 첫 0 은 무시함) // 1)문자, 숫자 식별 -> 아스키 번호로 구분 * 문자형 숫자 는'0': 48 2진수 (#=1, *=0) 로 바꾸고 2) 2진수 -> 10진수 변환 3) 아스키 번호 기준으로 10진수 -> 65 문자..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 2. 23.
String(문자열) 섹션 - (2)
String(문자열) 섹션 - (2) 1-5. 특정 문자 뒤집기 | Character.isAlphabetic() 사용해보기 import java.util.Scanner; /* 1-5. 특정 문자 뒤집기 * 영어 알파벳과 특수문자로 구성된 문자열이 주어지면 영어 알파벳만 뒤집고, 특수문자는 자기 자리에 그대로 있는 문자열을 만들어 출력하는 프로그램을 작성하세요. * */ // 알파벳과 특수문자를 구분할 수 있어야 하고 // lt와 rt 가 양끝단에서 ++ 출발하고, 둘다 알파벳일 경우에만 교환이 이루어져야 함 // lt 각 문자 배열 만들어 char[] s = str.toCharArray(); int lt = 0, rt = str.length()-1; //각 포인팅 할 것 //주요 로직 // -> 이 안에..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 2. 22.
String(문자열) 섹션 - (1)
String(문자열) 섹션 - (1) 1-1. 문자 찾기 한 개의 문자열을 입력받고, 특정 문자를 입력받아 해당 특정문자가 입력받은 문자열에 몇 개 존재하는지 알아내는 프로그램을 작성하세요. // 섹션 1-1 문자 찾기 //한 개의 문자열을 입력받고, 특정 문자를 입력받아 해당 특정문자가 입력받은 문자열에 몇 개 존재하는지 알아내는 프로그램을 작성하세요. //대소문자를 구분하지 않습니다.문자열의 길이는 100을 넘지 않습니다. //입력 : 첫 줄 문자열 , 두 번째줄 문자 입력 //출력 : 첫 줄의 문자열 속에서 두 번째 '문자' 포함된 [문자 개수]를 출력한다. public class Main { //솔루션 함수 (문자열, 문자) => 포함 개수 리턴 public int solution(String s..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 2. 21.