본문 바로가기

전체 글

 (118)
[Baekjoon 1197] 최소 스패닝 트리 - JAA [Gold IV] 최소 스패닝 트리 - 1197 문제 링크 성능 요약 메모리: 49428 KB, 시간: 612 ms 분류 최소 스패닝 트리, 그래프 이론 문제 설명 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000..
[Baekjoon 1987] 알파벳 - JAVA [Gold IV] 알파벳 - 1987 문제 링크 성능 요약 메모리: 15128 KB, 시간: 948 ms 분류 백트래킹, 깊이 우선 탐색, 그래프 이론, 그래프 탐색 문제 설명 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다. 입력 첫째 줄..
[Baekjoon 9527] 1의 개수 세기 - JAVA [Gold II] 1의 개수 세기 - 9527 문제 링크 성능 요약 메모리: 14192 KB, 시간: 124 ms 분류 비트마스킹, 수학, 누적 합 문제 설명 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라고 정의하고, 아래 식의 결과를 구하자. \[ \sum_{x=A}^{B}f(x) \] 입력 첫 줄에 두 자연수 A, B가 주어진다. $(1 ≤ A ≤ B ≤ 10^{16})$ 출력 1의 개수를 세어 출력한다. 문제 풀이 문제의 핵심은 아래와 같다. A이상 B이하의 수들을 2진수로 표현할 때 1의 개수 결과로 출력한다. A와 B의 입력 범위..
[Baekjoon 23291] 어항 정리 - JAVA [Platinum V] 어항 정리 - 23291 문제 링크 성능 요약 메모리: 16096 KB, 시간: 132 ms 분류 구현, 시뮬레이션 문제 설명 마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바닥 위에 놓여져 있다. 어항에는 물고기가 한 마리 이상 들어있다. 은 어항 8개가 바닥 위에 놓여있는 상태이며, 칸에 적힌 값은 그 어항에 들어있는 물고기의 수이다. 편의상 어항은 정사각형으로 표현했다. 어항을 한 번 정리하는 과정은 다음과 같이 이루어져 있다. 먼저, 물고기의 수가 가장 적은 어항에 물고기를 한 마리 넣는다. 만약, 그러한 어항이 여러개라면 물고기의 수..
[Baekjoon 8120] Coding of Permutations - JAVA [Gold III] Coding of Permutations - 8120 문제 링크 성능 요약 메모리: 19844 KB, 시간: 1712 ms 분류 이분 탐색, 자료 구조, 세그먼트 트리 문제 설명 Every permutation A = (a1, ..., an) of numbers 1, ..., n can be coded by a sequence B = (b1, ..., bn) in which bi equals the number of all aj such that (j ai), for i = 1, ..., n. The sequence B = (0, 0, 1, 0, 2, 0, 4) is the code of the permutation A = (1, 5, 2, 6, 4, 7, 3). ..
[Baekjoon 20921] 그렇고 그런 사이 - JAVA [Silver I] 그렇고 그런 사이 - 20921 문제 링크 성능 요약 메모리: 14776 KB, 시간: 152 ms 분류 해 구성하기, 그리디 알고리즘 문제 설명 신수동 최고의 인싸 환주는 오늘도 인기가 많다. 그 인기는 정말 대단해서 대나무숲에서는 매일 환주의 이름이 쏟아진다. 환주에게는 그 인기의 비결이 있었는데, 바로 자신이 원하는 두 명을 그렇고 그런 사이로 만들 수 있는 것이다! 환주가 그렇고 그런 사이를 만드는 방법은 다음과 같다. $1$번 사람부터 $N$번 사람까지 $N$명을 일렬로 세운다. 모든 사람에게 $1$부터 $N$까지 양의 정수 중 하나가 적힌 쪽지를 나눠준다. 쪽지에 적힌 정수는 중복되지 않는다. 서로 다른 두 사람을 골랐을 때, 왼쪽에 있는 사람이 오른쪽에 있는 사람보다 쪽지..
[Baekjoon 4307] 개미 - JAVA [Silver I] 개미 - 4307 문제 링크 성능 요약 메모리: 47540 KB, 시간: 436 ms 분류 애드 혹 문제 설명 개미 여러 마리가 길이가 lcm인 막대 위에 있다. 각 개미의 이동 속도는 모두 일정하며, 1cm/s이다. 개미가 막대의 마지막까지 걸어간다면, 개미는 그 즉시 떨어지게 된다. 또, 두 개미가 만나게 된다면, 방향을 반대로 바꾸어 걸어가게 된다. 가장 처음에 막대 상에서 개미의 위치를 알고 있다. 하지만, 개미가 어느 방향으로 움직이는 지는 알 수가 없다. 이때, 모든 개미가 땅으로 떨어질 때까지 가능한 시간 중 가장 빠른 시간과 느린 시간을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 막대의 길이와 개미의 ..
[Baekjoon 1806] 부분합 - JAVA [Gold IV] 부분합 - 1806 문제 링크 성능 요약 메모리: 23708 KB, 시간: 300 ms 분류 누적 합, 두 포인터 문제 설명 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. 출력 첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다. 문제 풀이 문제의 핵심은 시간초과가 ..

티스토리툴바