인생자취

1. 들어가기Java.util.Arrays 클래스에는 sort()가 있다. Arrays.sort()를 호출하면 배열을 정렬할 수 있다.위 [사진 1]을 통해 sort()는 DualPivotQuicksort로 정렬이 이뤄진다는 것은 쉽게 찾아볼 수 있고, JAVA에서 제공하는 API를 사용하는 정도로만 알고 있었기 때문에 정렬에 대한 더 자세한 구현에 대해서는 크게 관심을 갖지 않았었다. 그런데 새로운 사실을 알게 되었다. Arrays.sort()와 관련하여 JAVA API 문서에 다음과 같이 적힌 내용 때문이다.All elements in the array must implement the Comparable interface.[사진 2]와 [사진 3]을 통해 Comparable interface가 이렇..

본 문제는 벨만 포드 알고리즘 개념으로 해결할 수 있는 최단경로문제입니다. 벨만 포드 알고리즘에 대한 개념은 아래 링크로 확인해주시고, 문제를 바로 풀어보도록 하겠습니다. 2023.07.14 - [개발/Dev | 알고리즘] - 최단 경로 문제 (2) 벨만-포드 알고리즘을 중심으로 최단 경로 문제 (2) 벨만-포드 알고리즘을 중심으로 1. 들어가기 지난 글에서는 경로의 가중치가 음이 아닌 수로 부여된 경우에 사용되는 다익스트라 알고리즘에 대해 살펴봤다. 이번 글에서는 경로의 가중치가 음수인 경우에 단일 출발지의 최단 24h-daily-life.tistory.com 1. 문제 이해 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수..

1. 들어가기 지난 글에서는 경로의 가중치가 음이 아닌 수로 부여된 경우에 사용되는 다익스트라 알고리즘에 대해 살펴봤다. 이번 글에서는 경로의 가중치가 음수인 경우에 단일 출발지의 최단 경로 문제를 해결하는 벨만-포드(Bellman-Ford) 알고리즘에 대해 알아볼 것이다. 2. 벨만-포드(Bellman-Ford) 벨만-포드 알고리즘은 출발 점으로부터 도달 가능한 음의 가중치의 순환(음수 사이클)이 존재하는 경우에는 최단경로를 구할 수 없고, 그러한 순환이 없다면 최단 경로들과 그 경로들의 가중치를 계산할 수 있다. 벨만-포드 알고리즘은 매번 모든 간선을 확인하므로 다익스트라 알고리즘보다는 느리다. 시간 복잡도는 O(VE); E는 경로(간선) 수, V는 꼭짓점(노드)의 수 이다. 하지만 간선이 음수로 존..

1. 들어가기어떤 A지점에서 다른 B지점으로 이동하는 경로는 다양할 수 있다. 이는 네트워크에서도 마찬가지로 적용되는 부분이다. 연결 경로가 다양하게 존재할 수 있다. 경로가 다양하게 존재할 수 있는 가운데, 주목해야할 것은 가장 짧은 경로의 경우다. 이를 최단 경로라고 부른다. 최단 경로 문제는 다양한 경로 중 적은 비용으로 빠르게 이동하는 경로를 찾는 문제다. 이번 글에서는 최단 경로의 개념 및 이와 관련된 다익스트라 알고리즘에 대해 알아보고, 예제 문제를 살펴볼 것이다. 2. 최단경로어떤 가중치가 부여된 방향 그래프가 있다고 하자. 가중치가 부여된 그래프의 비용은 가중치를 계산하여 최단거리를 결정할 수 있다. 이때 가중치를 비용이라고 한다면 경로의 합이 가장 적은 경우가 최단 거리가 된다. 그리고 ..

이 문제는 해법이 아기 상어 노래처럼 깜찍하게 나오지 못한 문제였다. 그 이유는 필자가 BFS를 문제에서 제시한 내용에 맞게 사용하지 못하였기 때문이다. 그래서 게시글로 작성함을 통해 BFS 개념으로 문제를 풀어냈다. 독자도 이 경우에 해당한다면, 아래 태그된 링크를 통해 개념을 먼저 파악한 후 본 문제를 풀어보도록 하자. 2023.07.12 - [개발/Dev | 알고리즘] - 그래프 탐색 알고리즘 (3) 너비 우선 탐색을 중심으로 그래프 탐색 알고리즘 (3) BFS 를 중심으로 1. 들어가기 지난 시간에 이어서 그래프 탐색 알고리즘에 대해서 다뤄볼 것이다. 이번 글에서는 너비 우선 탐색(BFS;Breadth First Search)을 다뤄보겠다. 너비 우선 탐색은 시작 점으로부터 트리와 가 24h-da..

1. 들어가기지난 글에 이어 그래프 탐색 알고리즘에 대해서 다뤄볼 것이다. 이번 글에서는 너비 우선 탐색(BFS;Breadth First Search)을 다뤄보겠다. 너비 우선 탐색은 시작 점으로부터 트리와 가까운 꼭짓점을 모두 탐색한 뒤, 먼 꼭짓점까지 확장하는 규칙을 가지고 있다. 이와 관련해서 좀 더 자세하게 알아보자. 2. 너비 우선 탐색너비 우선 탐색은 시작점으로부터 인접한 꼭짓점을 모두 탐색하고, 인접한 꼭짓점을 시작으로 다시 인접한 꼭짓점들을 탐색하는 탐색이다. 다시 말하면, 깊이가 1씩 증가함에 따라 시작점과 가장 가까운 노드들을 모두 탐색하는 기법이라고 볼 수 있다. 깊이 우선 탐색의 시작점을 기준으로 최대 깊이를 우선으로 탐색하는 기법과는 대조적이다. 너비 우선 탐색도 예시를 통해 알아..

1. 들어가기 지난 글에서는, 그래프에 표시된 모든 노드를 탐색하는 방법으로 시작점을 기준으로 가장 먼 곳을 탐색하는 방법인 DFS를 살펴봤다. 필자는 이번 글에서 DFS를 베이스로 하여, N-Queen 문제를 통해 백트래킹을 적용하는 방식을 살펴볼 것이다. DFS로 완전탐색을 하지만, 백트래킹을 통해 탐색의 필요 여부를 따져볼 수 있다. 탐색의 필요 여부는 다음 예에서 확인해 볼 경우로 계산만 해봐도 뚜렷하게 알 수 있다. 5X5 체스판에 퀸이 놓일 수 있는 경우를 계산한다면, 모든 경우의 수는 5^5 가지가 되는데, 백트래킹으로 조건을 둔다면, 필요하지 않은 경우에 대해서는 더 따져볼 필요가 없게 된다. 그래서 경우의 수가 위의 값 보다는 확연하게 줄어들게 된다. 이와 관련해서 더 자세하게 살펴보도록..

1. 들어가기 그래프에 표시된 모든 노드를 탐색하는 방법으로는 시작점을 기준으로 일정한 방향으로 탐색하는 것이 효율적이다. 이때, 효율적인 탐색 방법으로는 깊이 우선 탐색(DFS;Depth First Search)과 너비 우선 탐색(BFS;Breadth First Search)이 대표적이다. 필자는 이번 글에서 깊이 우선 탐색 알고리즘을 중심으로 다뤄볼 것이다. 2. 깊이 우선 탐색 그래프 정점(꼭짓점)이 1, 2, 3, 4, ... , N 개가 있다고 하자. 깊이 우선 탐색은 시작점을 1 이라고 할 때, 1 에서 인접한 꼭짓점 중 아직 탐색하지 않은 꼭짓점 2에 방문하고, 꼭짓점 2에 인접한 꼭짓점 중 아직 탐색하지 않은 꼭짓점 3를 반복한다. 이때 인접한 모든 꼭짓점을 방문한 경우, 이전에 마지막으로..

좋은 개발자가 되는 길은 멀고도 험하다. 매일 치르는 코딩테스트도 그렇고, 평생을 공부해야하는 개발직군에서 일하면서 최근 한달동안 공부한 만큼을 공부했을까 싶다. 짬을 내서 심도 있게 공부한 적은 있었으나, 지금 생각해보면 부족했다. 낮/밤이 바뀌는지도 모를만큼 몰두한 날들을 돌아보니, 지난달을 회고하는 글을 꼭 남겨놔야겠다는 생각이 들었다. 좋은 개발자가 되는 본 과정을 수료하기까지 남은 5개월도 지금의 마음을 잃지 말라는 바람을 더해서 말이다. 1. 언어적응을 위한 문제풀이 언어를 이것저것 사용하면서 언어에 대한 이해도의 깊이는 얕았다. 게다가 언어 전환이 빠르게 이뤄지지 못해서 엄청나게 고생을 해왔다. 개발 언어 학습에서 임계점까지는 빨리 도달하지만 중급의 시작인 임계점을 넘지 못한 언어들만 알고 ..

1. 들어가며 백엔드 신입 개발자가 쌓아야 하는 역량은 자료구조와 알고리즘을 이해하고 있고, 이를 코드에 적용하는 것이다. 게다가 시간복잡도는 낮고, 코드는 잘 읽히게 코드 컨벤션을 고려해서 코드를 작성해낼 줄 안다면 기본은 갖추고 있다고 할 수 있을 것이다. 그래서 정해진 시간 내에 알고리즘과 자료구조를 잘 녹여낸 코드를 작성해내는 역량이 중요하다보니, 실무 전에 개발 역량을 코딩테스트로 체크하기도 한다.(기업 by 기업이지만, 필자는 코딩테스트를 요구하는 기업에 지원하여 코딩테스트를 여러번 본 경험이 있다. 애석하게도 통과된 적은 아직 없다.) 코딩테스트는 앞서 언급한 자료구조, 알고리즘을 잘 이해하고 있는지를 정량적으로 평가할 수 있다보니, 채용 시스템에서 인터뷰 전에 코딩테스트를 응시하도록 하고 ..