Dev Log

퀵 정렬 이란퀵 정렬의 메커니즘은 크게 다음과 같다. 하나의 리스트를 피벗(pivot)을 기준으로 두 개의 부분리스트로 나누어 하나는 피벗보다 작은 값들의 부분리스트, 다른 하나는 피벗보다 큰 값들의 부분리스트로 정렬한 다음, 각 부분리스트에 대해 다시 위처럼 재귀적으로 수행하여 정렬하는 방법이다. 퀵 정렬방법피벗을 하나 선택한다.피벗을 기준으로 양쪽에서 피벗보다 큰 값, 혹은 작은 값을 찾는다. 왼쪽에서부터는 피벗보다 큰 값을 찾고, 오른쪽에서부터는 피벗보다 작은 값을 찾는다.양 방향에서 찾은 두 원소를 교환한다.왼쪽에서 탐색하는 위치와 오른쪽에서 탐색하는 위치가 교차할 때까지 2번으로 돌아가 위 과정을 반복한다.교차한 지점을 기준으로 두 개의 부분리스트로 나누어 1번으로 돌아가 해당 부분리스트의 길이..

알고리즘/개념 및 TIP 2024. 11. 22. 14:28

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 1. 보석 무게를 기준으로 오름차순 정렬하고 무게가 같을경우 가격기준 내림차순으로 정렬한다. 2. 가방 무게를 기준으로 오름차순 정렬한다. => 보석 가격의 합이 최대가 되려면 가방보다 무게가 작으면서 가격은 제일 비싼 보석을 담아야한다. 3. PriorityQueue를 사용하여 무게가 작으면서 가장 비싼 보석을 찾아낸다. ※ 주의..

알고리즘/문제 2022. 2. 28. 14:38

https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 풀이 1. 두 묶음의 카드를 골라야한다. => Q : 어떤 기준에 의해서 두 묶음의 카드를 골라야할까? A : 문제 예시를 보고 가장 작은 카드 묶음 2개를 골라야하겠다. 2. 두 묶음의 카드를 합친다음에도 가장 작은 카드묶음 두개를 골라야한다. PriorityQueue(우선순위 큐)를 이용하면 정렬을 알아서 해준다. PriorityQueue(우선순위 큐)에 대한 정보는 여기를 클릭..

알고리즘/문제 2022. 2. 25. 16:19

https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 풀이 1. 5킬로그램의 봉지를 최대한 많이 선택해야한다. (3 ≤ N ≤ 5000) N의 범위가 3이상이기때문에 0개부터 계산한다. 2. 5킬로그램의 봉지 개수를 정할때 순차적으로 개수를 늘려나간다. 3. 5킬로그램의 봉지 개수를 먼저 선택한 후 3킬로그램의 봉지에 대해 고민한다. - 5킬로그램의 봉지 개수를 선택한 나머지가 3으로 나누어지지 않는다면 1번을 반복한다. 만약 5킬로그램의 봉지개수가 0이고 3..

알고리즘/문제 2022. 2. 15. 17:22

https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 풀이 동전갯수의 최솟값을 찾아야한다. 1. 금액이 큰 동전부터 선택한다. 2. 1번의 동전을 최대한 많이 선택한다. 3. 입력받은 금액만큼 동전을 선택했는지 확인한다. 그렇지 않다면 1번부터 다시 수행한다. 소스코드 package algorithm.greedy; import java.io.BufferedReader; import ja..

알고리즘/문제 2022. 2. 14. 16:19

그리디(Greedy) 알고리즘 Greedy란 '탐욕스러운, 욕심 많은'이라는 뜻을 가지고 있다. 우리는 어떠한 답을 효율적으로 찾으려고 다양한 알고리즘을 공부한다. 그러면 알고리즘에서 '탐욕스럽고 욕심 많은'이라는 뜻은 무엇일까? 필자의 생각은 빠르게 답을 찾으려고 하는 것이다. 순간순간 최적의 선택을 해나가는 방법으로 진행하여 최종적인 정답에 도달하게 된다. 계속해서 최적의 선택을 하였다고 해서 최종적인 정답이 정답이 아닐 수도 있다. 따라서 그리디 알고리즘은 최적의 해를 구하는 데 사용하는 '근사 알고리즘'이라고 할 수 있다. '근사 알고리즘'이란 해의 근사값을 구하는 알고리즘을 말한다. 가장 최적화되는 답을 구할 수는 없지만, 어느 정도 근삿값을 구할 수 있다. 방법 1. 선택 - 현재 상태에서 최..

알고리즘/개념 및 TIP 2022. 2. 11. 15:14

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 풀이 1. 상하좌우 이동이 5번되었을때 최댓값을 구해야한다. - 상하좌우 이동을 DFS로 구현해야겠구나 생각 - 재귀함수의 파라미터로 이동횟수를 +1씩해서 전달 - 재귀함수를 사용할때 배열의 값을 복제하여 파라미터로 넘겨준다. *중요* 2차원 배열은 clone 메소드로 단순복사할 수 없다. 별도의 로직 구현이 필요하다. 해당 내용이 궁금하면 여기 2. 한번의 이동에서 ..

알고리즘/문제 2022. 1. 13. 20:35

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 1. 국경선을 공유하는(인접한 나라)는 인구 차이가 L이상, R이하라면 국경선을 공유할 수 있다. 2. 국경선이 모두 열렸다면 인구이동 시작 -> 국경을 공유하는 나라들(연합)이 구성이 된다면 문제의 핵심은 두 가지라고 생각한다. (Q1) 연합을 어떻게 구성할 것인가 => BFS를 통해 연합을 구성한다. (Q2) N개의 연합이 생길 수 있고, N개의 연합이 인구이동을 끝내야 하..

알고리즘/문제 2022. 1. 10. 14:49