유제필의 개발 블로그

요약 해시란 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑한 값을 말함 해시 테이블이란, 키와 밸류를 한 쌍으로, 해싱 함수에 따라 효율이 달라짐 충돌이란 데이터를 넣어야 할 주소에 이미 다른 값이 저장되어 있는 현상을 말하며 충돌 시 체이닝 기법을 적용함 체이닝이란 해시 함수가 충돌이 발생하면, 각 데이터를 해당 주소에 있는 링크드 리스트로 삽입하여 문제를 해결하는 기법을 말함 체이닝의 성능 개선으로 선형 탐사, 제곱 탐사, 이중 해싱 등이 있음 제일 좋은 성능은 이중 해싱으로, 해싱 함수를 두 가지를 두고, 충돌 시 두 번째 해싱 함수를 사용 해시(Hash) 해시란 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑(Mapping)한 값이다. 즉, 해시는 데이터를 입력받아 ..

2164번: 카드 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 256 MB 77444 38048 26914 48.262% 문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ..

먼저 아래와 같은 큐 구조가 있다. 유선순위 큐의 각 요소는 우선순위를 가지고, 이들 요소의 우선순위 오름차순으로 연결된다. 이 예제에서는 낮은 값의 데이터들이 높은 우선순위를 가진다. 위 큐에서 20의 값을 넣는 과정을 살펴보면, 먼저 첫 요소부터 순서차적으로 우선순위를 비교한다. 20은 2와 17보다 크고 22보다 작으므로 17과 22사이에 삽입되어야 한다. 우선순위 큐의 제거 우선순위 큐의 제거 연산은 가장 앞 요소인 전단만 제거하면 되므로, 간단하다. 힙을 이용한 우선순위 큐 구현 방법 우선순위 큐를 구현하기 위해 힙을 이용한다. 여기서 힙(Heap)은 자유 저장소의 힙이 아닌, 힙 순서 속성(Heap Order Priority)을 만족하는 완전 이진트리를 말한다. 완전 이진 트리란 최고 깊이(잎..

11004번: K번째 수 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 512 MB 45258 15136 10327 40.224% 문제 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다. 둘째에는 A1, A2, ..., AN이 주어진다. (-109 ≤ Ai ≤ 109) 출력 A를 정렬했을 때, 앞에서부터 K번째 있는 수를 출력한다. 예제 입력 1 복사 5 2 4 1 2 3 5 예제 출력 1 복사 2 정답 #include #include #include using namespace std; int main() { cin.t..

11651번: 좌표 정렬하기 2 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 256 MB 52134 33823 28794 67.222% 문제 2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. 출력 첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다. 예제 입력 1 복사 5 0 4 1 2 1 -1 2 2 3 3 예제 출력 1 복사 1 -1 1 2..

11650번: 좌표 정렬하기 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 256 MB 94590 44754 34606 48.008% 문제 2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. 출력 첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다. 예제 입력 1 복사 5 3 4 1 1 1 -1 2 2 3 3 예제 출력 1 복사 1 -1 1 1 2..

2164번: 카드 시간 제한메모리 제한제출정답맞힌 사람정답 비율 0.5 초 (추가 시간 없음) 256 MB 55454 30423 25704 56.164% 문제 정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 여덟 가지이다. push_front X: 정수 X를 덱의 앞에 넣는다. push_back X: 정수 X를 덱의 뒤에 넣는다. pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다. pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 덱에 들어있는 정수의 개수를 출력한..

2164번: 카드 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 (추가 시간 없음) 128 MB 65842 33911 27706 51.633% 문제 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4..

큐 2 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 (하단 참고) 512 MB 57287 17737 14385 31.586% 문제 정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 여섯 가지이다. push X: 정수 X를 큐에 넣는 연산이다. pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 큐에 들어있는 정수의 개수를 출력한다. empty: 큐가 비어있으면 1, 아니면 0을 출력한다. front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들..

1929번: 수 찾기 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 128 MB 173155 51786 34391 29.842% 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을 출력한다. 예제 입력..