거의 알고리즘 일기장

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의 값들 중에서 같거나 가장 차이가 적게나는 큰숫자를 찾아 바꿔..

https://www.algospot.com/judge/problem/read/JLIS algospot.com :: JLIS 합친 LIS 문제 정보 문제 어떤 수열에서 0개 이상의 숫자를 지운 결과를 원 수열의 부분 수열이라고 부릅니다. 예를 들어 '4 7 6'은 '4 3 7 6 9'의 부분 수열입니다. 중복된 숫자가 없고 오름 차순으로 www.algospot.com 접근 첫번째 아이디어 수열을 합치는게 어떨까 생각했다. 하지만 더 곰곰히 생각해보니 어떻게 합칠지와 시간면에서 통과하는 방법은 아닐것으로 생각되어 패스했다. 두번째 아이디어 일반적인 LIS를 구하는 방식에서 두 수열을 모두 살펴본다. (종만북의 풀이) 풀이방법 그냥 LIS와 다를것 없는 풀이방식이다. 다만 모든 원소들은 32비트 부호 있는 ..

풀이방법 A : 1 + 2 + 4 + .. + 2^k-1의 축적합을 구해서 주어지는 수를 나눠주면 된다. 주의사항으로는 int의 범위값을 넘기때문에 담는 배열을 long long으로 만들어주면된다. 축적합은 30까지만 만들어주면 주어진 범위 넘으니 30까지만 만들어주자. #include #include #include using namespace std; long long aSum[31]; void ASumInit() { for (int i = 1; i num; solve(num); } return 0; } B : n%4 == 0이여야 조건중 하나인 배열의 1~n/2까지 누적합 *2 = 배열의 1~ n까지의 누적합이 성립한다. 이제 no는 문제가 없고 yes일때 list를 생각해면 나같은 경우에는 만약에..