CodeDrive

문제:

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1<=N<=20, |S|<=1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력:

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

풀이방법:

알고리즘 분류가 브루트 포스로 되어 있었기 때문에 가능한 모든 경우의 수를 만들고자 하였다. 따라서 itertools의 combinations을 사용하였다. itertools.combinations( iterable, n)과 같이 사용하며 iterable한 객체로 반환을 한다. 따라서 이를 반복문으로 넣고 합했을 때 s가 되는 경우에 answer를 하나씩 올렸다.

문제링크:

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

문제:

다솜이는 기타를 많이 가지고 있다. 그리고 각각의 기타는 모두 다른 시리얼 번호를 가지고 있다. 다솜이는 기타를 빨리 찾아서 빨리 사람들에게 연주해주기 위해서 기타를 시리얼 번호 순서대로 정렬하고자 한다.

모든 시리얼 번호는 알파벳 대문자(A-Z)와 숫자 (0-9)로 이루어져 있다.

시리얼 번호 A가 시리얼번호 B의 앞에 오는 경우는 다음과 같다.

    1. A와 B의 길이가 다르면, 짧은 것이 먼저 온다.

    2. 만약 서로 길이가 같다면 A의 모든 자리수의 합과 B의 모든 자리수의 합을 비교해서 작은 합을 가지는 것이 먼저 온다. (숫자인 것만 더한다.)

    3. 만약 1,2번 둘 조건으로도 비교할 수 없으면, 사전순으로 비교한다. 숫자가 알파벳보다 사전순으로 작다.

시리얼이 주어졌을 때, 정렬해서 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 기타의 개수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어져 있다. 시리얼 번호는 중복되지 않는다.

출력:

첫째 줄부터 차례대로 N개의 줄에 한줄에 하나씩 시리얼 번호를 정렬한 결과를 출력한다.

풀이방법:

 python에서는 정렬에 대한 기능이 잘 구현되어 있기 때문에 조건에 맞게 key를 설정해주면 된다. 시리얼 번호 중 숫자의 합을 구해야 하는 조건도 있기 때문에 입력을 받을 때 전처리 작업으로 숫자의 합을 구해서 (시리얼번호, 숫자합)과 같은 형태로 값들을 저장한다.

 값들을 다 저장한 후에는 sort의 key를 이용해서 정렬하도록 한다. key=lambda x : (정렬조건...) 과 같은 방식으로 사용한다. 1번 조건은 길이이므로 len(x), 2번 조건은 숫자의 합이므로 x[1], 마지막으로는 사전순이므로 x[0]과 같이 조건을 넣어주도록 한다.

문제링크:

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

문제:

독일 로또는 {1, 2, ... , 49}에서 수 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k개의 수를 골라 집합 S를 만든 다음 그 수만을 가지고 번호를 선택하는 것이다.

예를 들어 , k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다.

{[1,2,3,5,8,13].[1,2,3,5,8,21].[1,2,3,5,8,34],[1,2,3,5,13,21], ... ,[3,5,8,13,21,34]}

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

입력:

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k(6<k<13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력:

각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

풀이방법:

 경우의 수를 구하는 문제는 python의 itertools를 사용하면 쉽게 구할 수 있다. itertools.combinations( iterable, k )와 같은 방식으로 사용하면 iterable한 자료형에서 k를 골라 만들 수 있는 모든 경우의 수를 만들어 준다.

 이 경우의 수를 출력하기 위해 *c와 같이 사용을 하고 각 테스트 케이스 사이에는 빈 줄을 하나 출력해야 하므로 print()를 마지막에 넣어주었다.

문제링크:

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

문제:

김탑은 TV를 사러 인터넷 쇼핑몰에 들어갔다. 쇼핑을 하던 중에, TV의 크기는 그 TV의 대각선 길이로 나타낸다는 것을 알았다. 하지만, 김탑은 대각선의 길이가 같다고 해도, 실제 TV의 크기는 다를 수도 있다는 사실에 직접 TV를 보러갈걸 왜 인터넷 쇼핑을 대각선의 길이만 보고있는지 후회하고 있었다.

인터넷 쇼핑몰 관리자에게 이메일을 보내서 실제 높이와 실제 너비를 보내달라고 했지만, 관리자는 실제 높이와 실제 너비를 보내지 않고 그것의 비용을 보내왔다.

TV의 대각선 길이와, 높이 너비의 비율이 주어졌을 때, 실제 높이와 너비의 길이를 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 TV의 대각선 길이, TV의 높이 비율, TV의 너비 비율이 공백 한 칸을 사이에 두고 주어진다. 대각선 길이는 5보다 크거나 같고, 1,000보다 작거나 같은 자연수, 높이 비율은 1보다 크거나 같고, 99보다 작거나 같은 자연수 너비 비율은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다. 너비 비율은 항상 높이 비율보다 크다.

출력:

첫째 줄에 TV의 높이와 TV의 너비를 공백 한 칸을 이용해서 구분지은 후 출력한다. 만약 실제 TV의 높이나 너비가 소수점이 나올 경우에는 그 수보다 작으면서 가장 큰 정수로 출력한다. (예)1.7->1

풀이방법:

높이와 너비의 비율이 주어졌으므로 이들의 비율 1에 해당하는 r을 구하면 된다. 이 r은 대각선의 길이로 구할 수 있게 된다. 너비를 x, 높이를 y라고 했을 때, x²+y²=기울기² 를 만족하고, x:y=a:b 의 비율을 만족시키는 r이 있다고 하자.

(r은 x=a*r, y=b*r 을 만족한다.)

그러면 다음을 만족한다.

a²r²+b²r²=기울기²

따라서 r로 묶어서 계산할 수 있고, 최종적으론 a*r, b*r을 출력하면 된다.

문제링크:

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

문제:

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 NxN인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다.)

예를 들어, 그림이 아래와 같은 경우에

RRRBB

GGBBB

BBBRR

BBRRR

RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1)하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강, 초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N이 주어진다. (1<=N<=100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

출력:

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해서 출력한다.

풀이방법:

dfs를 사용해서 구역을 구분하는 문제인데, 적록색약인 사람과 그렇지 않은 사람을 구분하기 위해 각각 dfs 함수를 구현해 주면 된다. 그리고 또한 입력을 받을 때 G나 R을 R이나 G로 바꿔주어 적록색약인 사람들을 구분하면 된다. 이번 풀이에서는 G를 R로 바꾸었다.

문제링크:

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

문제:

카드게임이 있다. 게임에 사용하는 각 카드에는 양의 정수 하나가 적혀있고 같은 숫자가 적힌 카드는 여러 장 있을 수 있다. 게임방법은 우선 짝수개의 카드를 무작위로 섞은 뒤 같은 개수의 두 더미로 나누어 하나는 왼쪽에 다른 하나는 오른쪽에 둔다.

각 더미의 제일 위에 있는 카드끼리 서로 비교하며 게임을 한다. 게임 규칙은 다음과 같다. 지금부터 왼쪽 더미의 제일 위 카드를 왼쪽 카드로, 오른쪽 더미의 제일 위 카드를 오른쪽 카드로 부르겠다.

1. 언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다.

2. 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다.

3. (1)과 (2)의 규칙에 따라 게임을 진행하다가 어느 쪽 더미든 남은 카드가 없다면 게임이 끝나며 그때까지 얻은 점수의 합이 최종 점수가 된다.

왼쪽 더미의 카드에 적힌 정수가 담긴 배열 left와 오른쪽 더미의 카드에 적힌 정수가 담긴 배열 right가 매개변수로 주어질 때, 얻을 수 있는 최종 점수의 최대값을 return 하도록 solution 함수를 작성하시오.

풀이방법:

동적 계획법을 사용해서 푸는 문제이다. 오른쪽을 버릴 때에만 점수를 얻을 수 있으므로, 오른쪽을 많이 버릴 수 있으면 좋다. 그래서 우선 오른쪽을 먼저 버릴 수 있는지 확인을 하고, 왼쪽과 둘 다 버리는 경우를 생각해서 계산한다.

문제링크:

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

문제:

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약은 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다.

(한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있다고 간주한다.)

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다.

예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다.

(0은 배추가 심어져 있지 않는 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.)

입력:

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1<=M<=50)과 세로길이 N(1<=N<=50), 그리고 배추가 심어져 있는 위치의 개수 K(1<=K<=2500)이 주어진다. 그 다음 K줄에는 배추의 위치(0<=X<=M-1),Y(0<=Y<=N-1)가 주어진다.

출력:

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

풀이방법:

dfs를 전형적인 문제이다. 탐색을 진행하다가 1인 점을 만나게 되면(그리고 이전에 방문을 하지 않았다면) dfs 함수에 들어가서 주위에 있는 1의 위치들을 모두 방문하는 방식으로 진행하면 된다. 주위의 1을 모두 방문한 뒤에 answer를 1증가 시키며 다시 탐색을 진행하여 1이지만 방문을 안한 점을 찾아 같은 작업을 반복해주면 된다.

문제링크:

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

문제:

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1<=N<=500,000)이가 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1<=M<=500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있따. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력:

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

풀이방법:

 많은 수를 비교해야 하므로 일반 탐색을 사용하면 시간 초과가 발생할 것 같았다. 그래서 로그 단위로 탐색이 가능한 이진탐색을 사용하고자 하였다. 그리고 이진탐색이 가능했던 이유가 같은 수가 적혀있는 경우가 없기도 했다.

 python에 이진탐색을 제공하는 bisect모듈을 사용하였다. bisect.bisect를 사용하면 배열에 값이 있는 위치를 반환하며 이 인덱스는 0부터 시작하는 것이 아닌 1부터 시작한다.(왜 그런진 모르겠다.) 또한 없는 값에 대해서는 그 근처의 값의 인덱스를 반환하기 때문에 bisect로 찾은 값과 내가 찾고자 하는 값이 참일 경우에만 answers의 값을 1로 바꾸도록 하였다.

문제링크:

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

문제:

정수 N이 주어져 있을 때 이 수가 10보다 크면 일의 자리에서 반올림을 하고, 이 결과가 100보다 크면 다시 10의 자리에서 반올림을 하고, 또 이 수가 1000보다 크면 100의 자리에서 반올림을 하고..(이하 생략) 이러한 연산을 한 결과를 출력하시오.

입력:

첫째 줄에 정수 N이 주어진다. (0<=N<=99,999,999)

출력:

첫째 줄에 위와 같은 연산을 한 결과를 출력하시오.

풀이방법:

뒷자리에서 부터 하나씩 반올림을 하면서 진행하면 된다. 반올림을 하려고 하는 자릿수가 5이면 앞자리에 1을 더해주고, 그렇지 않다면 그 자리를 0으로 바꾼 뒤 그대로 이어붙이면 된다. 그런데 반올림을 하는 자리의 수가 5이상이고 1을 받는 자리가 9이면 문제가 발생한다. 이 경우에는 9가 1을 받아서 10이 되기 때문에 그 앞자리까지에도 영향을 받게 된다. 

이를 int 연산으로 바꾸어서 진행을 했다면 문제가 없겠지만 str의 슬라이싱을 사용해서 문제를 풀고 있기 때문에 이 경우를 따로 예외 케이스로 만들어서 해결해 주도록 한다.

문제링크:

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

문제:

당신은 FCFS(First-Come, First-Served)의 규칙에 따라 요청된 일을 처리하는 서버를 담당하게 되었다. 매일, 당신은 일을 처리하기 위해 최대 T분 동안 서버에 시간을 할당할 수 있다. 당신은 오늘 주어진 시간동안 몇개의 일이 완료될 수 있는지 알고 싶다.

예시를 들어보겠다. T=180이고, 요청된 일들의 수행시간이 요청된 순으로 45,30,55,20,80,20 분이다. 그러면, 단 4개의 일만이 완료될 수 있다. 처음 4개의 일의 수행시간은 150분으로 주어진 시간 내에 완료될 수 있지만, 처음 5개의 일의 수행시간은 230분으로 주어진 시간 180분보다 크기 때문에 완료될 수 없다. 처음 4개의 일을 수행한 뒤 6번째의 일을 수행해도 T를 초과하지 않지만 5번째 일을 수행할 수 없기 때문에 6번째 일을 수행할 수 없음을 참고해라.

입력:

첫 줄을 두 정수 n과 T이며 (1<=n<=50, 1<=T<=500) n은 일의 개수를 나타낸다. 두 번째 줄은 n개의 100이하의 자연수가 입력되며, 입력된 각 일의 수행 시간을 나타낸다.

출력:

일이 First-come, First-serverd 규칙에 따라 처리될 때, T분 안에 완료될 수 있는 일들의 개수를 출력하라.

풀이방법:

앞에서 부터 더하면서 T를 넘는지 확인하면 된다. T를 넘는다면 break를 걸고 나와서 그 때까지의 값을 출력하면 된다. idx<n이라는 조건이 있는데 이 것은 주어진 일을 모두 T 시간 내에 해결할 수 있을 때 발생하는 에러에 대한 조건이다. while문을 사용했기 때문에 T가 아직 남아 있다면 계속해서 반복하게 될 것이고 런타임에러가 발생한다. 따라서 모든 값을 탐색했다면 종료해야 하기 때문에 이 조건을 넣었다.

문제링크:

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