거의 알고리즘 일기장

programmers.co.kr/learn/courses/30/lessons/42748 코딩테스트 연습 - K번째수 [1, 5, 2, 6, 3, 7, 4] [[2, 5, 3], [4, 4, 1], [1, 7, 3]] [5, 6, 3] programmers.co.kr 간단하므로 풀이방법 생략하겠음. 코드 #include #include #include using namespace std; vector solution(vector array, vector commands) { vector answer; for (auto ele : commands) { int _i = ele[0] - 1; int _j = ele[1] - 1; int _k = ele[2]; vector temp; for (int i = _i;..

programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 풀이방법 문제는 최대힙으로 풀라고 권장하지만 multiset으로 푸는편이 더 깔끔하고 쉬워서 그렇게 풀었다. 참고로 multiset은 자동 정렬이 된다. 코드 #include #include #include #include #include using namespace std; vector solution(vector operations) { vector answer; multiset container; for (auto ele : operations) { if (ele[0] == 'I') { string strNum = ele.substr(2, ele...

programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를�� programmers.co.kr 풀이방법 프로그래머스의 heap관련 문제다. 작업 시간이 큰게 우선순위로 작업해야 한다는 것만 알면 어렵지는 않은 문제였다. 로직은 다음과 같다 1. 현재 시각보다 작거나 같은 시작시간을 가진 값들을 priority que에다 넣는다. 2. priority que가 비어있지 않을때는 priority que의 값을 뱉는다. 3. priority que가 비어있다면 현재..

https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 문제 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다. 어떤 사이 www.acmicpc.net 풀이방법 유니온 파인드에 size만 추가로 쓰면 되는데, 입력방식이 string이라 string을 키로 받고 value가 int인 map을 하나 선언해서 쓰면된다. c++에서 cin, cout을 쓰는 경우 cin.tie(NULL), ios::sync_with_stdio(false)를 꼭 쓰기바람. 코드 #include #include #include #include using namespace std; ..

https://www.acmicpc.net/problem/13306 13306번: 트리 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 트리의 정점의 개수와 질의의 개수를 나타내는 두 정수 N과 Q (1 ≤ N, Q ≤ 200,000)가 주어진다. 다음 N-1개의 줄의 i번째 줄에는 정점 i+1의 부�� www.acmicpc.net 풀이방법 문제가 구하라는 바는 다음과 같다. 1. 간선을 끊어라. 2. 경로가 있는지 확인해라. 이 문제는 간선을 모두 끊으므로, 먼저 간선을 모두 끊어놓고 주어진 물음들을 반대로 실행하면 쉽게 정답을 구할수있다. 코드 #include #include #include #include using namespace std; stack order; stack ans; int ..

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이방법 풀이 방법은 간단하다!! 1. BACK과 FOWARD를 multiset의 자료구조로 선언한다. 2. input이 들어왔을때 세가지의 조건에 따라 달리 넣어주면된다. 1. MID값이 비어있을때 2. FOWARD.SIZE >= BACK.SIZE 일때 3. FOWARD.SIZE < BACK.SIZE 일때 3. FOWARD의 맨 뒤의 값과 BACK의 맨앞의 값 그리고 MID의 값..

https://www.acmicpc.net/workbook/view/2052 문제집: N과 M (baekjoon) www.acmicpc.net 풀이방법 이 N과 M의 풀이방식이 다 똑같고 중복이나 오름차순? 같은 추가 옵션들만 추가해주면 됨. 그러므로 N과 M(12) 소스코드를 참고하시길 바란다. 코드 #include #include #include using namespace std; int N, M; vector num; vector answer; bool isVisited[9]; bool cmp(const vector& a, const vector& b) { for (int i = 0; i < M; i++) { if (a[i] == b[i] && i !=M-1) continue; return a[i..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc...

https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 풀이방법 1. 연산을 사용하는 횟수의 최솟값을 찾고 2. 1에서 이용한 dp값을 역추적해서 경로를 찾는다. 코드 #include #include #define MAXN 1000000 #define INF 987654321 using namespace std; int dp[MAXN + 1]; int N; void dpInit() { for (int i = 1; i

https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 풀이방법 이 문제는 간단하다. 일단 최장 수열을 저장할 vector를 하나 만들었다. (arr이라고 약칭하겠다.) 그리고 두가지 조건을 통해서 arr을 채워가면 된다. 1. 만약 입력받은 숫자가 arr의 끝에 있는 수보다 크면, arr에 추가 2. 입력받은 숫자가 arr의 끝에 있는 수보다 작다면, arr의 값들 중에서 같거나 가장 차이가 적게나는 큰숫자를 찾아 바꿔..