반응형

카카오 3

3. [Python] 프로그래머스 2020 카카오 블라인드 채용 : 가사 검색 - 코딩도치

안녕하세요. 코딩도치입니다~ 오늘은 프로그래머스에 있는 2020 카카오 블라인드 채용 : 가사 검색 문제를 풀어보려고 합니다! 위 문제는 트라이(Trie) 자료구조를 사용하여 풀어야 효율성 테스트를 통과할 수 있습니다. 먼저, 트라이(Trie) 자료구조에 대해서 알아보겠습니다. 트라이(Trie) 자료구조 트라이는 문자열을 트리 형태로 저장하는 문자열 검색에 특화된 자료구조입니다. 트라이 자료구조를 사용하게 되면 가장 긴 문자열의 길이가 N이라고 했을 때, O(N)의 시간복잡도로 문자열을 찾을 수가 있습니다. ["app", "apart", "away", "bear"] 의 문자열이 주어졌을 때, 트라이 자료구조가 만들어지는 과정은 다음과 같습니다. 트라이 자료구조는 아무 데이터도 들어 있지 않은 루트 노드부..

2. [Python] 프로그래머스 2021 카카오 블라인드 채용 : 합승 택시 요금 - 코딩도치

안녕하세요. 코딩도치입니다~ 오늘은 프로그래머스에 있는 2021 카카오 블라인드 채용 : 합승 택시 요금 문제를 풀어보려고 합니다! 위 문제는 플로이드 워셜(Floyd-Warshal) 알고리즘을 사용하여 풀어야 효율성 테스트를 통과할 수 있습니다. 먼저, 플로이드 워셜(Floyd-Warshal) 알고리즘에 대해서 알아보겠습니다. 플로이드 워셜(Floyd-Warshal) 알고리즘 프로이드 워셜 알고리즘은 가중치 그래프에서 최단 경로를 찾는 알고리즘입니다. 그래프에서 최단 경로는 찾는 알고리즘은 다양합니다. 하지만 각각의 알고리즘이 적용될 수 있는 상황이 있기 때문에, 문제를 보고 적절한 알고리즘을 파악할 수 있어야합니다. 또다른 그래프 최단 경로 알고리즘인 다익스트라 알고리즘과 특징을 비교해보자면 다음과 ..

1. [C++] 프로그래머스 2020 카카오 인턴십 : 보석쇼핑 - 코딩도치

안녕하세요. 코딩도치입니다~ 오늘은 프로그래머스에 있는 2020 카카오 인턴십 : 보석쇼핑 문제를 풀어보려고 합니다! 해당 문제는 정확성과 효율성까지 테스트하는 문제입니다. 그래서 문제를 딱 보고 완전탐색과 같은 방법으로 해결할 수는 있겠지만, 그렇게 하면 효율성 테스트를 통과할 수 없겠죠? 여기서 필요한 알고리즘이 바로 투 포인터(Two Pointer) 알고리즘입니다. 어떠한 연속된 배열의 범위를 구하는 문제이고, 빠른 검색을 요구하기 때문에 위 알고리즘을 생각해볼 수 있는 것입니다. 먼저 투 포인터(Two Pointer)가 무엇인지부터 살펴보겠습니다. 투 포인터(Two Pointer)란, 리스트를 두 개의 포인터를 이용해 순차적으로 접근하면서, 두 포인터 구간의 값이 타겟 값과 같을 때 까지 포인터를..

반응형