분류 전체보기
-
[백준] 17364번 대회문제 풀이 2020. 8. 11. 20:10
17364 대회 문제형섭이는 세계에서 고작 K번째로 프로그래밍을 잘하지만, 최대한 많은 프로그래밍 대회에서 우승하여 자신의 이름을 알리고 싶어한다. 형섭이가 프로그래밍 대회에 참가하면 자기보다 잘하는 사람에게는 항상 지고 자기보다 못하는 사람은 항상 이긴다. 즉, 형섭이가 프로그래밍 대회에서 우승하려면 형섭이보다 잘하는 사람이 대회에 참가하지 않아야 하며 그런 대회에서는 형섭이가 항상 우승한다.전세계에서는 총 N개의 프로그래밍 대회가 개최되며 각 대회는 Si일차부터 Ei일차까지 열린다. 대회가 열리는 장소가 다르므로 어느 누구라도 기간이 겹치는 대회는 동시에 참가할 수 없다. 형섭이는 자기보다 잘하는 K-1명의 사람들이 어떤 대회에 참가하는지 미리 알 수 있다. 형섭이는 K-1명이 참가하지 않는 대회들을..
-
[백준] 6549번 히스토그램에서 가장 큰 직사각형문제 풀이 2020. 8. 10. 21:25
6549 히스토그램에서 가장 큰 직사각형 문제히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오. 입력입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 ..
-
피사노 주기알고리즘 2020. 8. 9. 21:47
피보나치- 개념 : F0 = 0 , F1 = 1일때 Fn = Fn-1 + Fn-2- 구현 방법 1. 재귀적 방법 : O(2^n) 2. dp 방법 (= memoization 방법) : O(n) 3. 피사노 주기 피사노 주기(Pisano period) - 개념 : 피보나치 수를 어떤 수 K로 나눌 때, 나머지는 항상 주기를 가지게 되는데 이를 피사노 주기라고 한다. ex) 피보나치 수를 3으로 나누었을때, 주기의 길이는 8 N 0 1 2 3 4 5 6 7 89101112131415 Fn 0 1 1 2 3 5 8 13 21 34 55 89 144 233377 610 PP 0 1 1 2 0 2 2 1 0 1 1 2 0 2 2 1 - 성질 : 주기의 길이를 P라고 하면 N번째 피보나치 수를 M으로 나눈 나머지는 ..
-
[백준] 2933번 미네랄문제 풀이 2020. 8. 7. 17:29
2933번 미네랄 문제창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다.동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다. 각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다.창영은 동굴의 왼쪽에 서있고, 상근은 오른쪽에 서있다. 두 사람은 턴을 번갈아가며 막대기를 던진다. 막대를 던지기 전에 던질 높이를 정해야 한다. 막대는 땅과 수평을 이루며 날아간다.막대가 날아가다가 미네랄을 만나면, 그 칸에 있는 미네랄은 모두 파괴되고 막대는..
-
[백준] 11066번 파일합치기문제 풀이 2020. 8. 6. 19:05
11066 파일 합치기 문제소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산하시오.예를 들어, C1, C2, C3, C4가 연속적인 네 개의 장을 수록하고 있는 파일이고, ..
-
[백준] 10830번 행렬 제곱문제 풀이 2020. 8. 5. 19:21
10830번 행렬제곱 문제크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. 입력첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000)둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다. 출력첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다. 풀이)B의 범위가 크기 때문에 하나씩 곱해보는 A*A*A..*A 이런식으로 계산하면 시간초과가 나는 문제이다. 지수 법칙을 생각해서 풀어야 하는 문제다. 지수 법칙을 이용해 분할정복(divide and co..
-
[백준] 3197번 백조의 호수문제 풀이 2020. 8. 4. 18:08
3197 백조의 호수 문제두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.호수는 가로로 R, 세로로 C만큼의 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성한다.입력입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.각 R줄 동안 C만큼의 문자열이 주어진다.'.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간..
-
[백준] 2942번 퍼거슨과 사과문제 풀이 2020. 8. 3. 19:16
2942번 퍼거슨과 사과 문제맨체스터 유나이티드의 감독 퍼거슨은 빨간 사과를 R개, 초록 사과를 G개 가지고 있다. 훈련장에 있는 선수들 중 몇 명에게 나누어 주려고 한다. 단, 선수들이 서로 같은 개수의 사과를 받지 못하면 경기력 저하가 나타날 수 있으므로 모든 선수에게 같은 개수를 주려고 한다. 퍼거슨 감독은 사과를 싫어한다. 따라서 사과가 남으면 안 된다.예를 들어, 퍼거슨이 빨간 사과를 4개, 초록 사과를 8개 가지고 있다면, 다음과 같이 세가지 방법으로 나누어 줄 수 있다선수 1명에게 빨간 사과 4개와 초록 사과 8개를 줄 수 있다선수 2명에게 빨간 사과 2개와 초록 사과 4개를 각각 줄 수 있다선수 4명에게 빨간 사과 1개와 초록 사과 2개를 각각 줄 수 있다.퍼거슨이 사과를 나누어 주는 방법..