백준 | 10816번. 숫자 카드 2 문제 - HashMap
10816번. 숫자 카드 2 문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,00..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 4. 24.
섹션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..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 4. 20.
섹션1. 시뮬레이션 & 구현 - (3) | 과일 가져가기 문제 풀이
🎈섹션1. 시뮬레이션 & 구현 - (3) | 과일 가져가기 문제 풀이 🟦 1-6. 과일 가져가기 문제 문제 분석 (풀이) 문제 조건 1. 서로 이득이 될 때만 교환이 가능 문제 조건 2. 교환 가능 여러명 이면 번호 작은 학생과 교환 ⇒ 서로 교환 시 이득이 나는 조건 1) 각 학생에게 최솟값이 유일해야 한다. 2) 서로 교환하려는 최솟값 과일이 달라야 한다. (= 과일 idx 번호 달라야 한다.) 3) 교환 이후, 1개 증가한 과일 개수가 여전히 그대로 최솟값인 과일이어야 한다. (= 증가한 과일 ≥ 감소한 과일) 내 시도 나는 Fruit (사과, 배, 귤) 객체를 새로 생성해서, ArrayList 에 담아 → 각 학생의 최솟값을 체크해놓고, 최솟값 과일이 다를 경우 교환이 되도록 할 생각이었다. → ..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 4. 19.
섹션1. 시뮬레이션 & 구현 - (2)
🎈섹션1. 시뮬레이션 & 구현 - (2) 🟦 1-3. 잃어버린 강아지 | 현수, 강아지 동시 이동 문제 현수는 농사지을 땅을 찾아 강아지를 데리고 산으로 들로 땅을 찾아 다니고 있었다. 숲속에서 낮잠을 자던 현수는 강아지가 도망가버려 강아지를 잃게 되었다. 강아지가 어디로 갔는지 모르는 현수는 강아지를 찾아 나섰다. 다행히 강아지에게 위치 추적기가 달려 있어 핸드폰 실시간 위성지도로 현수의 위치와 강아지의 위치, 그리고 근처의 지도를 현수는 알 수 있습니다. 지도의 크기는 항상 10_10이며, 각각의 칸에는 각각 나무, 빈칸, 강아지, 그리고 현수가 있을 수 있습니다. 지도는 다음과 같이 주어진다. 0 - 빈칸, 1 - 나무, 2 - 현수, 3 - 강아지 강아지와 현수는 항상 고정된 방법으로 지도를 다닌..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 4. 14.
섹션1. 시뮬레이션 & 구현 - (1) | 사다리타기, 로봇 문제 풀이
🎈섹션1. 시뮬레이션 & 구현 시뮬레이션 & 구현 알고리즘 어떤 개체가 이동하는 것을 코드 상으로 구현한 것 (상/하/좌/우) 이동 문제를 해석하고 해석한 내용을 코드로 구현하는 게 중요하다. 🟦 1-1. 사다리 타기 문제 현수네 반에는 n명의 학생이 있습니다. 선생님은 n명의 학생이 모두 사다리타기를 한 다음 당첨 된 학생을 이 번주 학급회장으로 선출하려고 합니다. 각 학생은 알파벳 대문자로 표시됩니다. 만약 n=5 이고 아래와 같은 사다리라면 위에 사다리는 세로 라인이 1부터 5까지로 표현는 5개의 세로줄과 3개의 가로줄을 가지고 있습니다. 첫 번째 가로줄은 1번 세로줄과 2번 세로줄을 연결한 가로막대와 3번 세로줄과 4번 세로줄을 연결한 가로막대 2개가 있는데 이를 표현하는 방법은 [1, 3]으로 ..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 4. 10.
백준 | DP 섹션 - 11053번. 가장 긴 증가하는 부분 수열 문제 풀이
23.04.06 문풀 11053번. 가장 긴 증가하는 부분 수열 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. import java.util.Scanner; /* 11053번. 가장 긴 증가하는 부분 수열 */ public class Main {..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 4. 6.
동적 계획 알고리즘 -(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[]는 최대 갖는 ..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 4. 6.
동적 계획 알고리즘 -(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
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 4. 3.
트리 관련 개념 정리
트리 관련 개념 정리 신장트리와 최소비용 신장 트리 🟦신장트리 : n개 정점 무방향 그래프에서 간선 n-1개로 이루어진 부분 그래프 정점 n개, 간선 n-1개, 사이클X, 연결그래프(단절X) 🟦최소비용 신장 트리 : 무방향 가중치 그래프에서 신장 트리 구성 간선의 가중치 합이 최소인 그래프 1) 크루스칼 알고리즘 (1) 가중치 높은 간선 제거하며 최소비용 만들기 (2) 가중치 낮은 간선 삽입하며 최소비용 만들기 2) 프림 알고리즘 (간선 정렬 X) 하나의 정점에서 시작하여 트리 확장해감 확장 정점들에 부속된 모든 간선들을 비교하며 가장 낮은 간선 연결 확장 🟪 최단 경로 🟦 최단 경로 (신장트리가 아닌) 가중치 그래프에서 정점u와 정점 v를 잇는 경로 중 가중치 합이 최소인 경로 1) 다익스트라 최단 경..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 4. 3.
그리디 알고리즘 섹션 - (2)
그리디 알고리즘 섹션 - (2) 🟪 PriorityQueue 우선순위 큐 일반적으로 스택은 LIFO 후입선출 구조를 갖고, 큐는 FIFO 선입선출 구조를 갖는다. 그 중에서도 우선순위 큐의 경우, 들어온 순서와는 상관없이 우선순위가 높은 요소를 먼저 처리하는 자료구조이다. 🟪 ‘자바’의 우선순위 큐 라이브러리 사용법 기본적으로 PriorityQueue를 생성하면 우선순위 낮은 순으로 객체가 생성되는데 , 그 역순으로 (우선순위 높은 순) 으로 생성하려면 생성 인자로 Collections.reverseOrder() 를 주면 된다. import java.util.PriorityQueue; //import //int형 priorityQueue 선언 (우선순위가 낮은 숫자 순) PriorityQueue prio..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 3. 31.
그리디 알고리즘 섹션 - (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..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 3. 30.
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...
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1
- · 2023. 3. 29.
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.
백준 | 그래프 순회 - 2606번. 바이러스 (DFS, BFS) 풀이
2606번. 바이러스 (DFS, BFS) 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 3. 23.
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.