적자 생존 (Write, Survive!)

[자료구조] 트리(Tree)

트리 (Tree)트리(Tree)는 노드들이 계층적으로 연결된 비선형 자료구조로, 루트 노드와 부모-자식 관계의 서브트리들로 구성된다,트리는 재귀적으로 정의된다.트리에서는 DFS가 쓰이는 경우가 좀 더 많다.용어노드 (Node): 트리의 각 요소를 말하며, 데이터(값)와 포인터(자식 노드를 가리키는 링크)를 포함한다.간선 (Edge): 노드와 노드를 연결하는 선으로, 부모와 자식 노드 간의 관계를 나타냄루트 노드(Root Node): 트리의 최상위 노드, 부모 노드가 없다. 트리는 하나의 루트 노드만 가질 수 있다.부모 노드(Parent Node): 트리 구조에서 다른 노드(자식 노드)를 가리키고 연결을 유지하는 상위 노드자식 노드(Child Node): 부모 노드로부터 파생된 하위 노드서브트리(Subtr..

[프로그래머스] Lv2. 주차 요금 계산 (HashMap)

프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 파악요금표, 차의 입/출차 기록이 주어질 때, 각 차량의 정산된 요금을 계산해서 반환하는 문제까다로운 점은 요금표는 정수형 배열, 입/출차 기록은 "차량번호 시간 in/out" 형태로 주어진다. 문제 설명은 문제 링크에서 확인!!입출력 예feesrecordsresult[180, 5000, 10, 600]["05:34 5961 IN", "06:00 0000 IN", "06:34 0000 OUT", "07:59 5961 OUT", "07:59 0148 IN", "18:59 0000 IN", "19:09 0148 OUT", "22:59 5961 IN", "23:00..

[프로그래머스] Lv2. 게임 맵 최단거리 (BFS)

프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제 파악정말 단순히 벽에 둘러싸져있는 길에서 목적지까지 최단거리를 구하는 문제제한사항maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다. 입출력 예mapsanswe..

프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제 파악2진 트리 구조의 초원에서 양을 모으는 문제늑대의 수가 같거나 더 많아서는 안된다.늑대에게 양이 잡아먹히지 않게 하면서 최대한 양을 많이 모으는 문제이다. 제한사항2 ≤ info의 길이 ≤ 17info의 원소는 0 또는 1 입니다.info[i]는 i번 노드에 있는 양 또는 늑대를 나타냅니다.0은 양, 1은 늑대를 의미합니다.info[0]의 값은 항상 0입니다. 즉, 0번 노드(루트 노드)에는 항상 양이 있습니다.edges의 세로(행) 길이 = info의 길이 - 1edges의 가로(열) 길이 = 2edges의 각 행은 [부모 노드 번호, 자식 노드 번호] 형..

개발남노씨 강사님의 수업을 듣고 있어서 예제 문제로 노씨데브에 있는 문제도 가끔 공유해주신다.이번에는 암시적 그래프의 가장 기초적인 문제인 응급차 최단거리를 가져왔다. 코딩테스트 문제 응급차 최단 거리2 - Nossi.DevNossi.Dev는 개발자들을 위한 종합 플랫폼으로, 코딩테스트 연습과 커뮤니티를 통해 취업 및 이직 준비를 돕습니다. 최신 문제 풀이, 심도 있는 토론, 그리고 전문가 조언을 통해 여러분의 커리어cote.nossi.dev 문제 파악문제 설명한 도시에 큰 사고가 발생하여 응급차가 부상자를 구조하기 위해 출동해야 합니다. 도시는 m x n크기의 이진 행렬로 표현되며, 0은 차량이 통행 가능한 도로를, 1은 통행이 불가능한 구역을 나타냅니다. 응급차는 도시의 왼쪽 위(0, 0)에서 출발..

스택 (Stack)스택(Stack)은 데이터를 저장하는 선형 자료구조로, 후입선출(LIFO, Last In First Out) 방식을 따른다.후입선출(LIFO)가장 나중에 추가된 데이터가 가장 먼저 처리되는 구조스택 = 프링글스가장 나중에 넣은 과자를 가장 먼저 꺼내는 거랑 비슷함.Push : 데이터를 스택의 맨 위(top)에 추가Pop : 데이터를 스택의 맨 위(top)에서 제거하고 반환스택 사용 방법Stack 클래스Stack 클래스는 스택 자료구조를 구현한 클래스하지만 Deque 인터페이스와 ArrayDeque을 사용하는 방식에 비해 성능적으로 떨어져 잘 사용하지 않음.스택 대신에 Deque(덱)을 많이 이용Linked List 기반 Stack 구현LinkedList는 양방향 연결 리스트이므로 스택으..

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 파악초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.제한사항prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.prices의 길이는 2 이상 100,000 이하입니다.입출력 예pricesreturn[1, 2, 3, 2, 3][4, 3, 1, 1, 0]초 단위로 기록된 주식가격이 담긴 배열 price, 가격이 떨어지지 않은 기간은 몇 초인지 return1은 5초때까지 떨어진 적이 없음 → 4초2는 오름 2, 유지 1 ..

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 파악프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.제한 사항작업의 개수..

암시적 그래프암시적 그래프(Implicit Graph)는 명시적으로 노드와 간선을 저장하지 않고, 탐색하면서 그래프 구조를 동적으로 유추하는 방식탐색 과정에서 이동 가능한 노드(정점)와 연결관계(간선)를 문제의 조건을 기반으로 판별“그래프를 그리지 않았지만 탐색할 수 있는 모든 경우의 수가 노드처럼 동작한다."그리고 "어떤 상태에서 이동할 수 있는 다른 상태들이 연결된 간선처럼 동작한다."rowLength = row 수(행 개수)는 grid의 크기colLength = column 수(열 개수)는 첫 번째 행의 크기인접리스트 없이 nextVertex 찾는 방법(암시적 그래프)현재 위치에서 상하좌우로 이동하여, 다음 노드(nextVertex)를 동적으로 찾는다.단순히 상하좌우를 탐색하다 보면 배열의 범위를 ..

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