알고리즘 15

[알고리즘] 너비 우선 탐색 (BFS)

너비 우선 탐색 (BFS)너비 우선 탐색(Breadth First Search)은 시작 정점에서 가까운 노드부터 차례로 탐색하는 방식이다.먼저 방문한 노드를 기준으로 인접한 노드들을 한 층씩 넓게 탐색큐(Queue) 자료구조를 이용해서 구현한다.큐 (Queue)탐색 방식이 선입선출(FIFO) 특성을 가지기 때문에 큐가 적합하다.먼저 거리가 1인 노드를 넣어놓고, 2인 인접노드를 넣으면서 탐색.거리가 1인 (인접한) 노드부터 처리함.동작 방식인접리스트 그래프 graph 로 표현, 방문을 저장할 배열 visited 초기화큐에 시작 노드를 추가 (방문 처리)큐에서 노드를 꺼낸 후 인접 노드 탐색꺼낸 노드의 인접 노드를 큐에 저장 (추가하면 방문처리)큐가 비어있을 때 까지 반복활용 예시최단 경로(거리) 찾기레벨..

Algorithm 2025.05.11

[알고리즘] 깊이 우선 탐색(DFS)

알고리즘 개념에 대해서도 정리를 하기로 했다.이미 깃허브에도 올리고, 따로 마크다운으로 정리하지만블로그에도 추가하면서 다른 사람들도 볼 수 있고 내 블로그의 번영?을 위해서ㅋㅋㅋ 올리기로 했다. 깊이 우선 탐색 (DFS)깊이 우선 탐색(Depth-First Search)은 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.재귀함수나 스택 자료구조를 사용하여 구현한다.재귀함수깊이를 따라 들어갔다가, 막히면 되돌아오는 패턴을 가지기 때문에 재귀함수로 구현할 수 있다.쉽게 한 놈씩 한 놈만 패는 구조로 타고, 타고, 타고 들어가서 한 놈만 찾아낸다고 생각하면 쉽다.동작 방식인접 리스트 그래프로 표현, 방문을 저..

Algorithm 2025.05.08

[프로그래머스] Lv2. 문자열 압축

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 파악"aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함) "abcabcdede"와 같은 문자열은 전혀 압축되지 않음.문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법 가장 짧은 압축 단위를 찾..

[프로그래머스] LV3. 가장 먼 노드 (그래프)

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 파악n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.제한사항노드의 개수 n은 2 이상 20,000 이하입니다.간선은 양방향이며 총 1개 이상 50,000개 이하..

[프로그래머스] Lv1.같은 숫자는 싫어 (스택/큐)

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 설명배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다.이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다.단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다.예를 들면,arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다.arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다.배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 soluti..