Kwin's Development Diary.

문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 문제 접근 방법 카운팅 정렬을 사용하면 된다. 1. 입력으로 들어올 수 있는 수의 범위만큼 1차원 배열을 선언해준다. 2. 각각의 인덱스에 해당하는 숫자가 입력되면 해당 인덱스의 수를 +1 해준다. 3. 모든 인덱스를 순환하여 (인덱스 오름차순으로 순환) 배열에 저장된 수만큼 출력을 반복해주고 다음 인덱스로 넘어간다. +) 아래 두 가지의 방법으로 작성한 코드도 결과를 비..

문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재 절단기를 이용해서 나무를 구할 것이다. 목재 절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, ..

문제 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 땅을 파거나 집을 지을 수 있는 게임이다. 목재를 충분히 모은 lvalue는 집을 짓기로 하였다. 하지만 고르지 않은 땅에는 집을 지을 수 없기 때문에 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업을 해야 한다. lvalue는 세로 N, 가로 M 크기의 집터를 골랐다. 집터 맨 왼쪽 위의 좌표는 (0, 0)이다. 우리의 목적은 이 집터 내의 땅의 높이를 일정하게 바꾸는 것이다. 우리는 다음과 같은 두 종류의 작업을 할 수 있다. 좌표 (i, j)의 가장 위에 있는 블록을 제거하여 인벤토리에 넣는다. 인벤..

문제 수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계 값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자. 산술평균 : N개의 수들의 합을 N으로 나눈 값 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값 최빈값 : N개의 수들 중 가장 많이 나타나는 값 범위 : N개의 수들 중 최댓값과 최솟값의 차이 N개의 수가 주어졌을 때, 네 가지 기본 통계 값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. 출력 첫째 줄에는 산술평균을 출력한다. 소수점 이하..

그래프 순회(graph traversal), 그래프 탐색(graph search) - 하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한 번씩 방문하여 처리하는 연산 - 그래프 탐색 방법 ㄴ 깊이 우선 탐색 (Depth First Search : DFS) ㄴ 너비 우선 탐색 (Breadth First Search : BFS) 깊이 우선 탐색(Depth First Search : DFS) >>> A - B - D - G - E - C - F ① 시작 정점 v를 결정하여 방문 ② 정점 v에 인접한 정점 중 1. 방문하지 않은 정점 w가 있으면, 정점 v를 스택에 push 하고 w를 방문하고 w를 v에 대입하여 ②과정 반복 수행 2. 방문하지 않은 정점이 없으면, 탐색의 방향을 바꾸기 위해 마지막 방문 정..

그래프 (graph) - 선형 자료구조나 트리 자료구조로 표현하기 어려운 多:多관계를 가지는 원소를 표현하기 위한 자료구조 - 객체를 나타내는 정점(vertex)과 객체를 연결하는 간선(edge)의 집합 ☞ G = (V, E) ㄴ V : 그래프에 있는 정점들의 집합 ㄴ E : 정점을 연결하는 간선들의 집합 - 인접, 부속 ㄴ 그래프에서 두 정점 Vi와 Vj를 연결하는 간선 (Vi, Vj)가 있을 때, 두 정점 Vi와 Vj를 인접(adjacent)한다고 표현 ㄴ 간선 (Vi, Vj)는 정점 Vi와 Vj에 부속(incident)되어 있다고 표현 - 차수(degree) ㄴ 무방향 그래프의 Vn정점의 차수 = Vn정점에 부속되어 있는 간선 수 ㄴ 방향 그래프의 Vn정점의 차수 = Vn정점으로 진입하는 간선 수 ..

힙(heap) - 완전 이진트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해 만든 자료구조 - 최대 힙(max heap) ㄴ 키 값이 가장 큰 노드를 찾기 위한 완전 이진트리 ㄴ 부모 노드 키 값 ≥ 자식 노드 키 값 ㄴ 루트 노드 : 키 값이 가장 큰 노드 - 최소 힙(min heap) ㄴ 키 값이 가장 작은 노드를 찾기 위한 완전 이진트리 ㄴ 부모 노드 키 값 ≤ 자식 노드 키 값 ㄴ 루트 노드 : 키 값이 가장 작은 노드 힙 삽입 연산 1단계 : 완전 이진트리를 유지하면서 노드를 확장하여, 삽입할 원소를 임시 저장 ㄴ 노드가 n개인 완전 이진트리에서 다음 노드의 확장 자리는 n+1번의 노드 ㄴ n+1번 자리에 노드를 확장하고, 그 자리에 삽입할 원소를 임시 저장..

문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 문제 접근 방법 이번 문제는 삽입과 동시에 정렬을 진행할 것인지, 혹은 입력을 다 받고 정렬을 할 것인지 두 가지를 비교해보도록 하겠다. 1. 삽입과 동시에 정렬 - PriorityQueue 우선순위 큐를 사용하여 오름차순으로 입력된 숫자를 큐에 삽임 함과 동시에 정렬이 되도록 코드를 짠다. 2. 삽입 후 정렬 - 1) int [] + A..

문제 N개의 정수 A [1], A [2], …, A [N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A [1], A [2], …, A [N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다. 출력 M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다. 문제 접근 방법 이번 문제는 첫 번째 입력으로 수의 집합이 주어지고, 두 번째 입력으로 검색할 수의 집합이 주어진다. 따라서 처음..

문제 APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정의한다. 해시 함수는 무궁무진한 응용 분야를 갖는데, 대표적으로 자료의 저장과 탐색에 쓰인다. 이 문제에서는 여러분이 앞으로 유용하게 쓸 수 있는 해시 함수를 하나 가르쳐주고자 한다. 먼저, 편의상 입력으로 들어오는 문자열에는 영문 소문자(a, b, ..., z)로만 구성되어있다고 가정하자. 영어에는 총 26개의 알파벳이 존재하므로 a에는 1, b에는 2, c에는 3, ..., z에는 26으로 고유한 번호를 부여할 수 있다. 결과적으로 우리는 하나의 문자열을 수열로 변환할 수 있다. 예를 들어서 문자열 "abba"..