url : https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 크루스칼 알고리즘 코드만 작성하면 풀리는 문제이다. 크루스칼 알고리즘 vs 다익스트라 vs 플로이드 크루스칼 알고리즘은 그래프의 모든 노드를 최소한의 비용으로 연결하는 부분 그래프를 찾는다. 다익스트라 알고리즘은 한 노드에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘이고, 플로이드-워셜 알고리즘은 모든 노드에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘이다. 사용 기법 및 방..
url : https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr n이 500이하이므로 플로이드 워셜을 사용하던, 다익스트라를 사용하던 상관이 없다. 구현이 편리한 플로이드 워셜을 사용하였고, 효율성 풀이까지 통과하였다. 초기값 INF시 오버플로우 주의 거리의 초기값을 INF(매우 큰 수)를 둘 경우 초기값에 추가 값이 더해질때 오버플로우가 발생한다.(아주 작은 수(ex)-123456789)가 나온다.) 이 경우 min으로 거리 비교시 예상치 못한 값..
url : https://school.programmers.co.kr/learn/courses/30/lessons/12978 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 다익스트라 또는 플로이드 워셜로 풀 수 있는 문제이다. 플로이드 워셜이 구현이 훨씬 편리하므로 n이 500이하일 경우 플로이드 워셜로 풀면 좋다. 나의 경우에는 다익스트라로 풀었다. + 1211 플로이드 워셜 풀이 추가 그래프 문제는 조금만 익숙하지 않아도 어려워지는 것 같다. 하지만 정해진 템플릿에 기반하여 그려보며 풀면 생각보다 쉽게 풀리는 문제이기도 하다. 다익스트라 templat..
url: https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net
url : https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 www.acmicpc.net 초기 작성 코드 #include using namespace std; int n, tmp, answer; int main(){ ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); // 1.입력 받기 cin >> n; vector v(n, 0); vector dp(n, 0..
url : https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 로직 총 심사시간 / 심사 시간(단건) = 심사한 사람 수 이진탐색으로 총 심사시간의 최소값을 찾을 수 있는 이유 이진탐색은 주어진 조건(심사 시간)내에서 가능한 최적의 해(총 심사시간의 최소값)을 찾는 방법이다. => 총 심사 시간을 늘이고, 줄이면서 결국 총 심사시간의 최소값을 반환한다. 이진탐색 1. 탐색 범위 올바르게 설정 답이 될 수 있는 상한(최대 범위), 하한(최소 범위)를..
url : https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 동전 1 문제는 금액을 만드는 경우의 수이고, 동전 2 문제는 금액을 만드는 경우 중 동전의 개수가 최소인 경우의 동전 수를 구하는 문제이다. DP를 이용하여 해당 금액에 대한 최소 동전 개수를 저장하여 활용함으로써 정답을 찾을 수 있다. 코드 #include using namespace std; int n, k; int coins[10004], dp[1..
url : https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해결을 위해 dp를 사용하는 이유 k원을 만드는 방법을 구하기 위해, k원보다 작은 금액을 만드는 방법이 반복적으로 계산된다. => 중복 계산을 피하기 위해 메모이제이션, Tabulation(미리 구하기)이 필요하다. => DP 2원 동전 사용을 고려할때, 4원을 만드는 경우의 수가 dp[4] = dp[4] + dp[4-2] 인 이유 DP에서 부분 문제의 해결 개념과 관련이 있다. ..
