코딩도치

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

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

안녕하세요. 코딩도치 입니다~ 오늘은 백준 알고리즘 15684번 사다리 조작 문제를 풀어보려고 합니다! 이해하는 것도, 방법을 생각하기도, 구현하기도 참 어려운 문제입니다ㅜㅜ 그래도 한번 차근차근 알아보겠습니다! 먼저 이 문제는 기본적으로 dfs를 활용해서 모든 경우의 수를 다 생각해보고 판단할 수 있습니다. 하지만 이렇게 하면 시간초과가 나버리는데요. 그렇다고 무슨 특별한 방법이 있는 것은 아닙니다. 모든 경우의 수를 본다는 전제를 두고 그 경우의 수를 줄여주는 방법 밖에는 없습니다. 그럼 경우의 수는 어떻게 줄일까요?? 간단합니다. 기본적인 dfs방식에서 어떠한 조건을 주고 해당 조건을 만족하는 경우에만 이어서 탐색을 하도록 하는 것이죠. 이러한 방법을 백트래킹(Backtracking)이라고 합니다...

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

안녕하세요. 코딩도치 입니다~ 오늘은 백준 알고리즘 1260번 DFS와 BFS 문제를 풀어보려고 합니다! DFS, BFS는 코딩 테스트나 알고리즘 대회 같은 곳에 꼭 등장하는 단골손님입니다. 그러니까 꼼꼼히 공부하고 연습하는 것이 좋겠죠? 먼저 DFS, BFS가 무엇인지부터 살펴보겠습니다. DFS(Depth-First Search) : 깊이 우선 탐색 BFS(Breadth-First Search) : 너비 우선 탐색 DFS, BFS 모두 그래프 탐색의 일종으로, 탐색하는 방식의 차이에 의해서 구분되는 것입니다. 아래 그래프를 예로 DFS와 BFS를 설명해 보겠습니다.(시작 정점 0) 1. DFS(Depth-First Search) : 깊이 우선 탐색 결론적으로 말씀드리자면, DFS방식으로 위 그래프를 탐..