전체 보기

    [11279번] 최대 힙
    Algorithm/백준 문제 풀이

    [11279번] 최대 힙

    백준 11279번: 최대 힙 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 2^31보다 작다. www.acmicpc.net '힙(Heap)'이라는 자료구조를 이용하여 푸는 문제입니다. 힙은 유명한 자료구조 중 하나라고 할 수 있죠. 유용합니다. 힙(Heap)은 다른 말로 '우선순위 큐(Priority_queue)'라고도 할 수 있습니다. 그 이유는 가장 높은 value, 즉 가치가 높으면 높을수록 먼저 pop되기 때문에 그런 것입..

    [1065번] 한수
    Algorithm/백준 문제 풀이

    [1065번] 한수

    백준 1065번: 한수 1065번: 한수 어떤 양의 정수 X의 자리수가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. www.acmicpc.net 단순한 함수 구현 문제입니다. 사실 구하는 수들의 범위가 매우 크다면 접근 방식의 차이가 생겼겠지만, 이 문제에서는 1,000까지만 그 수를 구하면 되기 때문에 최악의 시간 복잡도를 구해도 $O(N)$이기 때문에 1초라는 시간제한을 넘을 일은 없습니다. 결과적으로 각 digits을 분해하고 그 차이를 계산해 한수인지 아닌지를 판단하는 함수를 만들고 for문을 통해 입력받은 수까지의 한수의 개수..

    [15953번] 상금 헌터
    Algorithm/백준 문제 풀이

    [15953번] 상금 헌터

    백준 15953번: 상금 헌터 15953번: 상금 헌터 첫 번째 줄에 제이지가 상상력을 발휘하여 가정한 횟수 T(1 ≤ T ≤ 1,000)가 주어진다. 다음 T개 줄에는 한 줄에 하나씩 제이지가 해본 가정에 대한 정보가 주어진다. 각 줄에는 두 개의 음이 아닌 정수 a(0 ≤ a ≤ 100)와 b(0 ≤ b ≤ 64)가 공백 하나를 사이로 두고 주어진다. www.acmicpc.net 2018년도에 열린 카카오 페스티벌 예선 A번 문제입니다. 각 케이스에 대해 받게 될 상금의 총액을 각각 출력하면 되는 문제입니다. 다른 사람들이 한 풀이를 보니 예상한 대로 각 순위가 끊기는 부분을 수식을 통해 알아내고 상금을 더해주는 형식을 취했더군요. 저는 그렇게 해도 물론 되지만 좀 더 빠르고 쉽게 풀고 싶어서 넉넉한..

    [11728번] 배열 합치기
    Algorithm/백준 문제 풀이

    [11728번] 배열 합치기

    백준 11728번: 배열 합치기 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거나 같은 정수이다. www.acmicpc.net 두 배열을 입력받고 이 둘을 합친 후 정렬된 결과를 출력하면 되는 문제입니다. 저는 이 문제를 STL을 사용하여 풀길 원했고 그래서 이용한 것이 헤더의 std::merge, std::sort 함수 헤더의 std::vector std::merge는 매우 안정성이 높고 빠릅니다. 그래서 두 배열을 합치는 데에 사용했고, vector를 사용해 합친 후 정렬을 수행한 결과를 저장하도록 ..

    [문제집] baekjoon - N과 M
    Algorithm/백준 문제 풀이

    [문제집] baekjoon - N과 M

    이번에는 하나의 문제집에 대한 문제들을 전체적으로 다뤄보도록 하겠습니다. 만든 사람은 'baekjoon'님으로 BOJ 사이트 이름만 봐도 얼마나 대단하신 분인지 알 수 있죠. ㅎㅎ 시작하기에 앞서 'N과 M'이라는 이 문제집은 전체적으로 하나의 알고리즘을 기준으로 풀게 됩니다. 그 알고리즘이란 여러분들도 익히 들어보셨을 만한 DFS(Depth-First Search)입니다! 이 개념은 왜 나왔느냐 하면은 State-Space tree라는 것에서 이용하기 위해서 나온 것입니다. [Reference: Maximizing Rewards in Wireless Networks with Energy and Timing Constraints for Periodic Data Streams - Scientific Fig..

    [10610번] 30
    Algorithm/백준 문제 풀이

    [10610번] 30

    백준 10610번: 30 10610번: 30 문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다. 미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. 입력 N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다. 출력 미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는 www.acmicpc.net 30이라는 수를 존경하는 미르코라는 사람이 양의 정수 $N (0으로 시작하지 않는 10^5자리의 수)$을 보고 해당 자리수들을 적절히 배치하여 가장 큰 30의 배수를 찾아내는 문제..

    [10814번] 나이순 정렬
    Algorithm/백준 문제 풀이

    [10814번] 나이순 정렬

    백준 10814번: 나이순 정렬 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오. www.acmicpc.net 정렬 문제입니다. 정렬의 결과로는 두 가지가 나타날 수 있습니다. 먼저 처음 입력받은 값과 순서가 바뀔 경우와, 두 번째로 순서가 유지될 경우입니다. 모든 일에는 득실이 있기 마련이죠. 저희는 알고리즘에서 이것을 trade-off 관계라고 합니다. 마찬가지로 순서가 뒤섞인 만큼 정렬하는 데에 시간이 덜 걸릴 테고, 반대로 순서를 유지하는 만큼 시간은 더 걸릴 것입니다. 전자의 결과를 도출하는 정렬 방법에는 '합병 정렬(Mer..

    [11441번] 합 구하기
    Algorithm/백준 문제 풀이

    [11441번] 합 구하기

    백준 11441번: 합 구하기 11441번: 합 구하기 첫째 줄에 수의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에는 A1, A2, ..., AN이 주어진다. (-1,000 ≤ Ai ≤ 1,000) 셋째 줄에는 구간의 개수 M이 주어진다. (1 ≤ M ≤ 100,000) 넷째 줄부터 M개의 줄에는 각 구간을 나타내는 i와 j가 주어진다. (1 ≤ i ≤ j ≤ N) www.acmicpc.net $N ( 1 \leq N \leq 10,000 ) $개의 숫자를 입력받고, 구간을 $ M ( 1 \leq M \leq 10,000 ) $만큼 입력하면 그 사이의 수를 더한 값들을 각각 출력해주는 문제입니다. 처음에 그냥 구간만큼 for문을 사용하여 반복하면 되지 않을까를 생각했지만, 그래서는 시..

    [3047번] ABC
    Algorithm/백준 문제 풀이

    [3047번] ABC

    백준 3047번: ABC 3047번: ABC 문제 세 수 A, B, C가 주어진다. A는 B보다 작고, B는 C보다 작다. 세 수 A, B, C가 주어졌을 때, 입력에서 주어진 순서대로 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 세 수 A, B, C가 주어진다. 하지만, 순서는 A, B, C가 아닐 수도 있다. 세 수는 100보다 작거나 같은 자연수이다. 둘째 줄에는 A, B, C로 이루어진 세 글자가 주어지며, 이 순서대로 출력하면 된다. 출력 주어진 세 수를 주어진 출력 순서대로 출력하면 www.acmicpc.net A는 제일 작은 수, B는 중간에 오는 수, C는 제일 큰 수를 나타냅니다. 저는 세 알파벳이 크기가 1씩 차이 나기 때문에 이를 이용하기로 했습니다. 3개의 숫자를 받아서 정렬을 ..

티스토리툴바