섹션3. 자료구조 활용 섹션 - (1)

🎈섹션3. 자료구조 활용 섹션 - (1) 🟦 3-1. 최대 길이 연속 수열 문제 풀이 코드 | 오류 났다. 최초 시도 때 나는 arr[i+1]-arr[i] == 1 즉, 1씩 차이나는 값일 때만 카운팅++하고, 나머지는 continue로 지속한 뒤, Math.max()로 더 큰 cnt 값이 나타날 때 answer에 세팅해주면 되는 문제라고 생각했는데, 계속해서 오류가 났다. package to_0428; /* 3-1. 최대 길이 연속수열 * */ import java.util.*; class Solution1 { public int solution(int[] nums){ int answer = 0; int cnt = 0; //1) 정렬 해놓고 Arrays.sort(nums); for(int i=0; i

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
• · 2023. 4. 28.
• textsms

섹션2. 해싱 & 시간 파싱 알고리즘 - (4)

🎈섹션2. 해싱 & 시간 파싱 알고리즘 - (4) 🟦 2-6. 문서 도난 ⬛ 문자열 (알파벳 순으로 ) 비교하는 compareTo() 사용법 A.compareTo(B) 1) A 가 B보다 앞순이면 음수 출력 2) A 가 B보다 뒷순이면 양수 출력 3) A== B순이면 0 출력 ⬛ 시간 파싱 HH:MM → 분 단위로 변환하여 비교할 것 getTime(String HH:MM) 함수 만들어서 들어온 입력을 → 분 단위로 변환시킴 HH:MM 단위로 들어온 String은 split(”:”) 기준으로 잘라서 앞은 HH, 뒤는 MM //시간 -> 분 단위 변형 함수 public int getTime(String time) { int H = Integer.parseInt(time.split(":")[0]); int M..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
• · 2023. 4. 27.
• textsms

섹션2. 해싱 & 시간 파싱 알고리즘 - (3)

🎈섹션2. 해싱 & 시간 파싱 알고리즘 - (3) 🟦 2-4. 음수가 있는 부분수열 최초 내 시도 | ⇒ 이중 for()문으로 답은 나왔다. | O(n2) 여서 비효율 나는 이중 for문 돌면서 특정 i로 찍은 현재 값에서 j로 0~i-1까지 차례로 돌며 구간합 == m 일때마다 answer++처리 했다. 다만, 만약 m값이 nums 값 그 자체일 경우도 고려해야 한다고 생각 package to_0426; /* 2-4. 음수가 있는 부분수열 문제 풀이 * */ import java.util.*; class Solution1 { //솔루션 함수 public int solution(int[] nums, int m){ int answer = 0; int[] az = new int[nums.length]; fo..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
• · 2023. 4. 26.
• textsms

섹션2. 해싱 & 시간 파싱 알고리즘 - (2)

🎈섹션2. 해싱 & 시간 파싱 알고리즘 - (2) 🟦 2-3. 서로 다른 빈도수 만들기 문제 풀이 이 문제는 유일한(Unique) 빈도수를 구하는 게 관건이다. 새로운 HashSet 를 만들어서 HashMap에 각 문자별 빈도수만 뽑아서 중복 검사 후 담아야 한다. 1) 각각의 Map에 담긴 전체 key 순회하면서 2) 각 key의 빈도수값이 Set에 중복되는 동안 계속 while() 문 돌며 Map에 다시 해당 key에 대한 value를 -1 처리, answer++ (중복 동안) 3) while 빠져나와서 만약 map의 해당 key 값이 0인 경우 continue 4) 확인용 Set에 최종 add처리한다. 코드 package to_0424; import java.util.HashMap; import j..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
• · 2023. 4. 24.
• textsms

섹션2. 해싱 & 시간 파싱 알고리즘 - (1)

🎈섹션2. 해싱 & 시간 파싱 알고리즘 - (1) 🟦 2-1. 한 번 사용한 최초 문자 코드 HashMap 저장해야 한다. map.getOrDefault() 사용해서 문자가 중복없이 카운팅 되도록 해야 함 다시 i로 전체 길이 순회하면서 i번째 문자(key) 기준으로 get 한 value가 1인 경우 해당 i+1을 곧장 리턴해주어야 한다. // 2-1. 한 번 사용한 문자 import java.util.*; class Solution1 { //솔루션 함수 public int solution(String s){ //각 문자, 빈도수 HashMap map = new HashMap(); //각 문자별 빈도수 카운팅 for(char x : s.toCharArray()) { //맵에 담되, 중복 없이 담음 map..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
• · 2023. 4. 20.
• textsms

섹션1. 시뮬레이션 & 구현 - (3) | 과일 가져가기 문제 풀이

🎈섹션1. 시뮬레이션 & 구현 - (3) | 과일 가져가기 문제 풀이 🟦 1-6. 과일 가져가기 문제 문제 분석 (풀이) 문제 조건 1. 서로 이득이 될 때만 교환이 가능 문제 조건 2. 교환 가능 여러명 이면 번호 작은 학생과 교환 ⇒ 서로 교환 시 이득이 나는 조건 1) 각 학생에게 최솟값이 유일해야 한다. 2) 서로 교환하려는 최솟값 과일이 달라야 한다. (= 과일 idx 번호 달라야 한다.) 3) 교환 이후, 1개 증가한 과일 개수가 여전히 그대로 최솟값인 과일이어야 한다. (= 증가한 과일 ≥ 감소한 과일) 내 시도 나는 Fruit (사과, 배, 귤) 객체를 새로 생성해서, ArrayList 에 담아 → 각 학생의 최솟값을 체크해놓고, 최솟값 과일이 다를 경우 교환이 되도록 할 생각이었다. → ..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
• · 2023. 4. 19.
• textsms

섹션1. 시뮬레이션 & 구현 - (2)

🎈섹션1. 시뮬레이션 & 구현 - (2) 🟦 1-3. 잃어버린 강아지 | 현수, 강아지 동시 이동 문제 현수는 농사지을 땅을 찾아 강아지를 데리고 산으로 들로 땅을 찾아 다니고 있었다. 숲속에서 낮잠을 자던 현수는 강아지가 도망가버려 강아지를 잃게 되었다. 강아지가 어디로 갔는지 모르는 현수는 강아지를 찾아 나섰다. 다행히 강아지에게 위치 추적기가 달려 있어 핸드폰 실시간 위성지도로 현수의 위치와 강아지의 위치, 그리고 근처의 지도를 현수는 알 수 있습니다. 지도의 크기는 항상 10_10이며, 각각의 칸에는 각각 나무, 빈칸, 강아지, 그리고 현수가 있을 수 있습니다. 지도는 다음과 같이 주어진다. 0 - 빈칸, 1 - 나무, 2 - 현수, 3 - 강아지 강아지와 현수는 항상 고정된 방법으로 지도를 다닌..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
• · 2023. 4. 14.
• textsms

섹션1. 시뮬레이션 & 구현 - (1) | 사다리타기, 로봇 문제 풀이

🎈섹션1. 시뮬레이션 & 구현 시뮬레이션 & 구현 알고리즘 어떤 개체가 이동하는 것을 코드 상으로 구현한 것 (상/하/좌/우) 이동 문제를 해석하고 해석한 내용을 코드로 구현하는 게 중요하다. 🟦 1-1. 사다리 타기 문제 현수네 반에는 n명의 학생이 있습니다. 선생님은 n명의 학생이 모두 사다리타기를 한 다음 당첨 된 학생을 이 번주 학급회장으로 선출하려고 합니다. 각 학생은 알파벳 대문자로 표시됩니다. 만약 n=5 이고 아래와 같은 사다리라면 위에 사다리는 세로 라인이 1부터 5까지로 표현는 5개의 세로줄과 3개의 가로줄을 가지고 있습니다. 첫 번째 가로줄은 1번 세로줄과 2번 세로줄을 연결한 가로막대와 3번 세로줄과 4번 세로줄을 연결한 가로막대 2개가 있는데 이를 표현하는 방법은 [1, 3]으로 ..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
• · 2023. 4. 10.
• textsms

동적 계획 알고리즘 -(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[]는 최대 갖는 ..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
• · 2023. 4. 6.
• textsms

동적 계획 알고리즘 -(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

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
• · 2023. 4. 3.
• textsms

트리 관련 개념 정리

트리 관련 개념 정리 신장트리와 최소비용 신장 트리 🟦신장트리 : n개 정점 무방향 그래프에서 간선 n-1개로 이루어진 부분 그래프 정점 n개, 간선 n-1개, 사이클X, 연결그래프(단절X) 🟦최소비용 신장 트리 : 무방향 가중치 그래프에서 신장 트리 구성 간선의 가중치 합이 최소인 그래프 1) 크루스칼 알고리즘 (1) 가중치 높은 간선 제거하며 최소비용 만들기 (2) 가중치 낮은 간선 삽입하며 최소비용 만들기 2) 프림 알고리즘 (간선 정렬 X) 하나의 정점에서 시작하여 트리 확장해감 확장 정점들에 부속된 모든 간선들을 비교하며 가장 낮은 간선 연결 확장 🟪 최단 경로 🟦 최단 경로 (신장트리가 아닌) 가중치 그래프에서 정점u와 정점 v를 잇는 경로 중 가중치 합이 최소인 경로 1) 다익스트라 최단 경..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
• · 2023. 4. 3.
• textsms

그리디 알고리즘 섹션 - (2)

그리디 알고리즘 섹션 - (2) 🟪 PriorityQueue 우선순위 큐 일반적으로 스택은 LIFO 후입선출 구조를 갖고, 큐는 FIFO 선입선출 구조를 갖는다. 그 중에서도 우선순위 큐의 경우, 들어온 순서와는 상관없이 우선순위가 높은 요소를 먼저 처리하는 자료구조이다. 🟪 ‘자바’의 우선순위 큐 라이브러리 사용법 기본적으로 PriorityQueue를 생성하면 우선순위 낮은 순으로 객체가 생성되는데 , 그 역순으로 (우선순위 높은 순) 으로 생성하려면 생성 인자로 Collections.reverseOrder() 를 주면 된다. import java.util.PriorityQueue; //import //int형 priorityQueue 선언 (우선순위가 낮은 숫자 순) PriorityQueue prio..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
• · 2023. 3. 31.
• textsms

그리디 알고리즘 섹션 - (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..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
• · 2023. 3. 30.
• textsms

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...

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
• · 2023. 3. 29.
• textsms

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 =..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
• · 2023. 3. 28.
• textsms

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..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
• · 2023. 3. 27.
• textsms

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. 동전교환 다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가?..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
• · 2023. 3. 24.
• textsms

DFS, BFS 활용 섹션 - (1)

📍 섹션8. DFS, BFS 활용 DFS, BFS 활용 섹션 - (1) 8-1. 합이 같은 부분집합 | DFS import java.util.Scanner; /* 8-1. 합이 같은 부분집합 (DFS) [입력] 첫 번째 줄에 자연수 N(1

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
• · 2023. 3. 23.
• textsms

그래프 관련 정리 -(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..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
• · 2023. 3. 22.
• textsms