전체 보기

    [2231번] 분해합
    Algorithm/백준 문제 풀이

    [2231번] 분해합

    백준 2231번: 분해합 2231번: 분해합 문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다. 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그 www.acmicpc.net 분해합: 어떤 자연수 $N$이 있을 때, $N$과 $N$이 이루는 각 자리수의 합 자연수 하나가 주어졌을 때, 다른 자연수의 분해합을 통해 그 자연수가 만들어진다면 만들어지는 다른..

    [4195번] 친구 네트워크
    Algorithm/백준 문제 풀이

    [4195번] 친구 네트워크

    백준 4195번: 친구 네트워크 4195번: 친구 네트워크 문제 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다. 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오. 친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계 www.acmicpc.net 이전 포스팅에서 다뤘던 '유니온 파인드'에 대한 변형 문제입니다. 이번에는 각 유니온들의 root 노드들이 기존 배열에서 정수로 된 index를 이용하는 것이 아니라..

    [1717번] 집합의 표현
    Algorithm/백준 문제 풀이

    [1717번] 집합의 표현

    백준 1717번: 집합의 표현 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a www.acmicpc.net 유명한 자료구조 중 하나인 '유니온 파인드(혹은 Disjoint-Set, 상호 배타적 집합,... 등등)'를 이해하고 사용하는 문제입니다. 먼저 무슨 자료구조인지부터 알..

    [1193번] 분수찾기
    Algorithm/백준 문제 풀이

    [1193번] 분수찾기

    백준 1193번: 분수찾기 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 특정 패턴을 따르도록 배열을 이동할 때, $N$번째 칸에서는 어떤 형태의 분수가 있을까를 알아보는 '규칙 찾기' 문제입니다. 먼저 가장 눈에 띄는 특징을 살펴보면, 대각선을 세는 횟수 기준으로 홀수일 때는 분모가 1부터 커지고 짝수일 때는 분자가 1부터 커집니다. 두 번째 특징은 대각선을 세는 횟수가 분자 분모에 영향을 준다는 것입니다. 이는 찾기 쉬우므로 한 번 찾아보세요. ㅎㅎ 규칙을 찾는 문제인 만큼 특정 패턴을 알아내는 것이 중요합니다. 그 안목을 길러보도록 합시다! [소스 보기]

    [10250번] ACM 호텔
    Algorithm/백준 문제 풀이

    [10250번] ACM 호텔

    백준 10250번: ACM 호텔 10250번: ACM 호텔 문제 ACM 호텔 매니저 지우는 손님이 도착하는 대로 빈 방을 배정하고 있다. 고객 설문조사에 따르면 손님들은 호텔 정문으로부터 걸어서 가장 짧은 거리에 있는 방을 선호한다고 한다. 여러분은 지우를 도와 줄 프로그램을 작성하고자 한다. 즉 설문조사 결과 대로 호텔 정문으로부터 걷는 거리가 가장 짧도록 방을 배정하는 프로그램을 작성하고자 한다. 문제를 단순화하기 위해서 호텔은 직사각형 모양이라고 가정하자. 각 층에 W 개의 방이 있는 H 층 건물이라고 가정 www.acmicpc.net ACM 호텔에 들어오는 손님들의 방을 준비해주는 문제입니다. 손님들은 많이 걷기 싫어하므로 엘리베이터로부터 가까운 방에 배정받고 싶어 합니다. 이 문제는 간단하게 패..

    [2447번] 별 찍기 - 10
    Algorithm/백준 문제 풀이

    [2447번] 별 찍기 - 10

    백준 2447번: 별 찍기 - 10 2447번: 별 찍기 - 10 첫째 줄에 N이 주어진다. N은 항상 3의 제곱꼴인 수이다. (3, 9, 27, ...) (N=3k, 1 ≤ k < 8) www.acmicpc.net BOJ에 존재하는 별 찍기 문제 중 10번입니다. 이 문제의 가장 큰 특징은 '재귀 함수'를 이용한다는 점입니다. 즉 '분할 정복' 문제입니다. 이전 포스팅에서도 분할 정복에 대한 내용은 좀 다뤘으니 tag를 참조해 한 번 보시기 바랍니다. 저는 사실 이 문제를 예전에 몇 번 틀렸습니다. 이유는 단순히 재귀의 가장 큰 단점인 시간 초과였죠. 그래서 이를 좀 더 최적화할 방법이 필요하다가 생각했... 지만 그게 아니었습니다. 이전에 했던 "생각"은 맞았지만, "구현" 방법의 차이 때문에 쓸데없..

    [1475번] 방 번호
    Algorithm/백준 문제 풀이

    [1475번] 방 번호

    백준 1475번: 방 번호 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 구매할 스티커 세트의 총 개수를 구하는 문제입니다. 여기서 중요한 점은 6과 9는 서로 대체될 수 있다는 점입니다. 이를 고려하면서 사야할 스티커 세트의 최소 개수를 구하면 됩니다. 저는 간단하게 각 스티커(0부터 9까지)의 개수를 각각 세고 난 뒤, 6과 9를 제외한 나머지 숫자들 중 최대 개수를 찾았습니다. 그 후 6과 9의 최대 개수를 구했죠. { (6의 개수 + 9의 개수) / 2 + (6의 개수 + 9의 개수) % 2 } 그리고 나머지에서 최대와 6,9에서의 최대를 비교해서 다시 최대를 구했습니다. 남은 일은 출력하..

    [11286번] 절댓값 힙
    Algorithm/백준 문제 풀이

    [11286번] 절댓값 힙

    백준 11286번: 절댓값 힙 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다. www.acmicpc.net 이전 포스팅했던 글과 매우 유사합니다. [여기]를 참고하여 Heap(또는 priority_queue)를 이해하고 거의 같은 문제라는 것을 보시기 바랍니다. 이 문제는 조금 생각을 해봐야 합니다. 이전에 보여드렸던 MAX 혹은 min Heap과는 달리 조건이 추가된 Heap을 ..

    [1927번] 최소 힙
    Algorithm/백준 문제 풀이

    [1927번] 최소 힙

    백준 1927번: 최소 힙 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 2^31보다 작다. www.acmicpc.net 이전 포스팅했던 글과 매우 유사합니다. [여기]를 참고하여 Heap(또는 priority_queue)를 이해하고 거의 같은 문제라는 것을 보시기 바랍니다. 이번에는 min Heap을 구현하여 맞는 opration들을 수행해주면 됩니다. priority_queue Container를 이용하면 되지만 이전에 보여드..

티스토리툴바