CodeDrive

문제:

평면상에 n개의 점이 있다. 이 점들 중에 서로 다른 두 점을 선택하면 하나의 직선이 만들어진다. 이와 같이 직선을 만들었을 때, x축 또는 y축에 평행한 직선이 몇 개나 되는지 알아내는 프로그램을 작성하시오.

입력:

첫째 줄에 n(1<=n<=100,000)이 주어진다. 다음 n개의 줄에는 각 점의 좌표가 int 범위에서 주어진다. 만약 입력에 서로 같은 두 점이 주어지면, 그 두 점을 이용하여 직선을 만들 수 있다.

출력:

첫째 줄에 답을 출력한다.

풀이방법:

 x좌표가 일치하는 두 점들이나 y좌표가 일치하는 두 점들이 축과 평행을 이루기 때문에 정렬을 통해서 쉽게 찾을 수 있을 것 같았다. 하지만 문제 이해를 잘못해서 처음에 조금 헤매었고, 질문에 있는 글을 보면서 겨우 이해했다.

 '만약 입력에 서로 같은 두 점이 주어지면, 그 두점을 이용하여 직선을 만들 수 있다.' 라는 문구때문에 많이 헷갈렸다. 처음에는 (0,0)_1 (0,0)_2 (0,10) 이렇게 있으면 (0,0)_1, (0,0)_2을 (0,0)_1, (0,10)을 (0,0)_2, (0,10)을 연결할 수 있어서 3개라고 생각했지만 아니였다.

 문제에서 원하는 것은 위와 같은 경우에는 (0,0)_1 (0,0)_2의 두 점을 통해 x=0, y=0이라는 두 직선을 만들 수 있었고, (0,0)_1, (0,10)을 (0,0)_2, (0,10) 이것들은 x=0인 직선에 포함되는 것이므로 카운트를 하지 않는다는 것이였다. 그래서 답은 2가 되는 것이였다.

 그래서 x축과 평행하게 만들 수 있는 직선의 숫자값, y축과 평행하게 만들 수 있는 직선의 숫자값을 각각 담는 배열을 만들어서 그 길이를 더하도록 했다.

하지만 매우 비효율적으로 구성했기 때문에 시간초과가 발생하였고 PyPy3로 통과할 수 있었다.

문제링크:

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

지금까지 풀었던 문제들을 GIT에 정리하기 시작했다. 많은 양이라 한 번에 다 업로드 하지는 못하고 있지만 차근차근 하나씩 다 올릴 예정이다. 문제는 1000번 단위로 정리하고 있으며 업로드 되어 있는 목록은 다음과 같다.

[2019-11-12] 현재는 1000~2999번까지 업로드

• 1000~2000

  • 1002 터렛
  • 1003 피보나치 함수
  • 1009 분산처리
  • 1011 Fly me to the Alpha Centauri
  • 1015 수열 정렬
  • 1016 제곱 ㄴㄴ수
  • 1018 체스판 다시 칠하기
  • 1037 약수
  • 1049 기타줄
  • 1065 한수
  • 1075 나누기
  • 1076 저항
  • 1080 행렬
  • 1110 더하기 사이클
  • 1120 문자열
  • 1149 RGB거리
  • 1152 단어의 개수
  • 1157 단어 공부
  • 1159 농구 경기
  • 1181 단어 정렬
  • 1260 DFS와 BFS
  • 1309 동물원
  • 1325 효율적인 해킹
  • 1357 뒤집힌 덧셈
  • 1371 가장 많은 글자
  • 1373 2진수 8진수
  • 1389 케빈 베이컨의 6단계 법칙
  • 1406 에디터
  • 1436 영화감독 숌
  • 1475 방번호
  • 1476 날짜 계산
  • 1495 기타리스트
  • 1547 공
  • 1561 놀이공원
  • 1629 곱셈
  • 1654 랜선 자르기
  • 1655 가운데를 말해요
  • 1676 팩토리얼 0의 개수
  • 1697 숨바꼭질
  • 1699 제곱수의 합
  • 1712 손익분기점
  • 1744 수 묶기
  • 1759 암호 만들기
  • 1789 수들의 합
  • 1834 나머지와 몫이 같은 수
  • 1874 스택 수열
  • 1890 점프
  • 1904 01타일
  • 1912 연속합
  • 1920 수 찾기
  • 1927 최소힙
  • 1929 소수 구하기
  • 1931 회의실 배정
  • 1977 완전 제곱수
  • 1987 알파벳

• 2001~3000

  • 2004 조합 0의 개수
  • 2011 암호코드
  • 2022 사다리
  • 2075 N번째 큰 수
  • 2133 타일 채우기
  • 2156 포도주 시식
  • 2163 초콜릿 자르기
  • 2178 미로찾기
  • 2193 이친수
  • 2217 로프
  • 2225 합분해
  • 2231 분해합
  • 2292 벌집
  • 2309 일곱 난쟁이
  • 2312 수 복원하기
  • 2331 반복 수열
  • 2407 조합
  • 2504 괄호의 값
  • 2606 바이러스
  • 2667 단지번호 붙이기
  • 2775 부녀회장이 될테야
  • 2805 나무 자르기
  • 2839 설탕 배달
  • 2851 슈퍼 마리오
  • 2869 달팽이는 올라가고 싶다.
  • 2875 대회 or 인턴
  • 2941 크로아티아 알파벳
  • 2960 에라토스테네스의 체

• 3001~4000

  • 3036 링
  • 3053 택시 기하학

• 4001~5000

  • 4307 개미
  • 4344 평균은 넘겠지
  • 4948 베르트랑 공준
  • 4949 균형잡힌 세상

• 5001~6000

  • 5430 AC
  • 5567 결혼식

• 6001~7000

  • 6064 카잉 달력
  • 6591 이항 쇼다운

• 7001~8000

  • 7568 덩치
  • 7576 토마토
  • 7569 토마토

• 8001~9000

  • 8979 올림픽

• 9001~10000

  • 9012 괄호
  • 9095 1,2,3 더하기
  • 9461 파도반 수열
  • 9465 스티커
  • 9613 GCD 합
  • 9933 민균이의 비밀번호
  • 9935 문자열 폭발

• 10001~11000

  • 10250 ACM 호텔
  • 10253 헨리
  • 10451 순열 사이클
  • 10610 30
  • 10816 숫자 카드2
  • 10825 국영수
  • 10828 스택
  • 10844 쉬운 계단 수

• 11001~

  • 11047 동전0
  • 11050 이항계수1
  • 11051 이항계수2
  • 11053 가장 긴 증가하는 부분 수열
  • 11057 오르막 수
  • 11052 카드 구매하기
  • 11279 최대힙
  • 11286 절대값 힙
  • 11718 그래도 출력하기
  • 11816 조세퍼스 문제0
  • 14501 퇴사
  • 14889 스타트와 링크
  • 15649 N과 M
  • 17144 미세먼지 안녕!

https://github.com/kimkyeonghun/BOJ

문제:

n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다.(-_-)

이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 둘 다 소중한 생명이지만 판다가 최대한 오래 살 수 있는지 고민에 빠져 잇따. 우리의 임무는 이 사육사를 도와주는 것이다. n*n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 오래 살려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

입력:

첫째 줄에 대나무 숲의 크기 n(1<=n<=500)이 주어진다. 그리고 둘째 줄부터 n+1번째 줄까지 대나무 숲의 정보가 주어진다. 대나무 숲의 정보는 공백을 사이로 두고 각 지역의 대나무의 양이 정수 값으로 주어진다. 대나무의 양은 1,000,000보다 작거나 같은 자연수이다.

출력:

첫째 줄에는 판다가 최대한 살 수 있는 일수(K)를 출력한다.

풀이방법:

 기본적으로는 dfs를 사용해서 판다의 이동 경로를 알아야 하지만 문제에서 원하는 것은 판다가 최대한 살 수 있는 일수, 즉 최대로 이동 가능한 거리의 길이를 원하고 있다. 작은 크기의 경우에는 시작점을 달리 해서 최대 일수를 찾을 수 있지만 500 x 500의 경우에는 이 것을 다 탐색하기에는 많은 시간이 걸릴 것이다.

 따라서 이를 해결하기 위해서 다이나믹 프로그래밍에서 메모리제이션을 사용한다. 한 점에서 출발을 해서 움직이다가 이미 이전에 다른 곳에서 움직였던 기록이 남아있고 그것을 기록해뒀다면 더 이상 그 길로 이동할 필요없이 그 값을 참조해서 다시 돌아오면 된다. 따라서 dfs로 이동을 하지만 이전에 이 길을 지나간 기록이 있다면 그 값을 가져오고, 그렇지 않다면 더 들어가면서 값을 기록하도록 한다.

 또한 재귀적으로 함수를 구현했기 때문에 깊은 재귀로 인한 에러를 방지하기 위해서 sys.setrecursionlimit를 사용한다.

문제링크:

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

문제:

서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받는 학생이 구금되어있다.

그러던 어느 날, 감옥 간수인 상범이는 지루한 나머지 정신나간 게임을 하기로 결정했다. 게임의 첫 번째 라운드에서 상범이는 위스키를 한 잔 들이키고, 달려가며 감옥을 한 개씩 모두 연다. 그 다음 라운드에서는 2,4,6, ... 번 방을 다시 잠그고, 세 번째 라운드에서는 3, 6, 9, ... 번 방이 열려있으면 잠그고, 잠겨있으면 연다. k번째 라운드에서는 번호가 k인 배수인 방이 열려 있으면 잠그고, 잠겨 있으면 연다. 이렇게 n번째 라운드까지 진행한 이후, 상범이는 위스키의 마지막 병을 마시고 쓰러져 잠든다.

입력:

입력의 첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄에 한 개씩 방의 개수 n(5<=n<=100)이 주어진다.

출력:

한 줄에 한 개씩 각 테스트 케이스의 답, 즉 몇 명이 탈출할 수 있는지를 출력한다.

풀이방법:

다이나믹 프로그래밍으로 풀어야 한다고 하는데 방의 개수가 100으로 작은편이기 때문에 완전탐색을 사용해서 풀었다.

0이면 열려 있고, 1이면 닫혀 있다고 했을 때, 해당하는 숫자 j의 배수마다 0이면 1로, 1이면 0으로 바꾸도록 했다. 이렇게 모두 탐색을 완료하면 0의 갯수에서 하나를 빼서 답을 구한다.

(다 풀고나니 1을 열려 있고, 0을 닫혀 있다 가정하고, 마지막에 sum을 하는 것이 더 깔끔할 것 같다.)

문제링크:

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

문제:

정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수 있다. 예를 들어 앞에서부터 순서대로 크기가(1,5,2,3,7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를 넣을 수 있는 방법을 여러 가지가 있을 수 있다. 앞의 예에서 차례대로 크기가 1, 2, 3, 7인 상자를 선택하면 총 4개의 상자가 한 개의 상자에 들어가게 된다.

상자의 크기가 주어질 때, 한 번에 넣을 수 있는 최대의 상자 개수를 출력하는 프로그램을 작성하시오.

입력:

파일의 첫 번째 줄은 상자의 개수 n(1<=n<=1000)을 나타낸다. 두 번째 줄에는 각 상자의 크기가 순서대로 주어진다. 상자의 크기는 1,000을 넘지 않는 자연수이다.

출력:

첫쨰 줄에 한 줄에 넣을 수 있는 최대의 상자 개수를 출력한다.

풀이방법:

앞에 있는 작은 상자를 뒤에 있는 큰 상자에 넣을 수 있으므로 이는 다이나믹프로그래밍을 사용한 LIS 문제와 같다.

LIS에서 lis[i]는 i번째 수열까지 한 번에 넣을 수 있는 최대의 상자 개수이며, i+1을 추가했을 때, boxes[1]~boxes[i]까지 boxes[i+1]보다 작은 값이 있는지 파악하고, 그 수에 해당하는 lis[k] 값들 중에 최댓값에 1을 더해주는 방식으로 진행한다. 그러고 전체 lis에서 최댓값을 출력해주면 된다.

문제링크:

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

문제:

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우) 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력:

첫째 줄에 두 정수 N(1<=N<=200),K(1<=K<=200)가 주어진다.

출력:

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

풀이방법:

동적계획법을 사용해서 이 문제를 풀었다. 점화식은 간단하다. K개의 합이 N이 되었을 때, 맨 마지막 수( l )를 빼면 남은 수는 K-1개로 N-l 이 남는 다는 것이다. 그래서 dp 테이블을 다음과 같이 구성할 수 있다.

dp[ i ][ j ] 는 i개의 수를 가지고 합이 j가 되는 경우를 뜻한다. 따라서 처음에는 1로 초기화되며, 한 층이 지날때마다 경우의 수가 더해져 우리가 원하는 dp[k][n]을 구할 수 있다.

문제링크:

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

문제:

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리는 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N<=M)

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

입력:

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N,M(0<N<=M<30)이 주어진다.

출력:

각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.

풀이방법:

이 문제는 다이나믹 프로그래밍을 활용해서 풀 수 있는 문제이다. 

왼쪽에 3개의 사이트가 있고, 오른쪽에 5개의 사이트가 있다고 가정하자. 그럼 왼쪽의 3개와 오른쪽의 5개를 이어야 하는 문제가 된다. 하지만 왼쪽의 제일 위 점과 오른쪽의 제일 위 점에 다리를 건설했다고 하자.

이제는 아래 남은 점들은 왼쪽의 2개의 점, 오른쪽의 4개의 점을 이어야 하는 문제가 된다. 이 단계에서 한 번 더 진행하면 이제 왼쪽에는 한 개만 남고 오른쪽에는 3개, 2개 ... 가 남게 된다. 왼쪽이 1개가 되면 오른쪽에 남은 개수가 이을 수 있는 경우의 수가 되므로 이를 활용해서 점화식을 만들 수 있게 된다.

dp[i][j] = d[i-1][k-1]+d[i-1][k-2]+ ... + d[i-1][i-1]

따라서 이를 반복문으로 구현하면 다음과 같게 된다. 

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

문제:

Day of Mourning의 기타리스트 강토는 다가오는 공연에서 연주할 N개의 곡을 연주하고 있다. 지금까지 공연과는 다른 공연을 보여주기 위해서 이번 공연에서는 매번 곡이 시작하기 전에 볼륨을 바꾸고 연주하려고 한다.

먼저, 공연이 시작하기 전에 각각의 곡이 시작하기 전에 바꿀 수 있는 볼륨의 리스트를 만들었다. 이 리스트를 V라고 했을 때, V[i]는 i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨을 의미한다. 항상 리스트에 적힌 차이로만 볼륨을 바꿀 수 있다. 즉, 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P+V[i]나 P-V[i]로 연주 해야 한다. 하지만 0보다 작은 값으로 볼륨을 바꾸거나, M보다 큰 값으로 볼륨을 바꿀 수 없다.

곡의 개수 N과 시작 볼륨 S, 그리고 M이 주어졌을 때, 마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 구하는 프로그램을 작성하시오. 모든 곡은 리스트에 적힌 순서대로 연주해야 한다.

입력:

첫째 줄에 N, S, M이 주어진다. (1<=N<=100, 1<=M<=1000,0<=S<=M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다.

출력:

첫째 줄에 가능한 마지막 곡의 볼륨 중 최댓값을 출력한다. 만약 마지막 곡을 연주할 수 없다면(중간에 볼륨을 조절을 할 수 없다면) -1을 출력한다.

풀이방법:

 2차원 배열을 사용하는 동적계획법을 사용하면 트리처럼 진행이 된다. 점차 연주가 가능한 볼륨이 많아지긴 하겠지만, 0보다 작은 값이나 초과하는 값들도 들어오기 때문에 생각만큼 많이 증가하지는 않게 된다.

 각 배열은 0으로 초기화 되어 있으며 각 곡마다 연주할 수 있는 볼륨은 1로 바뀌게 된다. 따라서 처음에는 S 자리에만 1로 초기화 되어 있으며 다음 곡의 배열은 이전 곡에서 1인 값에 V[i]를 빼거나 더한 값이 1로 초기화 될 것이다.

 이렇게 마지막 곡까지 위 행위를 반복하고 뒤에서부터 1인 값을 찾아 1이면 값을 넣고 종료시키면 그 값이 최댓값이 될 것이다. 그리고 애초에 -1을 초기값으로 잡아뒀기 때문에 1인 값을 만나지 못하면 연주 할 수 없는 것을 의미하므로 답은 그대로 -1이 될 것이다.

문제링크:

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

문제:

재현이는 다음과 같은 정수 게임을 하려고 한다. 게임은 다음과 같이 이루어져 있다.

 1. 정수 N과 크기가 K인 배열 A를 정한다.

 2. 1부터 N까지 정수를 모두 종이에 쓴다.

 3. 배열 A의 가장 첫 수를 고르고, 그 수를 배열에서 제거한다. 고른 수를 x라고 했을 때, 종이에 적혀있는 수 중에 x의 배수를 지운다.

 4. 배열이 비어있을 때 까지 3번을 반복한다.

게임이 모두 완료된 이후에, 종이에 적혀있는 수의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N과 K가 주어진다. (1<=N<=1,000,000,000, 1<=K<=15)

둘째 줄에 배열 A의 내용이 순서대로 주어진다. 배열에 담겨있는 수는 100보다 작거나 같은 자연수이다.

출력:

게임이 모두 완료된 이후에, 종이에 적혀있는 수의 개수를 출력한다.

풀이방법:

포함배제의 원리를 사용해서 풀어야 하는 문제이다. 포함배제의 원리는 유한 집합들의 합집합의 원소를 세는 기법 중의 하나이다. 보통 다음과 같은 식을 가진다.

따라서 count를 통해서 현재 값을 더해야 하는지 빼야 하는지를 결정해준다. 해당하는 값들은 combination으로 만든 조합의 최소공배수 값을 통해서 지워야 하는 갯수를 구할 수 있다.

이렇게 포함배제로 지워지는 수들의 갯수를 구하면 n과 더해줌으로써 남은 개수를 구한다.

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

https://ko.wikipedia.org/wiki/%ED%8F%AC%ED%95%A8%EB%B0%B0%EC%A0%9C%EC%9D%98_%EC%9B%90%EB%A6%AC

문제:

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계까 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다."를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

출력:

첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

풀이방법:

bfs를 사용해서 이 문제를 풀었다. 이 문제에서는 신뢰 관계가 양방향으로 존재한다는 가정이 없기 때문에 신뢰 관계를 정리 할 때, 단방향으로만 해야 한다. 일반적인 리스트를 사용해도 상관이 없지만 python의 시간 초과를 해결하기 위해 deque를 사용하고자 하였다. 하지만 그래도 python으로는 시간초과가 발생하였고,(한 명도 python으로 통과한 사람이 아직 없다.)그래서 결국 pypy3으로 통과했다.

 그 외의 특이사항으로는 방문했는지 확인하는 배열인 conti가 존재한다는 것이다. 아직 방문하지 않는 컴퓨터일 때에만 값을 갱신하며 count가 증가하도록 했다.

문제링크:

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