적자 생존 (Write, Survive!)

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

프로그래머스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 ..

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

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

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

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

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

프로그래머스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..

백엔드 프로그래밍 언어인 java를 사용하기 위해서는 Openjdk를 설치해야 한다.쉽게쉽게 설치를 진행해보자!1. Homebrewbrew 명령어를 사용하기 위해서 Homebrew를 먼저 설치해야한다.https://brew.sh/ko/ HomebrewThe Missing Package Manager for macOS (or Linux).brew.sh Homebrew 설치 명령어/bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)" 설치 오류메시지Warning: /opt/homebrew/bin is not in your PATH. Instructions on how to configure ..