본문 바로가기

전체 글282

15998. 카카오머니 (Python) 15998번: 카카오머니 만약 유효한 최소 충전 단위 M(1 ≤ M ≤ 9 * 1018)이 존재한다면, 첫 번째 줄에 M 을 출력한다. 가능한 값이 여러 가지 있다면, 그중 9 * 1018 이하인 것을 아무거나 하나 출력한다. 존재하지 않는다면 www.acmicpc.net 풀이 계좌에서 충전이 필요한 출금 작업을 할 때마다 충전에 필요한 최대 금액들에 대한 최대 공약수를 구하고 구한 값을 M으로 설정했을 때 로그에 모순이 생기지 않는지를 체크한다. 문제의 예제에서 충전이 필요한 출금 작업은 두 건 존재한다. (1)번 로그의 경우 충전이 필요한 첫 출금 작업이므로 계산에 필요한 값들을 기록하면 된다. 여기에서 필요한 값은 충전해야 하는 20,000원에 대한 정보와 출금 후 남은 잔액인 4,500원이다. (.. 2022. 5. 17.
2293. 동전 1 (Python) 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 1차원 dp를 사용하여 문제를 해결할 수 있다. dp[value]는 value를 만들 수 있는 동전 조합의 수를 의미한다. dp 배열의 모든 값을 0으로 초기화하여 만든 후 dp[0]은 1로 설정한다. 이는 가치 0을 만들 수 있는 조합은 아무 동전도 사용하지 않는 하나의 경우의 수가 있기 때문이다. 문제의 점화식은 다음과 같다. value는 현재 살펴볼 가치의 합을 의미하고 coin은 현재 사용할 동전의 가치를 의미한다. dp[value + coin] +=.. 2022. 5. 15.
6087. 레이저 통신 (Python) 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 풀이 BFS를 통해서 C에서 C로 갈 때 필요한 거울 개수의 최솟값을 구할 수 있다. BFS를 위한 큐에는 (행, 열, 이전에 이동했던 방향, 사용한 거울의 개수)와 같은 튜플의 형태로 값을 넣어줬다. 이전에 이동했던 방향을 넣어준 이유는 기존에 이동했던 방향 그대로 이동할 때는 거울을 사용하지 않고 이동하고 90도 방향으로 이동할 때는 거울을 사용하기 때문에 이를 체크하기 위해 사용했다. 반대 방향으로 이동하는 경우는 체크하지 않고 넘어간다(예를 들어.. 2022. 5. 13.
2467. 용액 (Python) 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 풀이 투 포인터(left와 right)를 사용하여 해결할 수 있다. 가장 처음과 끝에 포인터를 하나씩 두고 더한 결과에 따라서 포인터를 이동시킨다. 두 포인터가 가리키고 있는 용액의 합이 0일 경우 -> 그대로 탐색을 종료한다. 음수일 경우 -> 두 용액의 합을 0에 가깝게 하기 위해서는 더 작은 값을 가리키고 있는 left 포인터를 이동 시켜야 한다. 두 합이 음수일 경우는 더 작은 쪽의 값을 늘려야 0에 가까워 질 수 있기 때문이다. 양수일 경우 -> .. 2022. 5. 12.
2660. 회장뽑기 (Python) 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 풀이 회원의 수가 50명을 넘지 않으므로 회원 모두에 대하여 bfs를 진행하여 각 회원의 점수를 구한다. bfs를 통해 얻은 점수를 키로 하는 딕셔너리를 사용하여 해당 점수에 대한 회원들의 리스트를 기록한다. 마지막에 최소 점수에 해당하는 회원들의 리스트를 딕셔너리에서 가져와서 정렬한 후 출력해 주면 된다. 코드 import sys from collections import defaultdict input = sys.stdin.readline # n번 회원에 대.. 2022. 5. 11.
[2020 카카오 인턴십] 보석 쇼핑 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 풀이 두개의 포인터를 이용하여 문제를 해결할 수 있다. 두 포인터를 left와 right라고 했을 때(left left를 이동시켜서 구간의 길이를 감소시킨다. left가 가르키고 있는 보석은 right에 이미 있으므로 left에 있는 보석은 구간에서 제외해도 상관없다. 구간의 길이가 줄어들었으므로 기존의 가장 짧은 구간과 비교하여 더 짧은 구간으로 답을 갱신한다. 두 포인터가 가르키고 있는 보석.. 2022. 5. 6.
[2020 카카오 인턴십] 수식 최대화 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr 풀이 다음과 같은 과정을 통해서 답을 구할 수 있다. 수식에 존재하는 연산자 리스트를 구한다. 순열을 통해서 연산자들의 우선순위를 정해준다. 각각의 우선순위에 따라서 입력 받은 중위 표현식으로 된 수식을 후위 표현식으로 변환한다. 변환한 후위 표현식을 계산하여 결괏값을 구하고 이중 최댓값을 구한다. 코드 from itertools import permutations # 중위 표기식을 후위 표기식으로 변환하는 함수 # priority는 연산자의 우선순위를 나타낸.. 2022. 5. 5.
[2020 카카오 인턴십] 키패드 누르기 코딩테스트 연습 - 키패드 누르기 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL" programmers.co.kr 풀이 키패드에서 각 버튼의 위치를 행과 열의 좌표로 생각한다. 문제에서 주어진 것처럼 숫자 1, 4, 7의 경우는 왼손을 이동시키고 숫자 3, 6, 9의 경우는 오른손을 이동시키면 된다. 숫자 2, 5, 8, 0은 눌러야 하는 숫자의 좌표를 구하고 현재 왼손과 오른손의 위치에서 얼마나 떨어져 있는지를 구한다. 이를 비교하여 제일 가까이 있는 손을 이동시.. 2022. 5. 5.
9251. LCS (Python) 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 LCS 알고리즘의 대표적인 문제다. LCS 알고리즘에 대해서는 여기를 참고하자. 코드 if __name__ == '__main__': str1 = input() str2 = input() dp = [[0 for _ in range(len(str1) + 1)] for _ in range(len(str2) + 1)] for i in range(1, len(str2) + 1): for j in range(1, len(.. 2022. 5. 1.

티스토리툴바