문제https://school.programmers.co.kr/learn/courses/30/lessons/152996 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이이진탐색 이용 우선 몸무게를 오름차순으로 정렬한다.이제 몸무게가 a,b (a2a = 2b (즉 몸무게가 같은 경우, a=b)문제 조건에 의해 시소의 1(m)거리 지점에 앉을 수 없으므로 2a = 2b라고 나타낸 것이다.2a = b3a = 2b4a = 3bweights 배열을 오름차순으로 정렬한 뒤 weights[i]를 하나씩 방문하고, i보다 큰 j에 대해서 weights[i]와 시소 짝꿍이 되는 경우의 수를 만족하는 weights[j..

문제https://www.acmicpc.net/problem/12852 풀이1로 만들기 풀이와 유사하지만, x에서 1까지 어떤 숫자를 선택했는지를 저장해야 한다.next[x]는 x 다음 ( /3, /2, -1) 연산을 통해 어떤 숫자가 되어야 최소 작업으로 1이 될 수 있는 지를 저장한다. package boj.dp;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Boj_12852_1로만들기2 { static int[] d; static int[] next; public static void main(String[] args) throws IOException { Bu..

문제https://www.acmicpc.net/problem/2579 풀이DP를 활용해서 풀면 된다. 문제에 나온 예제를 예로 들어보자.idx012345score[idx]102015251020 배열 d[idx] (dp)에 들어가는 값은 0부터 시작해서 idx번째 계단을 밟았을 때 얻을 수 있는 점수의 최댓값으로 정의한다. 문제 조건에 따라 마지막 계단은 반드시 밟아야 하는 상황이다.따라서 d[5]의 입장에서 시작해 보자. 5번째 계단을 밟으면 가능한 상황은 3번째 계단을 밟거나, 4번째 계단을 밟은 상황 두 가지이다.하지만 그렇다고 d[n] = max(d[n-1], d[n-2]) + score[n] 로 점화식을 세우면 안 된다. 문제에 명시된 "계단을 3개 연속해서 밟을 수 없다" 는 조건이 위배될 수 ..

최단 경로 알고리즘그래프 상황에서 vertex 간의 최단 경로를 구하는 알고리즘이다.   문제는 위와 같이 아예 그래프로 문제 상황이 주어지거나, 혹은 위와 같이 '경로'로서 문제 상황이 주어진다. 문제를 graph, vertex, edge로 표현하여 풀면 된다. 단일 출발 최단 경로특정 하나의 노드에서 다른 모든 노드까지의 최단 경로를 구하는 문제이다.  1. 다익스트라 알고리즘음수 가중치 미포함 경우에만 사용 가능하다.방문하지 않은 정점 중, 거리가 최소인(cost가 낮은) 정점을 방문한다. 정점을 방문 처리하고, 최단 거리를 확정한다.현재 처리 중인 (최단 거리가 확정된) 노드를 거쳐서 다른 노드로 가는 비용을 계산하고 갱신한다. 특징거리가 최소인 정점을 찾는 과정에서 Heap 혹은 Priority..

Spanning Tree, 신장트리란?그래프에 포함된 모든 정점(vertex)들을 포함하는 부분 그래프이다. (즉, 그래프 구성 edge만이 달라짐)모든 vertex는 적어도 하나의 edge에 연결되어 있다.트리이므로 cycle이 존재해서는 안 된다.주어진 하나의 그래프에 대해 다양한 신장트리가 존재할 수 있다.vertex의 개수 v에 대해 (v-1)개의 edge를 가진다.신장 트리는 DFS, BFS 등을 이용하여 구성할 수 있다. (탐색을 통해 방문한 정점 순서대로 신장 트리 구성) Minimum Spanning Tree, 최소 비용 신장트리가중치가 부여된 무방향 그래프에서, 신장 트리의 비용이 가장 적은 spanning tree를 최소 비용 신장트리라 한다.즉, 신장트리를 구성하는 edge들의 가중치..

문제https://school.programmers.co.kr/learn/courses/30/lessons/118667 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이첫 번째 풀이 : 실패class Solution { public int solution(int[] queue1, int[] queue2) { int middleIndex = queue1.length; int[] connectedQueue = new int[middleIndex*2]; long targetSum = 0l; for(int i=0; itargetSum) { ..

문제https://school.programmers.co.kr/learn/courses/30/lessons/42892 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이모든 노드를 y좌표가 큰 순 - y좌표가 같다면 x좌표가 적은 순으로 정렬한다. - 트리를 이루는 순서대로 정렬정렬된 노드를 하나씩 트리에 삽입한다. 이 때, x좌표를 키로 하는 이진 검색 트리의 삽입 알고리즘을 따른다.완성된 트리를 전위순회, 후위순회하여 정답을 도출한다.트리를 이루는 순서대로 정렬한다는 의미는, nodeinfo로 주어지는 1-2-3-4-5-6-7-8-9 순서의 노드들을위 그림의 7-4-2-6-1-3-9-8-5 순서대로..

플로이드-워셜(Floyd-Warchall) 알고리즘가중 그래프에서 모든 노드 쌍들에 대한 최단 경로를 구할 때 사용하는 알고리즘이다.가중치가 음/양수일 때 모두 사용 가능하다. 알고리즘 동작모든 vertex쌍 간의 최단 경로를 갱신하여야 하므로 인접 행렬을 사용한다.정점 A에서 B로 가는 경로에서 거칠 수 있는 모든 노드(K)을 확인하여 해당 노드(K)를 경유할 경우 경로 길이가 더 짧아진다면 그 값을 테이블에 갱신한다. (D[i,j] = min( D[i,j] , D[i,k]+D[k,j])3중 for문을 사용한다. (D[i,k]와 D[k,j] 에서 공통인 중간점 k를 가장 바깥 for문으로 둔다.)만일 dist[i][i] 음수 사이클이 존재한다는 의미로, 최단 거리 테이블을 확정할 수 없다.구현 방법인..

벨만-포드(Bellman-Ford) 알고리즘가중그래프에서 특정 하나의 노드에서 다른 모든 노드로의 최단 거리 정보를 알아내는 알고리즘이다. (단일 출발)모든 경우의 수를 고려하기 때문에, 다익스트라 알고리즘보다 시간복잡도가 높다.그렇지만 다익스트라 알고리즘과 달리 노드 간의 간선 가중치가 음수인 경우에도 사용할 수 있다. 알고리즘 동작 방식매 단계(cycle)마다 모든 노드(vertex)를 방문한다.하나의 노드를 방문할 때마다 이 노드와 인접한 다른 노드들을 확인하여, 최단 거리 테이블을 갱신한다. 단계는 최단 거리 테이블이 더이상 업데이트되지 않을 때까지, 최대 V-1번 반복된다. (V: vertex, 노드의 수)만일 V-1번의 단계를 거친 이후에도 최단 거리 테이블이 업데이트 된다면, 이는 음수 사이..

다익스트라(Dijkstra) 알고리즘가중그래프에서 특정 하나의 노드에서 다른 모든 노드로의 최단 거리 정보를 알아내는 알고리즘이다.음수 가중치를 갖는 간선을 포함한 그래프에서는 올바르게 동작하지 않는다. (음수 가중치가 있을 경우 최단 경로가 계속 갱신될 수 있기 때문에)구현 특징문제를 그래프로 표현하여 각 정점 연결 상황을 저장한다.정점 간 최단 거리 정보(distance)를 1차원 리스트에 저장하며 리스트를 계속해서 갱신한다.매 단계마다 아직 방문하지 않은 정점 중 최단 거리인 정점을 찾아 방문하여 최단거리를 확정하고, 이를 반복하는 방식이다.방문하지 않은 정점 중에서 최단 거리가 최소인 정점을 찾는 과정에서 Heap, Priority Queue를 이용한다.구현 방법출발 노드(s) 설정최단 거리 테이..

투포인터 알고리즘의 정의투포인터 알고리즘(Two Pointers Algorithm) 혹은 슬라이딩 윈도우(Sliding Window)라 부른다.알고리즘 문제 중 완전 탐색으로 풀면 시간초과가 나는 문제일 때, 투포인터 알고리즘을 떠올려 보아야 한다.투포인터 알고리즘에는 1차원 배열이 있고, 이 배열에서 서로 다른 두 개의 포인터를 이용해 원소에 접근하며 원하는 것을 얻는다. 예시크기가 N인 1차원 배열 arr가 있다. 이 때 arr의 부분 배열 중 그 원소의 합이 M이 되는 경우의 수가 몇 개 인지를 구해보자.이를 완전 탐색으로 모든 경우의 수를 전부 테스트하는 것은,  $O(N^2)$의 시간복잡도를 가진다.이를 투포인터 알고리즘으로 풀기 위해서1. 포인터 s(start)와 포인터 e(end)..

인접리스트로 구현된 그래프에서의 구현 package graph; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; public class ListGraph implements Graph{ int size; boolean directed; LinkedList[] adj; LinkedList[] inv; public ListGraph(int size, boolean directed) { this.size = size; // vertex의 수 this.directed = directed; // true: 방향성 그래프, false: 무방향성 그래프 adj = new ..