Algorithm/백준 문제 풀이

    [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개의 숫자를 받아서 정렬을 ..

    [1431번] 시리얼 번호
    Algorithm/백준 문제 풀이

    [1431번] 시리얼 번호

    백준 1431번: 시리얼 번호 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어져 있다. 시리얼 번호는 중복되지 않는다. www.acmicpc.net 단순한 구현 문제입니다. algorithm 헤더에 포함된 sort 함수의 compare 부분의 인자를 잘 작성할 수 있는지를 물어보는 문제입니다. 이런 문제를 풀기 위해서는 STL 공부를 잘해야겠죠? 단순히 조건에 따라 compare 함수를 작성해주면 됩니다. [소스 보기]

    [11966번] 2의 제곱인가?
    Algorithm/백준 문제 풀이

    [11966번] 2의 제곱인가?

    백준 11966번: 2의 제곱인가? 11966번: 2의 제곱인가? 자연수 N이 주어졌을 때, 2의 제곱수면 1을 아니면 0을 출력하는 프로그램을 작성하시오. www.acmicpc.net 2의 제곱인지를 검사하는 문제입니다. 입력되는 값 $N$의 범위가 $ 1 \leq N \leq 2^{30} $ 이라서 int 범위 안에서 조절할 수 있다는 걸 알 수 있었습니다. 그리고 2로 계속 나누면서 feasibility를 검사하는 것은 시간 초과가 나올 것 같다는 생각이 들었습니다. 그래서 저는 문제의 제목이 2의 제곱인만큼 비트를 검사하는 것이 아닐까라고 생각했습니다. 이를 검사하기 위해 비트 연산을 사용하여 풀려했습니다. 접근법은 2의 제곱수의 특징에서 보았는데, 단 하나의 1과 나머지 0으로 이루어진 이진수가..

티스토리툴바