CodeDrive

문제:

풀이방법:

트리 구조를 알고 있는지 물어보는 문제인 것 같다. 따라서 Tree라는 class를 만들고, 이 클래스는 x,y 좌표와 left, right를 만들어서 node 연결을 하도록 한다.

우선 부모 노드를 찾고, 자식 노드들을 알기 위해서 정렬을 하는 작업을 먼저 한다. y가 큰 순으로, x가 작은 순으로 정렬하도록 하기 위해 sorted의 key를 사용하였다.

이렇게 root를 찾고 남은 node들은 root부터 시작하여서 x 좌표를 비교해서 이 값이 left 혹은 right인지 확인을 한다. 만약 현재 node에서 이미 left나 right 값이 있다면 그 노드로 이동해서 다시 비교를 하고 지정해주는 작업을 계속해서 반복한다. 따라서 얼마나 많은 반복을 해야할지 모르기 때문에 while을 사용하였으며, 연결을 완료하면 break로 나오도록 하였다.

node 연결을 마친 뒤에 preorder와 postorder는 정의대로 재귀를 사용해서 배열에 담아서 return 하도록 한다. 다만 이 때 많은 node들이 있으면 python의 재귀 메커니즘상 런타임 에러가 발생한다고 한다.

(python은 재귀가 최대 1000회로 제한되어 있다.)

따라서 이를 해결하기 위해서 sys.setrecursionlimit()를 사용해서 최댓값을 넉넉히 늘려주도록 한다.

문제링크:

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

문제:

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

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

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

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

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

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

풀이방법:

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

문제링크:

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

문제:

준민이는 탄산 음료를 좋아한다. 탄산 음료를 사느라 돈을 다 써버렸기 때문에, 이제 준민이는 가진 돈이 없어 탄산 음룔를 사먹을 수 없다.

준민이는 항상 법을 지키며 사는 사람이기 때문에, 아무리 탄산 음료가 먹고 싶어도 훔치지 않는다. 따라서, 법적으로 문제가 없는 방법으로 탄산 음료를 구매할 것이다.

마침 빈 병을 특정 개수만큼 가져가면, 새 병으로 바꾸어주는 이벤트가 진행중이다. 준민이는 길에서 빈 병을 열심히 찾은 뒤, 탄산 음료를 먹으려고 한다.

준민이가 현재 가지고 있는 빈 병의 수와 길에서 발견한 빈 병의 수, 새 병으로 바꾸는데 필요한 빈 병의 수가 주어졌을 때, 준민이가 탄산 음료를 몇 개 먹을 수 있는지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 준민이가 가지고 있는 빈 병의 수 e, 그날 발견한 빈 병의 수 f, 새 병으로 바꾸는데 필요한 빈 병의 개수 c가 주어진다. (e<1000, f<1000,1<c<2000)e,f,c는 모두 음이 아닌 정수이다.

출력:

첫째 줄에 준민이가 탄산 음료를 몇 개나 먹을 수 있는지를 출력한다.

풀이방법:

가지고 있는 빈 병이랑 발견한 빈 병의 수도 중요하지만 이를 통해서 구매한 병의 수도 중요하다. 이 문제의 경우처럼 9개의 빈병으로 3개를 바꿀 수가 있다. 그리고 이 3병을 다 마시면 다시 1병을 바꿀 수 있기 때문에 총 4병이 되는 것이다. 그래서 이와 같은 방법으로 몇번을 더 바꾸어 먹을 수 있는지 모르기 때문에 while을 사용하였다.

병의 수를 c로 나누었을 때 몫을 계속해서 더하며 남은 병과 몫을 다시 더해서 빈 병으로 만든다. 

이 과정을 계속해서 반복하면서 몫이 0이 되는 경우에 빠져 나오도록 하였다.

문제링크:

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

문제:

서울에서 경산까지 여행을 하면서 모금 활동을 하려 합니다. 여행은 서울에서 출발해 다른 도시를 정해진 순서대로 딱 한 번 방문한 후 경산으로 도착할 예정입니다. 도시를 이동할 때에는 도보 혹은 자전거를 이용합니다. 이때 도보 이동에 걸리는 시간, 도보 이동 시 얻을 모금액, 자전거 이동에 걸리는 시간, 자전거 이동 시 얻을 모금액이 정해져 있습니다. K시간 이내로 여행할 때 모을 수 있는 최대 모금액을 알아보려 합니다

예를 들어 여행 루트가 다음과 같고 K=1,650 일 때,

1, 2번 구간은 도보로, 3번 구간은 자전거로 이동해 모금액을 660으로 하는 것이 가장 좋은 방법입니다. 이때, 1,600시간이 소요됩니다.

solution 함수의 매개변수로 각 도시를 이동할 때 이동 수단별로 걸리는 시간과 모금액을 담은 2차원 배열 travel과 제한시간 K가 주어집니다. 제한시간 안에 서울에서 경산까지 여행을 하며 모을 수 있는 최대 모금액을 return 하도록 solution 함수를 작성하세요.

풀이방법:

동적계획법을 사용해서 풀어야 하는 문제이다. 0번째 인덱스에는 도보로 걸리는 시간, 2번째 인덱스에는 자전거 이동시 걸리는 시간이 담겨 있으며. 1번째, 3번째 인덱스에는 각각 금액이 담겨져 있다. 따라서 0,2번째로 K시간이 넘어가지 않는 선에서 1,3을 더 했을 때 최대가 되는 값을 찾으면 된다.

문제링크:

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

문제:

직사각형 종이를 n번 접으려고 합니다. 이때, 항상 오른쪽 절반을 왼쪽으로 접어 나갑니다. 다음은 n=2인 경우의 예시입니다.

먼저 오른쪽 절반을 왼쪽으로 접습니다.

다시 오른쪽 절반을 왼쪽으로 접습니다.

종이를 모두 접은 후에는 종이를 전부 펼칩니다. 종이를 펼칠 때는 종이를 접은 방법의 역순으로 펼쳐서 처음 놓여있던 때와 같은 상태가 되도록 합니다. 위와 같이 두 번 접은 후 종이를 펼치면 종이에 접은 흔적이 생기게 됩니다.

V 모양이 생긴 부분은 점선(0)으로, ㅅ 모양이 생긴 부분은 실선(1)으로 표시했습니다.

종이를 접은 횟수 n이 매개변수로 주어질 때, 종이를 절반씩 n번 접은 후 모두 펼쳤을 때 생기는 접한 부분의 모양을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

풀이방법:

이 문제는 종이접기 수열을 사용하는 문제이다. 종이접기 수열이란 이 문제처럼 종이를 일정한 방향으로 접었을 때 생기는 굴곡에 대한 수열이다. 

이 문제처럼 오른쪽에서 왼쪽으로 접는 경우에는 가운데가 0으로 고정되어서 수열이 생성된다.

1 ->  0

2 ->  0 + 0 + 1

3 ->  0 + 0 +1 + 0 +0 + 1+ 1

4 -> 001+0+011 + 0 + 001+1+011

5 -> 0010011+ 0 + 0011011 + 0 +0010011 + 1 + 0011011

....

1, 2, 3에서는 규칙을 찾기 어렵지만 4부터는 규칙을 찾을 수 있다.

가운데 0을 기준으로 이전 단계의 모양이 반복되는 것을 알 수 있다. 가운데 0을 기준으로 했을 때 왼쪽은 이전단계의 중간이 0인 경우 오른쪽은 이전단계의 중간이 1인 경우이다. 따라서 1, 2의 경우에는 예외처리로 두어서 답을 반환하도록 하고, 3부터는 반복문을 통해서 규칙을 생성하도록 하였다.

문제링크:

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

문제:

 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기 입니다. 이 종이를 격자 선을 따라 1cm x 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm x 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.

 가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

풀이방법:

직사각형에서 대각선으로 잘랐을 때 제거되는 부분은 다음과 같이 동일하게 삭제됨을 알 수 있다. 이들의 개수는 gcd를 통해서 구할 수 있으며 제거되는 칸 수도 w//gcd+h//gcd -1로 구할 수 있다. 

따라서 gcd를 구한 뒤 전체에서 해당하는 만큼 제거하면 답을 구할 수 있다.

문제링크:

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

문제:

풀이방법:

 내가 말해야 하는 단어까지만 알면 되므로 0부터 n진수로 변환을 하면서 digits에 더하고 digits의 길이가 t*m보다 커지면 그만 변환하도록 하면 된다.

 digits를 다 구했다면 내가 말해야 하는 위치의 인덱스 값을 answer에 더해서 반환하도록 한다.

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

문제:

풀이방법:

우선 파일명을 HEAD, NUMBER, TAIL로 정리를 해야한다. 이를 위해서 isdigit이라는 숫자인지 확인하는 함수를 사용한다.

 처음 isdigit이 참이 되는 순간 이전까지의 글자가 HEAD가 되므로 isdigit이 참이 되는 순간 parser에 값을 추가하고 break를 걸어서 반복문을 나온다. 

 해당 위치부터 다시 반복문을 사용해서 이번에는 isdigit이 거짓이 되는 순간이 NUMBER의 끝이므로 parser에 값을 추가하고 break를 걸어서 반복문을 나온다.

 이제 남은 부분은 TAIL에 해당하므로 parser에 추가해주면 되지만 TAIL이 아무것도 없을 경우에는 위 NUMBER를 파악하는 과정에서 맨 마지막 숫자가 추가되지 못했을 것이다. 따라서 해당 인덱스에 isdigit을 사용해서 참이면 TAIL이 없는 경우, 거짓이면 TAIL이 있는 경우를 의미한다.

 이제 파일명을 HEAD, NUMBER, TAIL로 나눴으므로 sort의 key를 사용해서 정렬을 하도록 한다. 우선 HEAD를 기준으로 사전 순 정렬을 하고, 대소문자 구별을 하지 않는다. 그리고 HEAD가 동일하다면 NUMBER가 작은순으로 정렬을 하는데 스트링 상태가 아닌 int 상태로 변환해서 정렬을 해야 한다. 따라서 sort의 key는 (x[0].upper(), int(x[1])) 이 된다. 이처럼 해야지 원래 파일명을 보존하면서 정렬을 할 수 있다.

 정렬을 완료했으므로 이를 다시 붙여서 출력을 해야 한다. TAIL이 있는 경우에는 parser에 2번째 인덱스가 존재하지만 없다면 1까지만 존재한다. 따라서 이를 try~ except ~ 예외처리 구문을 사용해서 추가하도록 한다.

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

문제:

풀이방법:

LZW 압축 과정대로 코드를 작성하면 된다.

 우선 길이가 1인 모든 단어를 포함해서 사전을 구축해야 하므로 dictionary에 밑과 같이 구축한다. 그 뒤에 idx가 입력으로 들어온 문자열의 길이와 같아질 때까지 반복해서 확인하고 추가하는 작업을 한다.

 LZW 압축과정은 다음과 같이 작동된다.

1. KAKAO의 경우에 KAKAO와 인덱스 0 그리고 사전이 check로 입력된다.

2. 이를 뒤에서부터 비교를 한다. 즉 KAKAO가 사전에 있는가? -> KAKA가 사전에 있는가? -> .... 순으로 진행이 되고 K가 사전에 있는가에서 참이므로 break를 걸고 반복문 밖으로 나온다.

3. 그러면 KA는 사전에 없는 단어였으므로 사전에 추가하고 인덱스와 사전을 반환한다.

4. check에서 나온 인덱스와 check에 넣기 전에 사용한 인덱스를 사용해서 슬라이싱을 하고 이를 사전의 색인 번호를 answer에 추가한다.

5. idx를 i로 지정한다.

 idx가 msg와 동일할 떄까지 진행을 하면 압축과정이 끝나게 된다.

문제링크:

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

문제:

풀이방법:

 이 문제에서 처리해야 할 것은 크게 두 가지이다. 재생된 시간의 길이에 따라서 음이 달라지므로 시간 형식으로 되어 있는 자료형을 분 단위로 바꿔야 한다. 그리고 음계 중에 C#, D#, F#, G#과 같이 #이 붙어 있는 음계가 있는데 스트링 형식으로 되어 있기 때문에 이들도 하나의 인덱스를 차지하고 있으므로 처리하는 방법에 대해서 생각해야 한다.

 우선 분으로 바꾸기 위해서 :를 기준으로 분할을 한다. 시작하는 분과 끝나는 분을 비교해서 음악의 총 재생된 시간을 구하도록 한다.

 C#과 같이 #이 달려있는 음들은 하나의 인덱스로 처리를 하는 것이 편하므로 소문자로 변경하도록 한다. (C#->c , D# ->d , ....) 이 작업을 하고 위에서 구한 재생된 시간으로 실제 재생된 멜로디를 구할 수 있고, 이 안에 m이 있는지 판단하여서 answers 리스트에 담도록 한다. 

 이 때 조건이 일치하는 음악이 여러 개일 경우에는 재생된 시간이 제일 긴 음악, 먼저 입력된 음악 제목 순으로 정렬해야 하므로 (재생된 시간, 입력된 인덱스,음악제목)과 같이 answers에 넣도록 한다.

 일치하는 음악을 모두 담았다면 sort의 key를 이용해서 위 조건에 맞게 정렬을 하도록 한다. 재생된 시간은 길수록 앞으로 와야 하므로 음수를 붙여주고, 먼저 입력된 것이 앞으로 와야 하므로 이는 양수로 정렬하도록 한다. 이렇게 정렬을 하고 난 뒤에 answers에 가장 앞에 있는 값의 맨 마지막 값을 출력한다면 그것이 음악제목일 것이다. (만약 answers가 비어 있다면 "(None)"을 출력해야 한다.

문제링크:

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