-
최장 공통 부분 수열 - Longest Common Subsequence
문제 두 문자열의 최대 공통 부분 수열 (Longest Common Subsequence)의 길이를 구하라. LCS(“ABCDGH”, “AEDFHR”) = “ADH”, length = 3 LCS(“AGGTAB”, “GXTXAYB”) = “GTAB”, length = 4 출처: https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/ 추가문제: 공간 효율적인 방법으로 LCS를 구하라. LCS 문자열을 구하라. 모든 LCS 문자열을 구하라. 풀이 동적 계획법, DP (Dynamic programming)로 O(mn) 시간에 풀...
-
곱하기 배열 퍼즐 - Product array puzzle
문제 Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i. 주어진 정수 배열에서, 원래 배열의 인덱스 i의 값을 제외한 모든 숫자들을 곱한 값이...
-
문자열에서 단어 순서 뒤집기 (공백처리 포함) - Reverse words in a string
문제 주어진 문자열에 나오는 단어들의 순서를 뒤집는 함수를 작성하라. 입력: "the sky is blue" 결과: "blue is sky the" 입력: " the sky is blue " 결과: "blue is sky the" 추가조건: ‘단어’는 ‘공백문자 (space)’가 아닌 문자들의 연속으로 정의한다. 입력 문자열은 앞부분 또는 뒷부분에 공백문자들이 있을 수 있다. 결과 문자열은...
-
카카오 신입 공채 코딩 테스트: 다트 게임
국내 회사들도 개발자 채용을 위해 코딩 테스트를 적극 도입하고 있다. 얼마전 화제가 되었던 카카오 신입 공채 코딩 테스트 문제 중에서 하나를 풀어보자. 문제 카카오 신입 공채 1차 코딩 테스트 - ‘다트 게임’ 점수 계산 http://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1 풀이 import re def char_to_power(ch): if ch == 'S': return 1 elif ch == 'D':...
-
퀵 선택 - Quick select
문제 정렬되어 있지 않은 중복없는 숫자들의 배열에서 k번째로 작은 숫자를 찾아라. (k는 언제나 유효한 값 이라고 가정한다. 1 <= k <= length of array) find_kth([7, 10, 4, 3, 20, 15], 3) 7 find_kth([7, 10, 4, 3, 20, 15], 4) 10 출처 GeeksforGeeks https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array 풀이 간단하게 생각하면 정렬하고 k번째 (인덱스 k...