거의 알고리즘 일기장

며칠전에 코테를 한번 볼일이 있었다. 영어로 된 문제였는데, ㄹㅇ 뭐라는지도 모르겠어서 한문제 좀 풀다가 껐다. 그래도 한때는... 열심히 풀었었는데 ㅠ 그래서 이제 백준을 다시 아주 조금씩 풀어볼까 한다. 딱 이번년도 안에 백준 플레만 가자!

www.acmicpc.net/problem/1175 1175번: 배달 어제 선물을 모두 포장한 민식이는 이제 선물을 배달하려고 한다. 민식이가 선물을 배달할 곳은 이 문제를 읽는 사람들이 앉아 있는 교실이다. 교실은 직사각형모양이고, 모두 같은 크기의 정사 www.acmicpc.net 이 문제도 달이 차오른다, 가자. 문제랑 똑같다. 메모리가 터지지않게 최대한 안될만한 데이터들을 선처리해서 큐에 넣지 않게 하는게 중요한 문제다! 전체코드 #include #include #include #include using namespace std; class BfsData { public: int y; int x; int dir; int time; int isDelivery; BfsData(){} BfsData(i..

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/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.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수� www.acmicpc.net 풀이방법 일반적인 top down 메모제이션 풀이로 풀면 됨. 전체코드 #include #include using namespace std; int A[1001]; int dp[1001]; int N; void dpInit() { for (int i = 0; i > N; for (int i = 1; i > A[i]; } int getMa..

https://www.acmicpc.net/problem/16500 16500번: 문자열 판별 첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 포함된 문자열은 알파벳 소문자로만 이루어져 있고, 길이는 100을 넘지 않는다. www.acmicpc.net 접근 이 문제를 완전탐색으로 푼다면 최악의 경우 100!으로 절대 시간안에 풀수없다. 잘 보면 중복연산이 매우매우 많으니 메모제이션을 사용하자!! 풀이방법 이 문제는 주어진 word들이 S를 만들수 있는지 없는지만 판별하면 되는 문제다. 그러므로 dp[string 길이] : -1일땐 아직 탐색안한..