Coding Test (40) 썸네일형 리스트형 백준 회의실 배정 성공(1931) 그리디를 이용한 방배정 문제 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 간단하게 빨리 끝나는 회의실 순으로 최적의 해를 구하면 된다. 그리고 빨리 시작하는 회의실을 잡아야하는데 그게 예시로 5-10, 10-10 두개의 회의를 사용해야하기 때문에...? 저게 말이되나... 일단 그렇다 package greedy; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Pri.. 백준 동전 0(11047) 그리디 문제를 하나 풀어본다. 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 가장 간단한 그리디 알고리즘 문제이다 현재 상황에서 최적의 상태를 체크해서 코인 개수를 구하고 나머지로 계속 반복하면 된다. package greedy; import java.io.*; import java.util.StringTokenizer; public class Q11047 { public sta.. 그리디 알고리즘 그리디 알고리즘 그리디 알고리즘이란 최적화 문제를 해결하는 알고리즘, 각 단계에서 지금 당장 최적의 선택을 계속해서 내려가면서 최종적으로 전체적으로 최적해를 찾아내는 방식이다. 예를 들어 최소 스패닝 트리, 최단 경로, 배낭 문제 등에 적용 할 수 있다. 다음과 같은 구조를 같습니다. 1. 해의 후보 중에 하나를 선택합니다. 2. 선택한 후보가 문제의 제약 조건에 부합하는지 확인합니다. 3. 부합한다면, 선택한 후보를 정답에 추가하고, 문제의 제약 조건을 수정합니다. 4. 제약 조건을 만족할때까지 1-3단계를 반복합니다. 각 단계에세 지금 당장의 최적인 선택을 하기에, 전체적인 최적해를 찾기 위해선 이러한 선택이 계속 이루어져야 합니다. 하지만, 항상 최적의 해를 보장하지 않습니다. 대표적인 문제로는 동.. 백준 가운데를 말해요(1655) 자료구조 문제 풀어보기~ https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제의 포인트는 중간값을 계속 유지해야한다. 무식하게 다 넣어놓고 정렬하면 시간초과의 길.... 중간값을 유지하는 방법은 우선순위 큐를 두개를 이용하면 된다. 양쪽에 번걸아가며 넣으며 중간값을 계속 유지해두면 된다. package struct; import java.io.*; import java.util.ArrayList; import java.util... 백준 듣보잡(1764) 이전 문제가 쉬운거 같아서 새로 풀어봤는데 더 쉽다.. https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 해시 테이블로 관리하면 된다. package struct; import java.util.ArrayList; import java.util.Collections; import java.util.HashSet; import java.util.Scanner; public class Q1764 { public static void main(Str.. 백준 카드2(2164) 자료구조 보이는 문제를 풀었다 https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 음... 문제가 너무 간단해서 금방 풀어버렸다 큐 이용하면 될듯하다. package struct; import java.util.Deque; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.concurrent.ConcurrentLinkedDequ.. 백준 수 정렬하기 2(2751) 이번에는 정렬 문제를 풀어보려고 문제 하나를 찾았다. https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬.. 백준 숫자 카드(10815) 백준에서 보이는 이분 탐색 문제 하나를 선택했다. https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘.. 이진 탐색 이진 탐색이란? 이진 탐색 (Binary search) 이진 탐색은 정렬 된 데이터 배열에 특정 값을 찾아내는 알고리즘이다. 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교 후 X가 중간값보다 작으면 중간값 기준 좌측, X가 중간값 기준으로 크면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하여 비교한다. 해당 값을 찾을때까지 이 과정을 반복한다. 위 그림을 보면 오름차순으로 정렬된 배열에서 Target(22)를 찾는 이진 탐색을 시작한다. 탐색을 반복적으로 수행하여 마지막 22 타겟을 찾는다. 시간복잡도 : O(logN) 해당 알고리즘은 반복문과 재귀 두가지 방법으로 구현이 가능하다. 시작 개발자 경력으로 이제 거의 4년차가 가까워져가는 나.. 경력기간중 한번의 이직을 성공한 나... 요즘들어 조금 나태해져 가는거 같아서 블로그를 시작하고 첫 페이지 만든다. 나름 매일 개발을 진행하고있지만 블로그 활동을 따로 진행하지도 않고 Git도 public하게 열어두지 않아서 나의 개발 공부의 흔적이 남아있지 않는거 같아서 시작해본다. 첫 시작은 나의 다음 이직을 위해 준비하는 코딩테스트 페이지 ( 필요 없을수도 있는데... 조금씩은 준비하자는 마인드) 이전에 코딩 테스트 준비했었는데 해당 정보도 따로 노션으로만 관리하고 이제는 너무 오래되어서 머리속에서 사라진 기억들을 차곡차곡 다시 쌓아보려 한다. 준비에 뭐가 필요할까 기웃기웃 찾아본 나의 정리 글이다. 1. 자료구조 & 알고리즘 공부 당연한 얘기.. 이전 1 2 3 4 다음
