![]()
문제 출처 : https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, ..
![]()
문제 링크 : https://www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N..
![]()
문제 링크 : 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 문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부..
![]()
문제 링크 : https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다. www.acmicpc.net 문제 수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장 났다. 리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고 있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른..
![]()
https://helpx.adobe.com/kr/download-install/kb/creative-cloud-desktop-app-download.html Creative Cloud 데스크탑 앱을 다운로드하는 방법 Creative Cloud 데스크탑 앱을 사용하여 Creative Cloud 앱을 다운로드, 설치 및 업데이트할 수 있습니다. helpx.adobe.com 이 사이트 접속 후 스크롤을 밑으로 조금 내리면 보이시는 곳에서 대체 다운로드 링크를 누르면 밑에 나오는 지침에 따라 설치하시면 됩니다!
![]()
이진 탐색트리란? 이진 탐색트리는 다음과 같은 속성이 있는 자료 구조이다. 각 노드에 값이 있고, 각 노드마다 최대 두 개의 자식을 갖는다. 왼쪽 자식은 부모보다 키 값이 작고, 오른쪽 자식은 부모보다 키 값이 크다. 이진 탐색트리 예시 {8,3,10,1,6,14,4,7,13} 이 노드를 기준으로, 루트 8 의 왼쪽 서브트리는 3부터 그 이하의 노드들로 이루어진 트리이고, 루트 8 의 오른쪽 서브트리는 10부터 그 밑에있는 노드들로 이루어진 트리이다. 이진 탐색 트리는 유일하지 않다. 예를 들어 {1, 2, 3, 4}에 대한 이진 탐색 트리는 이런식으로 두가지 이상으로 표현 가능하다. 만약 어떤 키 값이 자주 접근될 지 모른다면, 균형잡힌 오른쪽 트리가 유리할 것이고, 만약 1 값이 가장 자주 접근된다면..
![]()
기본 아이디어 -> 버블 정렬과 비슷하다. 1등을 뽑아내고 (최대 힙의 루트), 나머지 원소에서 1등을 계속 뽑아내면 정렬이다. 버블 정렬과 다른점 -> 1등을 뽑아낸 뒤, 나머지 원소에서 1등을 뽑을 때 다시 비교할 필요 없이 2등이 자동으로 1등이 된다. (루트 원소를 제거 한 후 -> 힙을 유지하는 방식) 힙이란? 힙의 성질 1. 리프 노드를 제외한 모든 노드는 자식이 반드시 둘이다. 완전 이진트리에서 리프 노드가 어떤 노드 이후부터 모두 생략된 형태이다. 트리를 배열로 표현할 수 있다. (노드의 왼쪽 자식 : node * 2, 오른쪽 자식 : node * 2 + 1) 1 2 3 4 5 최대 힙 (max heap) 정의 : 각 노드들이 (루트 포함) 자식들보다 큰 힙 최대 힙에서 루트 원소 제거 여..
![]()
병합 정렬 정의 : 분할 정복 알고리즘의 하나로 정렬되지 않은 리스트를 잘라 나누어 정렬 한 후 다시 병합하는 정렬기법이다. 작동 방식 1. 분할: 정렬 되지 않은 리스트를 절반으로 나누어 두 부분 리스트로 나눈다. 이를 눈에 보일만큼 작은 크기로 나누어 질 때까지 계속 실행한다 2. 정복: 나누어진 리스트들을 재귀적으로 다시 정렬한다. 3. 결합: 정렬된 리스트들을 하나의 배열에 병합한다. 작동 방식만 보고는 이해가 안되니 바로 그림으로 살펴 보도록 하자. 위 그림은 초기 배열 [3,1,7,2,8,4,6,5]를 밑에서 부터 위로 정렬하는 Down-Top 방식의 병합 정렬이다. 알고리즘의 진행 1. 전체 리스트의 앞의 반, 뒤의 반을 병합 정렬을 통해서 정렬 2. 병합 정렬에 의해서 앞의 반, 뒤의 반 ..
버블 정렬 정의 : 버블 정렬은 말 그대로 거품 정렬이다. 리스트 안의 원소들이 점점 뒤로 밀려들어가기 때문에 이 모습이 마치 거품이 수면위로 올라오는 듯한 모습처럼 보여 지어진 이름이다. 방법 : 맨 왼쪽 원소부터 바로 이웃한 원소와 비교해 가면서, 큰 수가(내림차순인 경우 작은 수가) 오른쪽으로 가도록 교환한다. 이 때 맨 끝과 그 앞의 원소까지 비교하면, 가장 큰 원소(또는 가장 작은 원소)를 찾은 것이므로, 다시 나머지 n-1개 수에 대하여 다시 반복한다. 예시 9 5 2 4 1 라는 배열이 있다고 가정하자. 오름차순을 만드는 버블 정렬을 순차적으로 표현하면 9 5 2 4 1 -> 5 9 2 4 1 -> 5 2 9 4 1 -> 5 2 4 9 1 -> 5 2 4 1 9 5 2 4 1 9 -> 2 5..
정렬이란? n개의 서로 다른 수가 주어졌을 떄, 이들을 이동하여 점점 커지게(오름차순), 또는 점점 작아지게(내림차순)으로 만드는 문제이다. ex) 4 2 1 9 5 -> 1 2 3 5 9 이런 식의 문제들은 아주 기본적이지만 실생활에 자주 쓰인다. 수능시험을 본 후 수십 만개의 omr카드를 성적순으로 분류해야하는데 이를 일일히 카운팅하면 정말 피곤할것같다. 머리가 대머리가 되버릴 수도 있다! 이 문제를 풀기 위해선 여러가지 정렬방법을 적용할 수 있다. 대표적인 정렬 방법으로는 버블 정렬 (Bubble sort) 삽입 정렬 (Insert sort) 병합 정렬 (Merge sort) 퀵 정렬 (Quick sort) 힙 정렬 (Heap sort) 그 이외에 버킷 정렬, stable sort, 기수 정렬, 계..
탐색 문제의 최적성 입력으로 주어진 수들 중 어떤 값을 찾는 탐색 문제는 항상 정렬만이 최적의 답은 아니다 문제 1. 정렬되지 않은 배열 A = {1,2,...,n} 중에서, 특정한 수 하나만 빼고, 무작위의 순서로 총 n-1개의 숫자가 한번에 하나씩 입력된다. 배열 A에서 빠진 하나의 수를 찾아라 이러한 문제를 봤을 때 가장 먼저 떠오르는 풀이법은 입력된 숫자들을 boolean배열에 저장하면서 숫자가 나왔을 때 그 배열을 true값으로 바꾸고, n-1개의 숫자가 모두 들어오면 배열을 처음부터 뒤져서 false인 값을 찾는다. 이런식으로 하면 boolean배열이 하나 필요하고, for문을 이용해 배열을 돌면서 boolean을 찾기 때문에 최소 1번, 최대 n번의 비교가 필요한 방법이다. 이 방법의 시간 ..
![]()
하노이 탑이란? 그림과 같이 세 개의 기둥과 이 기둥에 꽃을 수 있는 다양한 원판들이 있다. 이 탑은 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 기존에 있던 그대로 다른 기둥으로 옮겨서 다시 쌓아야한다. 조건은 다음과 같다 1. 한 번에 하나의 원판만 옮길 수 있다. 2. 큰 원판이 작은 원판 위에 있어서는 안 된다. 이 문제는 원판의 개수가 적을 경우는 머리로 쉽게 생각할 수 있지만 조금만 커져도 원판을 이동시키는 횟수가 급격하게 많아기지 때문에 생각만큼 쉽지 않다. 이 문제에 대한 해결방안은 알고리즘 설계 기법중 하나인 재귀(recursion)을 이용하는 것인데 방법은 다음과 같다. n=1 : 원판을 그냥 옮긴다 n=k 일 때 옮길 수 있다고 가정 한 후 n=k+1 일 때 (미리 가정한)..
