S E P H ' S

2023년 4월 중간 회고 회고를 꾸준히 써보자고 마음먹어두고 이제서야 작성을 하게 됐다. 이번 상반기는 2022년에 1년여 간의 코치 생활을 끝내고 백수 생활을 하면서 본격적으로 취업준비를 시작한 첫 시기였다. 앞으로 시간이 되면 꾸준히 기록하면서 스스로 돌이켜보는 시간을 많이 가져봐야겠다. 여전히 발목을 잡는 알고리즘 SSAFY 교육을 받으면서도 코치 생활을 하면서도 부끄럽지만 나는 알고리즘이 너무 약했다. 이번 삼성전자와 네이버 코딩테스트를 치르면서 발전한 점이 있다면 전보다는 문제를 파악하고 로직을 구성하는 것은 속도가 많이 붙었다는 것이다. 다만 디테일이 조금 부족했다. 노력했다고 생각했지만 문제를 풀어본 절대적 양과 알고리즘 유형에 대한 깊이 있는 이해가 부족했다. 그래서인지 문제를 풀면서도 ..

다익스트라 알고리즘 (Using Priority Queue) 다익스트라 알고리즘의 기본 구성은 지난 포스트에서 다뤘다. 다익스트라는 한 노드에서 다른 노드들까지 가는 모든 최소 비용을 구하는 알고리즘이었다. 여기서 두 가지 과정을 반복적으로 수행하면서 목적을 달성하게 된다. 방문하지 않은 노드들 중에 가장 비용이 적은 노드를 다음 노드로 삼는다. (그리디 알고리즘) 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다. (다이나믹 프로그래밍) 여기서 방문하지 않은 노드들 중에 가장 비용이 적은 노드를 찾기 위해 최악의 경우 모든 노드를 살펴봐야 할 수도 있다는 점이 최적화할 수 있는 부분이었다. 이를 개선하기 위한 방법 중 우선순위 큐를 활용한 다익스트라를 구현해보려고 한다. 다익스트라 알고리즘 구현 (..

다익스트라 알고리즘(Dijkstra) 그래프에서 여러 개의 노드가 있을 때, 한 노드에서 각 모든 노드 까지의 최단거리를 구하는 알고리즘이다. 다만 '음의 간선' 즉, 가중치가 0보다 작은 값이 아닌 경우에 정상 작동한다. 동작과정을 살펴보면 그리디 알고리즘(매번 비용이 가장 적은 노드를 선택하기 때문)과 다이나믹 프로그래밍(DP) 기법을 함께 사용한다. 이 두 단계를 반복하면서 임의의 노드에서 각 노드까지의 최단 거리를 구하게 된다. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다. (그리디 알고리즘) 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다. (다이나믹 프로그래밍) 작동 방식에 대해서 그림으로 알아보자. 그림 1은 주어진 그래프 상태이다. 출발점은 A, 도착점은 E라고 할 때..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 문제를 보자마자 조합이구나가 떠오른게 많이 발전한 것 같다. 조금 어려웠던 점은 data에 주어지는 조건에 맞도록 어떻게 조합을 맞춰나가야 하는지가 잘 떠오르지 않았다. 그래서 가능한 조합을 모두 만든 다음, 그 조합이 data에 주어지는 조건에 부합하는지 확인하도록 했다. 또한 조건에 부합하는 조합이 없다면 0을 출력해야한다. answer를 0으로 초기화 해두고 모든 조건을 확인하고도 answer의 증가가 일어나지 않으면 조건에 맞는 것이 없는 것이다. 그대로 코드를 작성해서 통과할 수 있었다. ..