코딩 맛집

'이것이 취업을 위한 코딩 테스트다 with 파이썬' 의 수록된 문제를 풀어 보겠습니다. 문제 제목은 '미로 탈출' 문제 입니다. 이것이 취업을 위한 코딩 테스트다 with 파이썬 IT 취준생이라면 누구나 입사하고 싶은 카카오ㆍ삼성전자ㆍ네이버ㆍ라인!취업의 성공 열쇠는 알고리즘 인터뷰에 있다!IT 취준생이라면 누구나 가고 싶어 하는 카카오, 라인, 삼성전자의 2016년부 book.naver.com 2차원 미로 속의 값이 0인 칸은 피하고, 1인 칸으로 만 이동해서, 출발점 : (0, 0), 도착점 : (N * M) 까지의 최소칸의 갯수를 구하는 문제 입니다. 구현하기 전에 먼저 고민 했습니다. 1. BFS와 DFS를 이용해서 탐색을 하는데, 최소 칸은 어떻게 구할수 있을지... 2. BFS와 DFS를 모두..

카카오 가사 검색 문제를 풀어 보았습니다. 아래 링크(프로그래머스) 에서 풀어 보실수 있습니다. 코딩테스트 연습 - 가사 검색 programmers.co.kr 처음의 다양한 접근 방법을 생각해 봤습니다. 1. word의 길이와 query의 길이가 같은 것들만 순차 탐색으로 찾는 접근 2. word들을 모두 합쳐서 하나의 문자열에서 query의 패턴을 kmp로 찾는 접근 하지만, 2가지 방법 모두 실패 하였습니다. 1번 방법은 일반 테스트는 모두 통과하지만, 효율성 테스트에서 실패 2번 방법은 완전히 매칭되는 단어를 찾는 문제이여서, 완전히 접근 방법 부터 틀렸습니다.(문제에서 접두사, 접미사 라는 단어가 나오길래, kmp를 의심;;) 다시, 이번엔 구글의 도움을 받아서 시도 했습니다. 1. 길이 별로 단..

1. 이진 탐색(Binary Search) 이진 탐색은 값이 정렬 되어 있는 상태에서 중앙 값을 이용해서 찾고자 하는 데이터의 위치를 탐색하는 알고리즘 입니다. 전체 탐색 범위(첫번째 인덱스, 마지막 인덱스)와 중앙 인덱스 알고 있다면, 중앙 인덱스의 값과 찾고자 하는 데이터의 값을 비교 해서, 더 작다면 왼쪽만 탐색, 더 크다면 오른쪽만 탐색 합니다. 따라서 우리는 3가지 변수를 알고 있어야 합니다. 첫번째 인덱스 : head 마지막 인덱스 : tail 중앙 인덱스 : mid = (head + tail) / 2 여기서, 중앙 인덱스의 나머지 값은 버리고, 몫만 사용 합니다. 2. 이진 탐색(Binary Search) 순서 위 그림과 같이, 찾고자 하는 target 값은 9 입니다. (target < a..

오늘은 플로이드 와샬(Floyd Warshall) 알고리즘에 대해서 포스팅 하겠습니다. 1. 플로이드 와샬 핵심 아이디어 플로이드 와샬(Floyd Warshall)도 다익스트라 알고리즘(Dijkstra algorithm)과 같이 특정 노드까지의 최단 거리를 구할 수 있는 알고리즘 입니다. 다익스트라 알고리즘(Dijkstra algorithm)은 one-to-all 알고리즘 입니다. 따라서 하나의 특정 노드로 부터 모든 노드까지의 최단 거리를 구할 수 있습니다. 하지만, 플로이드 와샬(Floyd Warshall) 알고리즘은 all-to-all 알고리즘 이므로, 모든 노드에서 부터 모든 노드 까지의 최단 거리를 구할수 있습니다. 각 노드 마다의 거리를 2차원 배열로 표현해 주고, 자기 자신의 노드까지 거리는..

다익스트라(Dijkstra) 알고리즘 안녕하세요. 오늘 소개할 알고리즘은 다익스트라(Dijkstra) 알고리즘 입니다. 다익스트라(Dijkstra) 알고리즘은 흔히 어떠한 노드들 사이에서 출발 노드 부터 도착 노드 까지 최단 거리, 최단 경로를 coding-food-court.tistory.com 지난 시간의 다익스트라(Dijkstra) 알고리즘에 대해서 공부하였습니다. 하지만 지난 시간의 다익스트라(Dijkstra) 알고리즘은 거리가 최소값인 노드를 찾기위해서 순차 탐색으로 찾아야 해서 시간 복잡도가 O(N^2) 이었습니다. 이것을 우리는 힙(heap) 자료구조를 이용해서 시간 복잡도를 줄일수 있습니다. 1. 힙(heap) 자료구조 힙(heap) 자료구조는 완전이진트리(Complete binary tr..

안녕하세요. 오늘 소개할 알고리즘은 다익스트라(Dijkstra) 알고리즘 입니다. 다익스트라(Dijkstra) 알고리즘은 흔히 어떠한 노드들 사이에서 출발 노드 부터 도착 노드 까지 최단 거리, 최단 경로를 찾는 알고리즘 입니다. 따라서, 가중치 그래프에서 사용할수 있는 알고리즘 입니다. 여기서 가중치는 거리라고 생각 하시면 되겠습니다. 위 그림 처럼 수원역에서 출발해서 강남역까지 최단 경로나 최단거리를 찾을때 사용 할 수 있는 알고리즘 입니다. 그럼 다익스트라(Dijkstra) 알고리즘의 핵심 아이디어를 한번 보시겠습니다. 1. 다익스트라(Dijkstra) 알고리즘 핵심 아이디어 2. 다익스트라(Dijkstra) 알고리즘 순서도 3. Java 소스 코드 public class DijkstraTest {..