본문 바로가기

분류 전체보기282

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.

티스토리툴바