Kwin's Development Diary.

문제 수직선 위에 N개의 좌표 X1, X2,..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2,..., XN에 좌표 압축을 적용한 결과 X'1, X'2,..., X'N를 출력해보자. 입력 첫째 줄에 N이 주어진다. 둘째 줄에는 공백 한 칸으로 구분된 X1, X2,..., XN이 주어진다. 1 ≤ N ≤ 1,000,000 -109 ≤ Xi ≤ 109 출력 첫째 줄에 X'1, X'2,..., X'N을 공백 한 칸으로 구분해서 출력한다. 문제 접근 방법 이번 문제는 입력된 수의 크기 순위를 0부터 매겨 수를 압축하여 출력하는 문제이다. 따라서, 숫자를 정렬하여 해당 숫자가 입력된 수..

서론 정말 시간이 빠르다. 풀릴 것 같지 않던 날씨가 점점 풀리고 옷차림도 이전에는 두 겹 세 겹 껴입었다면 이제는 한 겹만 입어도 해가 따스한 날에는 땀이 나기 시작한다. 이번 기간에는 크고 작은 일이 있었다. 사고를 치기도 했고, 분대장도 달았고, 하여간 정말 정신없는 바쁜 기간을 보내고 있다. 지금은 게다가 훈련 기간이라 하루에 1문제를 푸는 것조차 버겁다. 숙영을 하고 오면 아예 공부할 시간이 하나도 없고 최근에는 피곤해서 개인 정비 시간에 곯아떨어지기 일쑤다. 본론 이번 기간에는 훈련으로 인한 공백이 있다. 그러나 이를 제외한 나머지 날은 하루에 한 문제씩 꼬박꼬박 열심히 채워나갔다. 이제 슬슬 골드 상위 티어 문제를 접하다 보니 새로운 자료구조를 접하기보다는 이전에 나왔던 자료구조를 이용하여,..

문제 절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다. 배열에 정수 x (x ≠ 0)를 넣는다. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러 개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -2^31보다 크고, 2^31보다 작다. 출력 입력에서 0이 주어진..

문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 1 ≤ N ≤ 100,000 1 ≤ M ≤ 100,000 1 ≤ i ≤ j ≤ N 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다. 문제 접근 방법 이번 문제는 누적 합 문제인데 개인적으로 다이나믹 프로그래밍 문제와 같다고 생각한다. 누적 합을 저장할 배열을 n+1칸만큼 선언해주고, 1번 인덱스부터 n번 인덱스까지 [idx] =[idx-1] + 입력된 수 해주..

문제 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1 ×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다. 아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다. 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄..

문제 선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다. 함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다. 배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다. 각 테스트 케이..

벨만-포드 알고리즘(Bellman-Ford Algorithm) : 음수인 가중치가 포함되어 있는 그래프에서 최단 거리를 구하는 알고리즘 음수 간선이 존재하지 않는다면 [알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm) - JAVA / 자바를 사용하여 문제를 해결하는 것이 실행 시간이 더 빠르다. 특징 ① 음수인 사이클을 찾을 수 있다 ② 매번 모든 간선을 확인하기에 연산 시간이 느리다 알고리즘 ① 출발 노드 설정 ② 최단 거리를 저장할 배열을 초기화 ③ 전체 간선을 하나씩 확인 ④ 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신 ⑤ 모든 노드에 연결되어 있는 모든 간선을 확인할 때까지 ③ ~ ④반복수행 ⑤-1 이때, 마지막 반복에서 최단 거리 테이블이 갱신된다면..

0-1 너비 우선 탐색 (0-1 Breath First Search, 0-1 BFS) : 가중치가 0과 1만 존재하는 그래프에서 최단 경로를 찾는 알고리즘 [알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm) - JAVA / 자바를 사용하여 풀 수도 있는 문제이지만, 가중치가 0과 1만 존재하는 그래프라면 0-1 BFS 알고리즘이 보다 효율적으로 문제풀이가 가능하다. 특징 ① 큐(Queue) 대신 덱(Deque)을 사용 ② 가중치가 0과 1만 존재할 때 사용 알고리즘 1. 덱(Deque)의 front에서 이동할 다음 경로를 꺼낸다. 2. 현재 위치에서 연결된 다음 경로를 탐색한다. 3. if(출발 지점부터 현재 위치까지 누적된 가중치 + 다음 경로와 연결된 간선의 가중치 < 다음 경로까지..

문제 비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오. add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다. remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다. check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20) toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20) all: S를 {1, 2,..., 20}으로 바꾼다. empty: S를 공집합으로 바꾼다. 입력 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산..

문제 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+둘째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다. 듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다. 출력 듣보잡의 수와 그 명단을 사전 순으로 출력한다. 문제 접근 방법 이번 문제는 들도 못한 사람의 명단과 보도 못한 사람의 명단에 둘 다 포함되어 있는..