코딩은 마라톤

해시 현대 사회에서 데이터를 저장하거나 탐색할 때 가장 쉽게 떠올릴 수 있는 방법은 "순차 탐색" 이다. 가장 확실하게 찾을 수 있지만 최악의 경우 탐색할 때마다 모든 데이터를 살펴봐야하기 때문에 효율적이진 않다. 이 방법을 개선하기 위해 찾아야 할 값이 어디에 있는지 알아낼 방법이 필요하다. 즉, 어떠한 값이 저장되는 위치를 어떤 규칙으로 정할 수 있으면 탐색 필요 없이 바로 데이터를 찾을 수 있다. 이러한 자료구조를 "해시(Hash)"라고 한다. 해시의 개념 해시는 해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조이다. 키를 활용해 데이터 탐색을 빠르게 할 수 있다. 해시의 특징 1. 해시는 단방향으로 동작한다. 키를 통해 값을 찾을 수 있지만 ..

1. 정의 동적계획법 (DP) 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식 Memoization 기법을 사용함 Memoization : 프로그램 실행 시 이전 계산 값을 저장하여 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술 분할 정복 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘 하향식 접근법으로, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식 일반적으로 재귀함수로 구현한다. 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않는다...

[Silver IV] 30 - 10610 문제 링크 성능 요약 메모리: 29736 KB, 시간: 600 ms 분류 그리디 알고리즘, 수학, 정수론, 정렬, 문자열 문제 설명 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다. 미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. 입력 N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다. 출력 미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라. 문제풀이 이 문제는 30의 배수를 만족하는 가장 큰 수를 만들..

[Gold IV] 카드 정렬하기 - 1715 문제 링크 성능 요약 메모리: 113076 KB, 시간: 1000 ms 분류 자료 구조, 그리디 알고리즘, 우선순위 큐 문제 설명 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 2..

[Silver III] 주유소 - 13305 문제 링크 성능 요약 메모리: 182580 KB, 시간: 1124 ms 분류 그리디 알고리즘 문제 설명 어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다. 처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터..

[Silver V] 수들의 합 - 1789 문제 링크 성능 요약 메모리: 17732 KB, 시간: 208 ms 분류 그리디 알고리즘, 수학 문제 설명 서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까? 입력 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. 출력 첫째 줄에 자연수 N의 최댓값을 출력한다. 문제 풀이 자연수 s를 입력 받는다. 위의 식에서 n을 1부터 계속 1씩 증가시키면서 반복문을 수행한다. 만약 합이 입력 받은 s보다 커질 경우를 확인해야 한다. (작은 경우를 확인할 경우, 만약 191이 입력될 경우 출력은 19가 아닌 20이 n이 되기 때문이다. 따라서 나는 합이 s보다 커질 경우, n에 1을 뺀 값을 출력하고 반복문을..

[Silver IV] 로프 - 2217 문제 링크 성능 요약 메모리: 110084 KB, 시간: 1088 ms 분류 그리디 알고리즘, 수학, 정렬 문제 설명 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를..

[Silver IV] 보물 - 1026 문제 링크 성능 요약 메모리: 17876 KB, 시간: 224 ms 분류 그리디 알고리즘, 수학, 정렬 문제 설명 옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다. 길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자. S = A[0] × B[0] + ... + A[N-1] × B[N-1] S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다. S의 최솟값을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N..