CodeDrive

문제:

수빈이는 강호와 함께 스타크래프트 게임을 하고 있다. 수빈이는 뮤탈리스크 1개가 남아있고, 강호는 SCV N개가 남아있다.

각각의 SCV는 남아있는 체력이 주어져있으며, 뮤탈리스크를 공격할 수는 없다. 즉, 이 게임은 수빈이가 이겼다는 것이다.

뮤탈리스크가 공격을 할 때, 한 번에 세 개의 SCV를 공격할 수 있다.

1. 첫 번째로 공격받는 SCV는 체력 9를 잃는다.
2. 두 번째로 공격받는 SCV는 체력 3을 잃는다.
3. 세 번째로 공격받는 SCV는 체력 1을 잃는다.

SCV의 체력이 0 또는 그 이하가 되어버리면, SCV는 그 즉시 파괴된다. 한 번의 공격에서 같은 SCV를 여러 번 공격할 수는 없다.

남아있는 SCV의 체력이 주어졌을 때, 모든 SCV를 파괴하기 위해 공격해야 하는 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 SCV의 수 N (1 ≤ N ≤ 3)이 주어진다. 둘째 줄에는 SCV N개의 체력이 주어진다. 체력은 60보다 작거나 같은 자연수이다.

출력:

첫째 줄에 모든 SCV를 파괴하기 위한 공격 횟수의 최솟값을 출력한다.

풀이방법:

 SCV는 최대 3개까지만 있을 수 있기 때문에 이보다 더 적은 SCV가 들어온다면 0 배열을 이어 붙여서 길이가 3인 배열로 만들어 주도록 한다. SCV는 최대 체력이 60이고, 몇번째로 공격받느냐에 따라 체력이 달라지기 때문에 60의 길이를 가지는 3차원 visited 배열을 만든다.

 이후로는 BFS를 사용하여 나올 수 있는 경우의 수를 기반으로 체력을 감소시키며 모두 0이 되는 순간이 정답이다.

문제링크:

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

문제:

동혁이는 NBA 농구 경기를 즐겨 본다. 동혁이는 골이 들어갈 때 마다 골이 들어간 시간과 팀을 적는 이상한 취미를 가지고 있다.

농구 경기는 정확히 48분동안 진행된다. 각 팀이 몇 분동안 이기고 있었는지 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 골이 들어간 횟수 N(1<=N<=100)이 주어진다. 둘째 줄부터 N개의 줄에 득점 정보가 주어진다. 득점 정보는 득점한 팀의 번호와 득점한 시간으로 이루어져 있다. 팀 번호는 1 또는 2이다. 득점한 시간은 MM:SS(분:초) 형식이며, 분과 초가 한자리 일 경우 첫째자리가 0이다. 분은 0보다 크거나 같고, 47보다 작거나 같으며, 초는 0보다 크거나 같고, 59보다 작거나 같다. 득점 시간이 겹치는 경우는 없다.

출력:

첫째 줄에 1번 팀이 이기고 있던 시간, 둘째 줄에 2번 팀이 이기고 있던 시간을 출력한다. 시간은 입력과 같은 형식(MM:SS)으로 출력한다.

풀이방법:

 1번팀과 2번팀과의 점수를 기록하면서 한 팀이 점수를 앞서 나가는 순간에만 시간 차이를 계산하여 각 팀의 시간에 더해주도록 한다. 시간을 더할 때 계산의 편의성을 위해 초 단위로 모두 변환한다.

 중간중간 동점이 되는 경우도 있기 때문에 동점이 되기 전에 시간 차이를 더해준 뒤에 기준이 되는 시간을 갱신하고 각 팀에 점수를 더해주도록 한다.

문제링크:

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

문제:

알고리즘의 킹갓제너럴엠퍼러마제스티충무공알고리즘마스터 현우가 교수로 취임하였다!

그러나 학생들에게 크나큰 기대를 품고 첫 수업에 들어갔던 현우는 아무도 외판원 순회 문제(Traveling Salesman Problem, TSP)를 풀지 못하는 것을 보고 낙심하였다.

그 와중에 학생 남규는 TSP를 완전탐색으로 풀려고 하였고, 현우는 그걸 보고 경악을 금치 못한다. 왜냐면 TSP를 완전탐색으로 풀려면 O(N!)의 시간이 소모되는데, 이는 경악을 금치 못할 시간이기 때문이다.

그러나 남규는 O(N!)이 왜 큰지도 잘 모른다. 그래서 현우는 더더욱 경악을 금치 못하고, N!이 얼마나 큰지 대략적으로나마 알려주기 위해, 자연수 N이 주어지면 N!의 오른쪽 끝에 있는 0의 개수를 알려주기로 하였다.

그러나 현우는 경악을 금치 못하여 지금 코딩을 할 수 없는 상황이다. 여러분이 현우를 대신하여 프로그램을 작성하시오.

입력:

첫째 줄에 테스트 케이스의 개수 T가 주어지고, 이어서 T개의 줄에 정수 N이 주어진다(1 <= N <= 1000000000).

출력:

각 줄마다 N!의 오른쪽 끝에 있는 0의 개수를 출력한다.

풀이방법:

 오른쪽 끝에 0이 생기기 위해서는 2x5가 곱해져야 한다. 즉, N!을 소인수 분해 했을 때, 2와 5 중 더 작은 인수가 0의 갯수가 될 것이다. (2^P, 5^Q 일 때 P, Q 중 더 작은 수) 하지만 10까지만 봤을 때에도 2의 갯수가 압도적으로 많기 때문에 5의 개수만 알면 바로 0의 갯수를 알 수 있다. 따라서 5의 인수를 구하도록 한다.

문제링크:

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

문제:

JOI시는 남북방향이 H 킬로미터, 동서방향이 W 킬로미터인 직사각형 모양이다. JOI시는 가로와 세로의 길이가 1킬로미터인 H × W 개의 작은 구역들로 나뉘어 있다. 북쪽으로부터 i 번째, 서쪽으로부터 j 번째에 있는 구역을 (i, j) 로 표시한다.

각 구역의 하늘에는 구름이 있을 수도, 없을 수도 있다. 모든 구름은 1분이 지날 때마다 1킬로미터씩 동쪽으로 이동한다. 오늘은 날씨가 정말 좋기 때문에 JOI시의 외부에서 구름이 이동해 오는 경우는 없다.

지금 각 구역의 하늘에 구름이 있는지 없는지를 알고 있다. 기상청에서 일하고 있는 여러분은 각 구역에 대해서 지금부터 몇 분뒤 처음으로 하늘에 구름이 오는지를 예측하는 일을 맡았다.

각 구역에 대해서 지금부터 몇 분뒤 처음으로 하늘에 구름이 오는지를 구하여라.

입력:

입력은 1 + H 행으로 주어진다.

첫 번째 행에는 정수 H, W (1 ≦ H ≦ 100, 1 ≦ W ≦ 100) 가 공백을 사이에 주고 주어진다. 이것은 JOI시가 H × W 개의 작은 구역으로 나뉘어 있다는 것을 의미한다.

이어진 H 개의 행의 i번째 행 (1 ≦ i ≦ H) 에는 W문자의 문자열이 주어진다. W 개의 문자 중 j번째 문자 (1 ≦ j ≦ W) 는, 구역 (i, j) 에 지금 구름이 떠 있는지 아닌지를 나타낸다. 구름이 있는 경우에는 영어 소문자 'c' 가, 구름이 없는 경우에는 문자 '.' 가 주어진다.

출력:

출력은 H 행으로, 각 행에는 공백으로 구분된 W 개의 정수를 출력한다. 출력의 i 번째 행 j 번째 정수 (1 ≦ i ≦ H, 1 ≦ j ≦ W) 는, 지금부터 몇 분후에 처음으로 구역 (i, j) 에 구름이 뜨는지를 표시한다. 단, 처음부터 구역 (i, j) 에 구름이 떠 있었던 경우에는 0을, 몇 분이 지나도 구름이 뜨지 않을 경우에는 -1을 출력한다.

풀이방법:

주어진 조건대로 구현해야 하는 문제다. 이 문제에서는 총 3가지 행동을 수행한다.

1. 지금 하늘에 구름(c)가 있는가?

2. 구름이 몇 분뒤에 지금 하늘에 도착하는가?

3. 구름의 이동

따라서 while 계속해서 반복하고, 1에 의해서 break 조건을 만든다. 그 동안에 2와 3을 반복하며 answer 2차원 배열을 채우도록 한다.

문제링크:

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

문제:

상근이는 수학시간에 딴 짓을 하다가 선생님께 걸렸다. 선생님은 상근이에게 이번 주말동안 반성하라며 엄청난 숙제를 내주었다.

선생님이 상근이에게 준 종이에는 숫자와 알파벳 소문자로 되어있는 글자가 N줄있다. 상근이는 여기서 숫자를 모두 찾은 뒤, 이 숫자를 비내림차순으로 정리해야한다. 숫자의 앞에 0이 있는 경우에는 정리하면서 생략할 수 있다.

글자를 살펴보다가 숫자가 나오는 경우에는, 가능한 가장 큰 숫자를 찾아야 한다. 즉, 모든 숫자의 앞과 뒤에 문자가 있거나, 줄의 시작 또는 끝이어야 한다.

예를 들어, 01a2b3456cde478에서 숫자를 찾으면 1, 2, 3456, 478이다.

선생님이 준 종이의 내용이 주어졌을 때, 상근이의 숙제를 대신하는 프로그램을 작성하시오.

입력:

첫째 줄에 종이의 줄의 개수 N이 주어진다. (1 ≤ N ≤ 100)

다음 N개의 줄에는 각 줄의 내용이 주어진다. 각 줄은 최대 100글자이고, 항상 알파벳 소문자와 숫자로만 이루어져 있다.

출력:

종이에서 찾은 숫자의 개수를 M이라고 하면, 출력은 M줄로 이루어져야 한다. 각 줄에는 종이에서 찾은 숫자를 하나씩 출력해야 한다. 이때, 비내림차순으로 출력해야 한다. 비내림차순은 내림차순의 반대인 경우인데, 다음 수가 앞의 수보다 크거나 같은 경우를 말한다.

풀이방법:

 python의 isdigit 기능을 사용해서 숫자를 찾도록 한다. 숫자가 연속해서 나오는 경우에는 이어붙이고, 숫자가 아닌 경우에만 배열에 담도록한다. 그리고 맨 끝의 숫자(lo3za4)에서 4도 탐색하기 위해서 for 문이 끝나고 나서 숫자가 남아있다면 추가로 넣어주도록한다.

 이렇게 모든 문자열 탐색이 끝난 뒤에, 배열에 있는 모든 숫자를 int형으로 바꾼 뒤에 정렬을 하도록 한다. (01과 같은 것을 제거하기 위함)

문제링크:

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

문제:

2차원 좌표 평면 위에 있는 점 3개 P1, P2, P3가 주어진다. P1, P2, P3를 순서대로 이은 선분이 어떤 방향을 이루고 있는지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다.

출력:

P1, P2, P3를 순서대로 이은 선분이 반시계 방향을 나타내면 1, 시계 방향이면 -1, 일직선이면 0을 출력한다.

풀이방법:

 2차원 평면에서 점 3개의 방향을 판단하는 알고리즘을 CCW(Counter Clockwise)라고 한다. 외적을 사용하는 알고리즘인데, 아래 링크에서 자세하게 잘 설명해준 것 같아서 참조하도록 한다.

참고링크: https://degurii.tistory.com/47

문제링크:

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

문제:

좋은 패스워드를 만드는것은 어려운 일이다. 대부분의 사용자들은 buddy처럼 발음하기 좋고 기억하기 쉬운 패스워드를 원하나, 이런 패스워드들은 보안의 문제가 발생한다. 어떤 사이트들은 xvtpzyo 같은 비밀번호를 무작위로 부여해 주기도 하지만, 사용자들은 이를 외우는데 어려움을 느끼고 심지어는 포스트잇에 적어 컴퓨터에 붙여놓는다. 가장 이상적인 해결법은 '발음이 가능한' 패스워드를 만드는 것으로 적당히 외우기 쉬우면서도 안전하게 계정을 지킬 수 있다.

회사 FnordCom은 그런 패스워드 생성기를 만들려고 계획중이다. 당신은 그 회사 품질 관리 부서의 직원으로 생성기를 테스트해보고 생성되는 패스워드의 품질을 평가하여야 한다. 높은 품질을 가진 비밀번호의 조건은 다음과 같다.

1. 모음(a,e,i,o,u) 하나를 반드시 포함하여야 한다.
2. 모음이 3개 혹은 자음이 3개 연속으로 오면 안 된다.
3. 같은 글자가 연속적으로 두번 오면 안되나, ee 와 oo는 허용한다.

이 규칙은 완벽하지 않다;우리에게 친숙하거나 발음이 쉬운 단어 중에서도 품질이 낮게 평가되는 경우가 많이 있다.

입력:

입력은 여러개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스는 한 줄로 이루어져 있으며, 각 줄에 테스트할 패스워드가 주어진다.

마지막 테스트 케이스는 end이며, 패스워드는 한글자 이상 20글자 이하의 문자열이다. 또한 패스워드는 대문자를 포함하지 않는다.

출력:

각 테스트 케이스를 '예제 출력'의 형태에 기반하여 품질을 평가하여라.

풀이방법:

이 문제에는 조건이 3개 있고, 각각 다음과 같이 처리하도록 한다.

1. 모음 하나를 반드시 포함하여야 한다.

vowel이라는 리스트를 선언하고, string의 chr 하나씩 보면서 모음인 경우에 vowel_check를 True로 변환해준다. 모든 string 탐색을 마친 뒤에 vowel_check를 확인하도록 한다.

2. 모음이 3개 혹은 자음이 3개 연속으로 오면 안 된다.

한 단어를 확인할 때마다. v, nv의 갯수를 업데이트 한다. 각각 vowel, non_vowel을 의미하고, 모음이 나온 경우에는 v++을 하고, nv는 0으로 만들어준다. 자음의 경우에는 반대로 수행한다. 그리고, 둘 중 하나가 3인 경우에는 answer를 False로 바꾼다.

3. 같은 글자가 연속적으로 두번 오면 안되나, ee와 oo는 허용한다.

각 chr를 stack에 담으면서 끝 값과 비교하도록 한다. 이 때 만약 같다는 조건문을 통과한 경우에는 answer를 False로 바꾸는데, ee와 oo만 따로 예외상황으로 빼도록 한다.

문제링크:

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

문제:

위대한 해커 창영이는 모든 암호를 깨는 방법을 발견했다. 그 방법은 빈도를 조사하는 것이다.

창영이는 말할 수 없는 방법을 이용해서 현우가 강산이에게 보내는 메시지를 획득했다. 이 메시지는 숫자 N개로 이루어진 수열이고, 숫자는 모두 C보다 작거나 같다. 창영이는 이 숫자를 자주 등장하는 빈도순대로 정렬하려고 한다.

만약, 수열의 두 수 X와 Y가 있을 때, X가 Y보다 수열에서 많이 등장하는 경우에는 X가 Y보다 앞에 있어야 한다. 만약, 등장하는 횟수가 같다면, 먼저 나온 것이 앞에 있어야 한다.

이렇게 정렬하는 방법을 빈도 정렬이라고 한다.

수열이 주어졌을 때, 빈도 정렬을 하는 프로그램을 작성하시오.

입력:

첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000)

둘째 줄에 메시지 수열이 주어진다.

출력:

첫째 줄에 입력으로 주어진 수열을 빈도 정렬한 다음 출력한다.

풀이방법:

 python의 Counter는 편리하고 빠르게 개수를 세도록 지원한다. Counter가 가진 함수 중에서 most_common이 자주 등장하는 순서로 정렬을 하는데, 개수가 같은 요소는 처음 발견된 순서를 유지한다. 이 문제에서 요구하는 조건과 같기 때문에 이를 사용하여 개수를 집계하고, 정렬된 순서에 따라 출력을 하도록 한다.

문제링크:

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

문제:

상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다. 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M<N) 플레이어는 게임을 하는 중에 바구니를 왼쪽이나 오른쪽으로 이동할 수 있다. 하지만, 바구니는 스크린의 경계를 넘어가면 안 된다. 가장 처음에 바구니는 왼쪽 M칸을 차지하고 있다.

스크린의 위에서 사과 여러 개가 떨어진다. 각 사과는 N칸중 한 칸의 상단에서 떨어지기 시작하며, 스크린의 바닥에 닿을때까지 직선으로 떨어진다. 한 사과가 바닥에 닿는 즉시, 다른 사과가 떨어지기 시작한다.

바구니가 사과가 떨어지는 칸을 차지하고 있다면, 바구니는 그 사과가 바닥에 닿을 때, 사과를 담을 수 있다. 상근이는 사과를 모두 담으려고 한다. 이때, 바구니의 이동 거리의 최솟값을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N과 M이 주어진다. (1 ≤ M < N ≤ 10) 둘째 줄에 떨어지는 사과의 개수 J가 주어진다. (1 ≤ J ≤ 20) 다음 J개 줄에는 사과가 떨어지는 위치가 순서대로 주어진다.

출력:

모든 사과를 담기 위해서 바구니가 이동해야 하는 거리의 최솟값을 출력한다.

풀이방법:

바구니의 너비가 있기 때문에 사과를 양 끝에 걸치게 받는 것이 가장 조금 이동하면서 사과를 받는 방법이다. 따라서 바구니의 양 끝의 index를 기억하면서 사과가 떨어지는 지점과의 차이를 더해나가도록 한다.

사과가 바구니의 오른쪽이면 바구니의 오른쪽과의 차이를 , 왼쪽이라면 바구니의 왼쪽과의 차이를 계산하면서 바구니도 같이 이동시키도록 한다.

문제링크:

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

문제:

이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 깨고 말았다. 안타깝게도 자는 동안 키보드가 잘못 눌려서 보고서의 모든 글자가 A와 B로 바뀌어 버렸다! 그래서 평석이는 보고서 작성을 때려치우고 보고서에서 '좋은 단어'나 세보기로 마음 먹었다.

평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓기로 하였다. 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 '좋은 단어'이다. 평석이가 '좋은 단어' 개수를 세는 것을 도와주자.

입력:

첫째 줄에 단어의 수 N이 주어진다. (1 ≤ N ≤ 100)

다음 N개 줄에는 A와 B로만 이루어진 단어가 한 줄에 하나씩 주어진다. 단어의 길이는 2와 100,000사이이며, 모든 단어 길이의 합은 1,000,000을 넘지 않는다.

출력:

첫째 줄에 좋은 단어의 수를 출력한다.

풀이방법:

단어들을 stack에 다음과 같은 규칙을 따르면서 A나 B를 하나씩 넣도록 한다.

 1. stack이 비어있다면 추가한다.

 2. stack의 마지막 값과 같다면 pop을 하고, 다르다면 append한다.

이 과정을 마치고 난 뒤에 stack에 값이 남아 있다면 이는 '좋은 단어'가 아니라는 것을 의미한다. 따라서 stack이 비어있을 때에만 count를 올려주도록 한다.

문제링크:

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