https://school.programmers.co.kr/learn/courses/30/lessons/42883 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 그리디 알고리즘을 사용하기 위해서는 아래와 같이 2가지 조건을 만족해야 한다. 1) 탐욕 선택 속성(Greedy Choice Property) 2) 최적 부분 구조(Optimal Substructure) 1)은 이전의 선택이 이후에 영향을 주지 않음을 의미하며, 2)는 부분 문제의 최적결과가 전체에도 그대로 적용될 수 있어야 한다는 것이다. 1개 제거 2개 제거 3개 제거 4개 제거 1924..
https://school.programmers.co.kr/learn/courses/30/lessons/42862 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 2
1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이 최단 경로를 구하는 문제지만, 특정 정점을 지나는 최단 경로의 길이를 구해야 한다. 1번 정점 -> N번 정점의 최단 경로를 구해야 하는데, 두 정점 v1, v2를 거치는 최단 경로를 구해야 한다. 즉 위 조건을 만족하는 1번 정점 -> N번 정점의 최단 경로는 두가지가 있다. 1. 1 -> v1 -> v2 -> N 2. 1 -> v2 -> v1 -> N 그렇다면 각 정점부터 정점까지의 최단 경로를 구해서, 모든..
1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 풀이 그래프 최단 경로를 구하는 다익스트라 알고리즘을 사용하여 푸는 문제다. 인접리스트, PriorityQueue, 각 정점까지의 최단 경로를 저장하는 dis 배열을 사용하여 풀었으며 자세한 풀이는 이전에 풀었던 문제와 같기 때문에 설명은 생략하겠다. [프로그래머스] Lv.2 : 배달 (그래프 최단 경로 알고리즘) - 자바[Java] [프로그래머스] Lv.2 : 배달 (그래프 최단 경로 알고리즘) - 자바[Java] http..
https://school.programmers.co.kr/learn/courses/30/lessons/12978 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이1 : 다익스트라 - 순차 탐색, 인접 배열 최단 경로 알고리즘을 사용하여 1번 마을부터 각 마을까지의 최단 시간(경로)를 구해야 한다. 최단 경로 알고리즘이란 주어진 그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘이다. 대표적인 최단 경로 알고리즘은 3가지가 있다. 다익스트라 알고리즘 (default, 가중치가 모두 양수 = 음수X) 벨만 포드 알고리즘 (dista..
https://softeer.ai/practice/6291 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 풀이기본적인 그리디 문제다.강의가 끝나는 시간으로 정렬빨리 끝나는 것부터 먼저 함(선택)그 다음 강의 시작시간이, 그 전 강의 종료시간보다 크거나 같으면 선택종료시간 오름차순으로 정렬한 다음, 시작시간 오름차순으로 정렬되도록 한다.로직1. 강의의 시작시간과 종료 시간을 저장하기 위한 클래스 Lecture를 만든다. Lecture는 종료시간 오름차순으로 정렬한 다음, 시작시간 오름차순으로 정렬되도록 한다.2. 강의의 개수 n을 입력받는다.3. 강의의 정보를 저장할 List lectures를 선언한다.4. n개의 강의의 시작시간과 종료시간을 입력받는다.5. lectures를 정렬한..