https://www.acmicpc.net/problem/11659 [11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net](https://www.acmicpc.net/problem/11659) 0. 알고리즘 분류 누적 합 1. 문제 2. 풀이 https://blog.naver.com/kks227/220787178657 해당 블로그를 참고했다. 문제는 쉬웠다. cin과 cout을 써서 시간초과가 났던 것만 빼면.. 3. 코드 #include using namespace std; int a[10..
생각없이 문제푸는 거에 충족감도 들고, 머리가 회전한다는 느낌도 들어서 풀면 기분은 좋다. 하지만, PS만으로 취직을 할 수도 없을테고.. 다른 공부도 다시 시작해야된다.. 강화학습 다시 해야지...
https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 0. 알고리즘 분류 그래프 이론, 자료 구조, 그래프 탐색, 분리 집합 1. 문제 2. 풀이 유니온 파인드(Union-Find) 문제다. 그래프 문제이기도 하지만, 그냥 유니온 파인드에 익숙해지라고 준 문제인듯 하다. 그냥 풀면 된다. 3. 코드 #include using namespace std; int p[201]; int find(int i) { if (p[i] == 0) { return i..
https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 0. 알고리즘 분류 다이나믹 프로그래밍 1. 문제 2. 풀이 LIS(가장 긴 증가하는 부분 수열) 문제와 비슷한 유형인줄 알고 시도했다가 제대로 대가리 깨졌다. 문제의 개념은 비슷할지마도 사용하는 알고리즘은 완전히 다르다. 몰라서 역시 구글링했다. http://melonicedlatte.com/algorithm/2018/03/15/181550.html ..
https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 0. 알고리즘 분류 이분탐색, 가장 긴 증가하는 부분 수열(o(n log n)) 1. 문제 2. 풀이 11053번: 가장 긴 증가하는 부분 수열 의 연장선 문제다. 단순하게 수의 범위(1000에서 1000000으로)만 증가했다. 코드에서 차이점은, 11053번은 이분 탐색을 직접 구현하여 풀었지만 12015번은 stl의 lower_bound를 사용했다. 오름차순 정렬된 배열에서 어떤 값 이상의 숫..
https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 0. 알고리즘 분류 이분 탐색 1. 문제 2. 풀이 이분탐색 문제이다. 당연하게도, 문제에서 제시하는 순서대로 배열을 만들고 정렬하고 찾으면, 시간초과가 나온다. 필자는 도대체 어떻게 이분탐색을 쓰면 이 문제를 풀 수 있는지 생각해내지 못했다.. 결국 또 구글링이다. 구글링한 결과, 필자로서는 생각조차 못했던, 생각보다도 간단하게 풀리는 문제가 야속했다. left =..
https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 0. 알고리즘 분류 다이나믹 프로그래밍 1. 문제 2. 풀이 11053과 같은 LIS 문제이다. 처음 봤을 땐 이게 왜 LIS 문제인지 싶었는데, (구글링으로)무작위로 주어진 전깃줄 연결을 A 전봇대에서 오름차순으로 정렬하면, B 전봇대에서 값이 작아지면 줄이 꼬인다는 것을 의미한다. 즉, B 전봇대에서 가장 긴 증가하는 부분 수열을 구하고, N에서 이 값을 빼면 우리가 원하는 답이 나온다. 문제를 풀 ..
https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 0. 알고리즘 분류 다이나믹 프로그래밍 1. 문제 2. 풀이 제목에서 보이다시피, 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence) 문제이다. 개념을 몰라서 구글링으로 배웠다. 하나의 배열을 만들고, 여기에 입력값을 증가하는 순으로 쌓는다. 만약 작은 값이 들어오면 이분탐색으..
https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 0. 알고리즘 분류 자료 구조, 분리 집합 1. 문제 2. 풀이 유니온 파인드(Uniono-Find)를 이용하는 기본 문제이다. SCPC 1번문제가 유니온파인드를 사용한 문제였어서 공부했다. 개념 자체는 어렵지 않다. 두 집합을 합하는 union 연산과 부모를 찾는 find 연산 뿐이다. 3. 코드 #include using namespace std; in..
