본문 바로가기

알고리즘

2019 KAKAO BLIND RECRUITMENT - 오픈채팅방, 파이썬 1. 문제 - 2019 카카오 코딩테스트 1차 1번 오픈채팅방 문제이다. - 난이도는 레벨 1로 추정되며 매우 쉬운 문제 - 개선점을 기록하고자 남겨둠 2. 풀이 - 들어왔던 ID가 새로 들어왔을 때 그 이전 기록이 새로 들어온 닉네임으로 바뀜. - Leave의 경우 닉네임 기록이 없음 - Change의 경우도 해당 아이디의 닉네임이 모두 새로운 닉네임으로 바뀜 - 딕셔너리에 아이디를 키로 해서 최신 닉네임으로 업데이트해준다. - 나중에 반복문으로 출력 def solution(record): ans = [] dic = {} for i, data in enumerate(record): record[i] = data.split(" ") if record[i][0] == 'Enter' or record[i][..
2020 KAKAO BLIND RECRUITMENT - 가사 검색 (파이썬) 1. 문제 - 카카오 코딩테스트 가사검색 문제 - 주어진 queries 에 맞는 words의 수를 리턴하는 문제 - 단 와일드카드 "?" 가 들어감 - queriesquequeriesries 2. 풀이 - word와 query의 길이는 각각 100,000 이기 때문에 Brute Force로 풀면 시간초과가 나온다. - 따라서 시간초과가 떴고 써 본적이 없는 트라이 구조를 검색해서 적용해봤다. - 와일드카드가 단어 중간에 들어갈 수 없으며 빈칸일 수는 없다는 점(와일드카드에 따라 단어 수가 변동되지 않는다는 점)이 힌트인듯 - 단어 길이는 최대 10,000 이기 때문에 각 단어길이에 맞는 Trie 배열을 생성해준다.(접두사가 같더라도 단어 길이에 따라 = 뒤에 붙는 와일드카드 ? 개수에 따라 답이 다르기 ..
카카오 코딩테스트 2020 괄호 변환, 파이썬 1. 문제 1) 문제에서 주어진 정의에 따라 요구한 순서대로 풀면 된다. 2) 말 그대로 언어를 프로그래밍 언어로 변환하면 되는 문제이기 때문에 매우 쉬운 문제이다. 3) 알고리즘은 사실상 완전한 괄호를 찾는 알고리즘(스택이나 Brute force 이용)만 필요. 2. 풀이 좀 길긴 하지만 누구나 이해하기 쉽게 짰다는 점에서 만족스럽다. 다만 함수 이름과 변수명에 대해서는 좀 고민이 필요할듯..^^ def solution(p): answer = '' if not p : return answer while not is_val(p) : idx = find_u(p) u = p[:idx] v = p[idx:] if is_val(u) : answer += u p = v else : temp_v = solution..
카카오 코딩테스트- 문자열 압축, 파이썬 1. 문제 문자열을 압축하여 표현할 때 가장 짧은 문자열 수를 구하라 2. 풀이 1부터 문자열 길이의 절반까지 반복해서 압축된 문자열의 길이 중 최소값을 구하는 식으로 풀었다. Brute force 문제인데 왜 함수명을 dfs라쓴지는 모르겠다. 1번문제 답게 어렵지 않게 풀 수 있다. 다만 두 가지 때문에 테스트케이스를 틀렸는데 1) 아래처럼 범위를 돌리다보니까 s 길이가 1인 경우 for문이 실행되지 않아 ret 배열이 비어버려 오류가 난다. for i in range(1, len(s)//2 + 1) : dfs(s, i, ret) 그냥 구현만 하려고 위에 문자열 길이가 1인 경우 예외처리를 해줬는데 주의해야할 부분이다 2) 반복되는 문자열이 나온 경우 앞의 숫자 예를들어 aaa의 경우 3a로 생각하고 ..
카카오 코딩테스트 2021 - 합승 택시 요금 (파이썬) 문제 프로그래머스 합승 택시 요금 링크 A와 B가 같은 지점에서 택시를 타고 임의의 경유지까지 합승 후(옵션) 각자의 목적지까지 가는 최소의 요금의 합을 구하는 문제 결국 정점을 거쳐 출발지에서 목적지로 가는 최소비용을 구하는 문제 풀이 레벨 3 난이도 합승하지 않는 케이스는 출발지점에서 출발지점까지 합승한다고 가정하면 이때 비용은 0이므로, 결국 모든 노드까지 합승하는 비용 + 합승지점에서 각자의 목적지까지 가는 비용을 더한 값 중 최저값을 구하면 된다. 각 지점에서 각 지점까지 가는 최소비용이 필요, dfs를 이용해서 구했더니 타임초과가 떴다. 결국 검색 후 플로이드 와샬이 알고리즘을 적용했다. 플로이드와샬 알고리즘 기본적으로 DP에 근거한 알고리즘 거쳐가는 정점 기준으로 최소 비용을 구하는 알고리즘..
40. Combination Sum II, 파이썬 예전에 풀었을 때는 시간초과 때문에 틀렸던 것 같다. [1, 1, 1, 1, 1, 1, 1] 등에서 시간초과가 났었다 문제 1. 숫자들이 배열로 주어졌을 때 합이 target인 숫자 조합을 중복 없이 구하는 것. 풀이 1. 어려운 문제는 아니지만 중복을 피하고, 시간을 줄이는 것이 핵심. 2. target 8, [1, 1, 4, 6, 7] 이라고 했을 때 [1, 1, 6] 은 체크하고 [1, 7], [1, 7] 이 중복이 나오지 않게 해야한다. 3. 따라서 정렬된 배열에서 path에서 arr[i] 값이 중복되어 다음 dfs로 넘어가지 않도록 체크해준다. class Solution(object): def combinationSum2(self, candidates, target): ret = [] self...
22. Generate Parentheses - 파이썬 이 문제는 dfs로 풀려다 뭔가 꼬여서 틀렸던 문제이다. 릿코드는 일단 200번까지 푸는게 목표인데 145번을 풀고 있는 지금 다시 풀어보니 풀렸다. Medium에서 알 수 있듯 그다지 어려운 문제는 아닌데 전형적인 문제라 남겨준다. 문제 1. n이 주어졌을 때 가능한 괄호 닫기 모든 경우의 수. 2. Parentheses가 무슨 뜻인지 몰라 검색했던 기억이 난다... ^^ 풀이 1. 핵심은 "(" , 즉 괄호가 열려있던 적이 있어야 괄호 닫기 ")"를 사용할 수 있다는 점. n이 충분할 때 "((" 는 가능하지만 "())"는 불가능 2. n의 개수만큼 (를 사용 할 수 있고 사용할 때마다 스택에 )를 쌓아 둔다. 3. 재귀와 스택을 활용 개선점 1. 무언가 코드가 너저분 2. 변수가 너무 많아 직관성이..
2021 KAKAO BLIND RECRUITMENT - 순위 검색, 파이썬 과정 1. 문제를 구현하는 것은 어렵지 않지만 시간 조건때문에 조금 까다롭다. 주어진 두 개의 배열이 각각 50,000, 100,000개라서 각각 순환하며 조건을 체크하면 1억번이 넘어 시간제한(10초)에 걸리게 된다. 2. 따라서 딕셔너리를 이용해서 어지간한 건 사전처리를 해줘서 이용하기 쉽게 해준다. 예를 들어 sort()같은 경우 시간복잡도가 O(n)이기 때문에 따로 빼줘서 시간제한에 걸리지 않게 해준다. 3. 조건 점수에 맞는 케이스를 찾는 것도 그냥 인덱싱은 O(n)이라 시간초과가 나와 O(logn)인 이분탐색을 활용한다. lower boundary니 Upper boundary니 있던데 어차피 binary search 고 그때그때 예시로 생각해보면 된다. 개선점 1. 시간초과를 생각안하고 풀면서..

티스토리툴바