Algorithm

    [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를 이용하면 되지만 이전에 보여드..

    [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문을 통해 입력받은 수까지의 한수의 개수..

티스토리툴바