url: https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS = 최장 공통 부분 수열 두 문자열에서 연속적이지 않으면서 한방향(동일한 순서)로 가장 긴 공통 문자열을 찾는 문제이다. DP 유형의 고전적인 문제(유형화된 문제)라고 할 수 있다. 점화식 인덱스가 각각 0~i, 0~j라고 할 때, dp 배열을 채워보자. 직전 문자 (각각 i-1 위치 문자와 j-1 위치 문자)가 같다면, i와 j위치 문..
url : https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 골드 5인데, 이진탐색 template을 알고있다면 풀 수 있는 문제이다. 최솟값, 최댓값 구하기 최솟값을 구할 경우 초기값은 최댓값(ex)합의 최댓값 or int 최댓값)으로, 최댓값을 구할 경우 초기값은 최솟값(ex)합의 최소 or int 최소값)으로 설정하기 이진탐색 Tip 이진탐색은 1. 조정해야하는 값(문제에서 구하는 값)의 상한과 하한을 구하..
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. 탐색 범위 올바르게 설정 답이 될 수 있는 상한(최대 범위), 하한(최소 범위)를..
