문제 링크 https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 풀이 과정 문제에 주어진 그림을 보자 마자 바로 그래프 자료구조로 접근했다. https://born2bedeveloper.tistory.com/42 [JAVA] 그래프 구현하기 (인접 행렬, 인접 리스트) 그래프(Graph)란? 그래프는 vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex : 정점 edge : 정점과 정점을 연결하는 간선 아래는 대표적인 그래프 종류들의 예시다. 이러한 그래프는 인접 ..

그래프(Graph)란? 그래프는 vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex : 정점 edge : 정점과 정점을 연결하는 간선 아래는 대표적인 그래프 종류들의 예시다. 이러한 그래프는 인접 행렬, 인접 리스트 방식으로 표현할 수 있다. 그래프 구현 - 인접 행렬 먼저, 행렬로 구현하는 방식을 살펴보자 정점 a와 정점 b를 잇는 간선이 있을 경우, 행렬(a,b)에 1을 표기해준다. 만약 가중치가 있는 그래프라면 1 대신 가중치를 넣을 수 있다. 기본적으로 무방향 그래프의 경우는 (a,b) (b,a)에 모두 간선 값을 넣지만, 방향 그래프같은 경우는 위의 표와 같이 방향에 맞는 간선만 표기한다. ex) 정점 1과 3을 잇는 간선이 존재할 때 : graph[1][3] = 1, gr..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/43236 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 이 문제 역시 제한사항을 보면 1,000,000,000 이하 라는 어마어마한 범위를 가지고 있다. 즉, 완전탐색으로는 백퍼센트 타임오버라는 것이다. 따라서 효율적으로 값을 찾을 수 있는 이분 탐색을 사용할것이다. 이분 탐색 https://born2bedeveloper.tistory.com/40 [프로그래머스] 입국심사-JAVA 문제 링크 ..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 문제의 제한사항을 보면 1,000,000,000이라는 택도없이 큰 숫자가 등장한다. 보통 제한사항의 숫자가 큰 경우에는 완전탐색등의 방법을 쓰면 경우의 수가 어마무시하게 커지게 될 것이다. 이런 경우에는 효율적인 알고리즘을 채택해야 하는데, 필자는 이 문제에서 '이분 탐색'을 선택했다. 이분 탐색 이분 탐색은 일련의 데이터들 중에서 하나의 값을 찾을 때..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42897 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 programmers.co.kr 이 문제는 동적계획법으로 풀이하였다. 풀이 방법 이 문제의 분기점은 처음 도둑질을 할 때, 첫 번째 집을 고르냐, 두 번째 집을 고르냐에 따라 크게 두가지로 나뉜다. 인접한 집은 털 수 없다는 제한으로 두 경우로 나뉘어 집을 터는 루트가 정해지기 때문이다. 필자의 풀이 방법을 그림을 통해 자세히 보도록 하자. 왼쪽에 보이는대로, 처음 세 개의 집은 터는..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr Dynamic Programming(동적 계획법)을 이용하여 풀었다. 풀이 방식 개인적으로 로직을 짜기 제일 까다로웠던 문제중 하나였던 것 같다. 필자는 이 문제를 'N을 사용한 횟수'를 기준으로 나눠 풀이하였다. 즉 N이 5라면, 5를 1번, 2번, 3번...8번(문제 조건에 8보다 크면 -1리턴이기 떄문)사용해서 만들 수 있는 숫자들의 경우로 나눈 것이다. 박스가 8개 있다고 해보자. 1번 박스에는 N을 1번 사용해서 만들 수 있는 숫자들이 담겨있다. N = 5라고 한다면 1번 박스에는 5만 담겨있을 것이다. 2번 박스에서는 ..