CodeDrive

문제:

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K무게까지의 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력:

첫 줄에 물품의 수 N(1<=N<=100)과 준서가 버틸 수 있는 무게 K(1<=K<=100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1<=W<=100,000)와 해당 물건의 가치 V(0<=V<=1,000)가 주어진다.

입력으로 주어진느 모든 수는 정수이다.

출력:

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

풀이방법:

knapsack의 가장 기본적인 문제다. dp를 사용해서 간단하게 풀었다.

문제링크:

https://www.acmicpc.net/problem/12865

문제:

크기가 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의 최대 크기가 100,000,000,000인 만큼 효율적인 계산 방법이 필요한 문제다. 따라서 다음과 같은 규칙에 의해서 계산을 한다.

A^N일 때,

if N이 짝수라면, (A^2)^(N/2)로 수정한다.

if N이 홀수라면, (A^(N-1))*A로 수정하고, A는 answer에 곱한다.

N이 1이 될 때까지 위를 반복하고, 1이면 그 때의 A를 answer에 곱한다.

위와 같이 계산을 한다면 지수가 log2단위로 줄어들기 때문에 최대 100,000,000,000번 연산이 최대 36번으로 줄어들게 될 것이다. 

문제링크:

https://www.acmicpc.net/problem/10830

문제:

원룡이는 한 컴퓨터 보안 회사에서 일을 하고 있다. 그러던 도중, 원룡이는 YESWOA.COM 으로부터 홈페이지 유저들의 비밀키를 만들라는 지시를 받았다. 원룡이는 비밀 키를 다음과 같은 방법으로 만들었다.

개인마다 어떤 특정한 소수 p와 q를 주어 두 소수의 곱 pq를 비밀 키로 두었다. 이렇게 해 두면 두 소수 p,q를 알지 못하는 이상, 비밀 키를 알 수 없다는 장점을 가지고 있다.

하지만 원룡이는 한 가지 사실을 잊고 말았다. 최근 컴퓨터 기술이 발달함에 따라, 소수가 작은 경우에는 컴퓨터로 모든 경우의 수를 돌려보아 비밀 키를 쉽게 알 수 있다는 것이다.

원룡이는 주성조교님께 비밀 키를 제출하려던 바로 직전에 이 사실을 알아냈다. 그래서 두 소수 p,q 중 하나라도 K보다 작은 암호는 좋지 않은 암호로 간주하여 제출하지 않기로 하였다. 이것을 손으로 직접 구해보는 일은 매우 힘들 것이다. 당신은 원룡이를 도와 두 소수의 곱으로 이루어진 암호와 K가 주어져 있을 때, 그 암호가 좋은 암호인지 좋지 않은 암호인지 구하는 프로그램을 작성하어야 한다.

입력:

암호 P(4<=P<=10^100)와 K (2<=K<=10^6)이 주어진다.

출력:

만약에 그 암호가 좋은 암호이면 첫째 줄에 GOOD을 출력하고, 만약에 좋지 않은 암호이면 BAD와 소수 r을 공백으로 구분하여 출력하는데 r은 암호를 이루는 두 소수 중 작은 소수를 의미한다.

풀이방법:

 n보다 작은 소수를 찾아서 이를 P에다가 나눠본다. 이 때 나눠진다면 좋지 못한 암호이기 때문에 BAD와 그 수를 출력하면 된다. 이 때, K가 최대 10^6까지 가능하기 때문에 소수를 구하는 최적의 알고리즘이 필요할 것이라고 생각했고, 가장 효율적인 소수 알고리즘 중 하나인 에라토스테네스의 체를 사용했다.

 길이가 K이고 값들이 1인 배열을 만들었고, 에라토스테네스의 체를 사용해서 소수를 구했다. 에라토스테네스의 체를 간단히 설명하면 한 소수 n의 배수들은 이 소수 n로 다 나눠질 것이기 때문에 소수가 아니라는 것이다.

 따라서 해당하는 인덱스의 배열 값이 1이고, 소수라면 그 배수들의 배열값들을 다 0으로 만들어준다. 그리고 추후 탐색을 편하게 하기 위해서 인덱스를 answer 리스트에 담아둔다.

 이렇게 하면 answer에는 소수만 남게 되고, 이를 P에다가 나눠보면서 좋은 암호인지 판단한다.

문제링크:

https://www.acmicpc.net/problem/1837

문제:

어떤 숫자 n이 자신을 제외한 모든 약수들의 합과 같으면, 그 수를 완전수라고 한다.

예를 들어 6은 6 = 1 + 2 + 3 으로 완전수이다.

n이 완전수인지 아닌지 판단해주는 프로그램을 작성하라.

입력:

입력은 테스트 케이스마다 한 줄 간격으로 n이 주어진다. (2 < n < 100,000)

입력의 마지막엔 -1이 주어진다.

출력:

테스트케이스마다 한줄에 하나씩 출력해야 한다.

n이 완전수라면, n을 n이 아닌 약수들의 합으로 나타내어 출력한다. (예제 출력 참고).

이때, 약수들은 오름차순으로 나열해야 한다.

n이 완전수가 아니라면 n is NOT perfect. 를 출력한다.

풀이방법:

약수들을 찾는 것은 어렵지 않으나 출력 요건을 주의 깊게 맞춰야 하는 문제인 것 같다.

약수들을 찾는 것은 브루트포스 방법으로 2부터 다 나눠보면서 나머지가 없는 값을 찾으면 된다. 이 때, 조금이라도 시간을 줄이기 위해서 n까지 다 나눠보는 것이 아닌 n//2-1까지 나눠보도록 했다. 이렇게 약수들을 모두 찾은 다음에 중복을 제거한 다음에 정렬을 했다. (중복은 제곱수를 위해 제거, 9와 같은 경우 1,3,3과 같이 들어가 있을 것)

약수들의 합이 n과 같으면 완전수이므로 출력 조건에 맞춰서 출력을 하고, 다르면 n is NOT perfect.로 출력한다.

100,000미만의 완전수는 6, 28, 496, 8128만 있으니 확인 후 제출하면 된다.

문제링크:

https://www.acmicpc.net/problem/9506

문제:

풀이방법:

문자열을 잘 parsing할 수 있는지와, 어느 시점에 최대가 되는지 알아야 하는 문제다.

 우선 문자열을 파싱하기 위해서 splitTime이라는 함수를 만들었고, 날짜, 시간, 처리시간은 공백으로 구분되어 있기 때문에 split해주고, 날짜는 항상 2016년 9월 15일로 고정되어 있기 때문에 사용하지 않는다. 시간은 다시한번 :로 구분되어 있기 때문에 split해주고 1초간 처리하는 요청의 최대 개수를 알아야 하기 때문에 시간을 1초 단위로 만들어준다. 처리시간은 초 단위로 나오고 항상 s로 끝나기 때문에 이를 제거한 다음에 float으로 만들어 준다. 그리고 처리시간은 시작시간과 끝시간을 포함하기 때문에 배열로 반환을 할 때 시작시간에 0.001만큼 더하도록 한다.

 보통 최대 개수인 부분은 시작시간이나 끝시간에서 발생하게 된다. 이 시간들을 기준으로 처리해야하는 데이터가 생성되거나 사라지기 때문이다. (배열의 모든 시간을 탐색해도 좋지만 시간이 오래 걸릴 것이다.) 각 트래픽별의 시작시간과 끝나는 시간을 기준으로 트래픽의 갯수를 세서 최대 갯수를 파악한다.

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/17676?language=python3

문제:

풀이방법:

여러가지 푸는 방법이 있겠지만, 가장 단순하면서 쉬운 방법을 사용하고자 한다. 브루트 포스 방식으로 가능한 모든 경우의 수를 만들고 그 중에서 해당하는 조건을 찾는 방법으로 했다.

 우선 python의 itertools의 permutation을 사용해서 모든 경우의 수를 만든다. 그리고 각 조건에 맞는지 확인을 하는데, 조건의 길이와 다르면 바로 False로 가도록 하고, 길이가 같다면 그 때 조건을 비교하도록 한다.

 이렇게 조건에 맞는 경우를 찾았다면 중복을 방지하기 위해서 set으로 값을 넣도록 한다.

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/64064

문제:

 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.

 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다.

이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을 회색으로 표시하면 다음과 같다.

물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다.(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다.)

또한 위와 같은 지역에서 높이가 6이하인 지점을 모두 잠기게 만드는 많은 비가 내리면 물에 잠기지 않는 안전한 영역은 아래 그림에서와 같이 네 개가 됨을 확인할 수 있다.

이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다. 위의 예와 같은 지역에서 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5임을 알 수 있다.

어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오.

입력:

첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1 이상 100 이하의 정수이다.

출력:

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

풀이방법:

 bfs를 사용해서 풀수는 있을 것 같지만 dfs를 사용해서 풀었다. 재귀의 깊이가 얼마나 될지 모르고, deepcopy를 사용하기 위해서 sys와 copy를 import 했다.

 지역의 높이 정보 입력값을 받으면서 max 연산을 취해서 지역 내에 가장 높은 영역이 값을 얻도록 했다. (뒤에서 for 반복문에서 사용하기 위해) 입력을 다 받은 뒤에는 이 높이 정보를 deepcopy한 뒤 현재 rain에 맞게(1부터 시작한다.) 값을 빼주고 만약 0 이하로 떨어지게 된다면 0으로 만들고 나머지는 그대로 냅뒀다.

 이제 이렇게 비에 잠긴 영역들을 표시했으니 dfs를 사용해서 살아있는 영역의 개수를 구한다. 각 점을 탐색하며 0이 아닌 곳에서 dfs 탐색을 시작하며 탐색 되는 곳은 0으로 만들어줘서 방문했음을 알려준다. 이렇게 반복해서 하면 영역의 개수를 구할 수 있고 max 연산을 통해 최댓값을 구한다.

문제링크:

https://www.acmicpc.net/problem/2468

문제:

어떤 파일 시스템에는 디스크 공간이 파일의 사이즈와 항상 같지는 않다. 이것은 디스크가 일정한 크기의 클러스터로 나누어져 있고, 한 클러스터는 한 파일만 이용할 수 있기 때문이다.

예를 들어, 클러스터의 크기가 512바이트이고, 600바이트 파일을 저장하려고 한다면, 두 개의 클러스터에 저장하게 된다. 두 클러스터는 다른 파일과 공유할 수 없기 때문에, 디스크 사용 공간은 1024바이트가 된다.

파일의 사이즈와 클러스터의 크기가 주어질 때, 사용한 디스크 공간을 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 파일의 개수 N이 주어진다. N은 1,000보다 작거나 같은 자연수이다. 둘째 줄에는 파일의 크기가 공백을 사이에 두고 하나씩 주어진다. 파일의 크기는 1,000,000,000보다 작거나 같은 음이 아닌 정수이다. 마지막 줄에는 클러스터의 크기가 주어진다. 이 값은 1,048,576보다 작거나 같은 자연수이다.

출력:

첫째 줄에 사용한 디스크 공간을 출력한다.

풀이방법:

파일을 클러스터에 넣으려고 할 떄 크게 3가지 경우가 발생한다.

1. 한 파일의 크기가 한 클러스터의 크기보다 큰 경우

2. 한 파일의 크기가 한 클러스터의 크기와 같은 경우

3. 한 파일의 크기가 한 클러스터의 크기보다 작은 경우

그리고 위 3가지 case는 몫과 나머지를 통해서 구할 수 있다.

파일사이즈를 클러스터의 크기로 나눴을 때, 몫이 1보다 커지게 된다면 1의 케이스에 해당하며 몫만큼 클러스터의 개수를 준비하고 나머지가 있을 경우 하나 더 준비하면 된다.

그리고 몫이 0이라면 나머지가 있을 경우에는 한 개를 준비하면 되고, 나머지가 없다면 준비안하면 된다.

몫과 나머지를 구할 수 있는 divmod를 사용해서 알고리즘을 구현하면 된다.

문제링크:

https://www.acmicpc.net/problem/1350

문제:

강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다.

스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다.

보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베이터는 버튼이 2개밖에 없다. U버튼은 위로 U층을 가는 버튼, D버튼은 아래로 D층을 가는 버튼이다.(만약, U층 위, 또는 D층 아래에 해당하는 층이 없을 때는, 엘리베이터는 움직이지 않는다)

강호가 G층에 도착하려면, 버튼을 적어도 몇 번 눌러야 하는지 구하는 프로그램을 작성하시오. 만약, 엘리베이터를 이용해서 G층에 갈 수 없다면, "use the stairs"를 출력한다.

입력:

첫째 줄에 F, S, G, U, D가 주어진다. (1<=S,G<=F<=1000000, 0<=U,D<=1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다.

출력:

첫째 줄에 강호가 S층에서 G층으로 가기 위해 눌러야 하는 버튼의 수의 최솟값을 출력한다. 만약, 엘리베티어로 이동할 수 없을 때는 "use the stairs"를 출력한다.

풀이방법:

 BFS로 경우의 수를 카운팅하면서 최소의 값을 찾을 수 있다. 우선 S와 G가 같으면 버튼을 누를 필요가 없기 때문에 0으로 답을 출력하도록 했다. 이제 이외의 경우에 대해서 BFS를 사용하기 위해, 초기 시작 층인 S로 state를 초기화 했고, 중복방문을 제거하기 위해서 visited를 초기화 했다.

 이제 갈 수 없는 경우( 0층, F층 초과)만 있을 때까지 계속 반복하기 위해서 while을 len(state) 초기화 했고, 현재 층을 s라고 할 때 다음과 같은 경우에만 이동하도록 한다.

1. s+U가 F층 이하이고, 방문하지 않은 곳이라면

2. s-F가 1층 이상이고, 방문하지 않은 곳이라면

이를 반복하면서 G가 나타나거나, 1,2 케이스가 하나도 없을 떄까지 반복해서 답을 구하도록 한다.

문제링크:

https://www.acmicpc.net/problem/5014

문제:

상근이는 덧셈과 나눗셈을 엄청나게 못한다. 이런 상근이를 위해 정인이는 상근이에게 다음과 같은 문제를 냈다.

정인이는 양의 정수 A,B,C,D로 이루어진 2*2 표를 그렸다.

위와 같은 표가 있을 때, 표의 값은 A/C + B/D 이다.

상근이는 표를 몇 번 돌리면 표의 값이 최대가 되는지 궁금해졌다.

표는 90도 시계방향으로 돌릴 수 있다.

문제 상단의 표를 1 번 회전시키면 다음과 같다.

2번 회전 시키면 다음과 같이 된다.

표에 쓰여 있는 A,B,C,D가 주어졌을 때, 표를 몇 번 회전시켜야 표의 값이 최대가 되는지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 A와 B가 공백으로 구분되어 주어진다. 둘째 줄에 C와 D가 공백으로 구분되어 주어진다. 모든 수는 100보다 작거나 같은 양의 정수이다.

출력:

첫째 줄에 표를 몇 번 돌려야 표의 값이 최대가 되는지 출력한다. 만약, 그러한 값이 여러개라면 가장 작은 값을 출력한다.

풀이방법:

사실 경우의 수가 4개 밖에 없기 때문에 0,90,180,270도 순으로 배열을 구성하도록 했다.

그리고 max 값의 index를 찾도록 했는데, 최대인 값이 여러개라고 하더라도 index는 가장 먼저 나오는 index를 반환하기 때문에 출력조건에 위배되지 않는다.

문제링크:

https://www.acmicpc.net/problem/2863