본문 바로가기

Algorithm175

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.
[Algorithm] LCS (Longest Common Substring / Subsequence) 알고리즘 LCS란? LCS는 최장 공통 문자열(Lognest Common Substring) 또는 최장 공통 부분 수열(Longest Common Subsequence)을 의미한다. 전자는 연속된 문자열에 대한 것을 뜻하고 후자는 연속되지 않은 문자열이 포함될 수 있다. 최장 공통 문자열 (Longest Common Substring) 최장 공통 문자열을 구하는 과정은 다음과 같다. 문자열 A의 i번째 문자와 문자열 B의 j번째 문자를 비교한다. 두 문자가 같다면 ( A[i] == B[j] ) dp[i][j]에 dp[i-1][j-1] + 1을 대입한다. 두 문자가 다르다면 ( A[i] != B[j] ) dp[i][j]의 값을 0으로 설정한다. 과정중에 구한 최댓값이 최장 공통 문자열의 길이가 된다. 공통 문자열은.. 2022. 5. 1.

티스토리툴바