JUINTINATION

1번 문제: K번째https://school.programmers.co.kr/learn/courses/30/lessons/42748 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구해야 한다.예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]이다.1에서 나온 배열을 정렬하면 [2, 3, 5, 6]이다.2에서 나온 배열의 3번째 숫자는 5이다.배열 array, [i, j, k]를 원소로 가진 2차원..

1번 문제: 더 맵게https://school.programmers.co.kr/learn/courses/30/lessons/42626 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만든다.섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최..

1번 문제: 같은 숫자는 싫어https://school.programmers.co.kr/learn/courses/30/lessons/12906 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이각 원소는 숫자 0부터 9까지로 이루어진 정수 배열 arr에서 원소들의 순서를 유지한 상태로 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거한 후 남은 수들을 return 하는 solution 함수를 완성해야 한다. 예를 들면,arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 한다.arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 한다.접근스택..

1번 문제: 폰켓몬https://school.programmers.co.kr/learn/courses/30/lessons/1845 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이 N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, 가장 많은 종류의 폰켓몬 N/2마리를 선택하는 방법을 찾아 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 메서드를 완성해야 한다.폰켓몬은 종류에 따라 번호를 붙여 구분하며, 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리..

APSP(All-pairs shortest paths) 알고리즘이란? 어떤 그래프에서 모든 노드(시작 노드)부터 각각의 노드(도착 노드)까지의 모든 최단거리를 구하는 알고리즘이다. 여러 APSP 알고리즘 중에서 2가지를 살펴보겠다. 모든 정점에서 SSSP 알고리즘 실행하기 모든 정점에서 SSSP 알고리즘을 실행해야 하기 때문에 |V| 만큼 시간 복잡도가 증가한다. Dijkstra’s algorithm(음의 간선 X): O(|V||E| + |V|² log |V|) Bellman-Ford algorithm(음의 간선 O, 음의 사이클 X): O(|V|²|E|) DAG Shortest Path using Topological Sort: O(|V|² + |V||E|) 음의 사이클이 존재하지 않는 경우 Floyd..

SSSP(Single-source shortest paths) 알고리즘이란?어떤 그래프에서 시작 노드부터 도착 노드까지의 최단거리를 구하는 알고리즘이다.SSSP 알고리즘은 대표적으로 3가지로 나눌 수 있다.그래프에 음의 간선이 없는 경우Dijkstra’s algorithm: O(|E| + |V| log |V|)음의 사이클이 존재하지 않는 경우Bellman-Ford algorithm: O(|V||E|)DAG(Directed Acyclic Graph, 유향 비순환 그래프)의 경우One pass of Bellman-Ford: O(|V||E|)DAG Shortest Path using Topological Sort: O(|V| + |E|)다익스트라 알고리즘(Dijkstra's Algorithm)dijkstra(..