QQ의 다이어리

문제 https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 풀이 미로탐색과 같은 일반적인 BFS 문제인데, 상하좌우가 아닌 다른 방향으로도 체크해봐야 하는 문제. 다른 방향(말의 움직임)을 체크하는 건 한도(K번)가 정해져있으므로, 그 한도도 같이 큐에 저장해서 풀었다. 큐에 값을 2개 넣는 건 해봤는데 3개 넣는 건 있는지도 몰랐다. 값을 2개 갖는 큐는 queue q처럼 해주듯이 값을 3개 갖는 큐는 queue q 해주면 된다. ..

문제 https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 풀이 처음 생각한 방식은 #include #include using namespace std; int a, b; void bfs() { queue q; q.push({a, ""}); while (!q.empty()) { int tmp; int x = q.front().first; string op = q.front().second; q.pop(); if (x == b) { cou..

문제 https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 풀이 스택을 이용하여 풀이한다. ()의 값은 2이고, []의 값은 3이므로 여는 괄호가 나오면 괄호 모양에 따라 각각 스택에 tmp*2 또는 tmp*3을 push 한다. 닫는 괄후가 나오면 여는 괄호와 마찬가지로 tmp/2 또는 tmp/3을 스택에서 pop 한다. 코드 #include #include #include using namespace std; int main() { string ..

문제 https://www.acmicpc.net/problem/11292 11292번: 키 큰 사람 입력은 여러개의 테스트케이스로 구성되어있다. 각 테스트케이스는 첫 번째 줄에 학생의 수 N (0 >n; if(n==0) break; for(int i=0; i>s>>f; m.insert({f,s}); } float tmp=0; for(auto iter = m.begin();iter!=m.end(); iter++) { if(tmp>iter->first) break; cout

문제 https://www.acmicpc.net/problem/4470 4470번: 줄번호 텍스트에서 줄을 입력받은 뒤, 줄 번호를 출력하는 프로그램을 작성하시오. www.acmicpc.net 풀이 브론즈 4 문제지만 배울 게 있었다. 1. 화이트 스페이스 scanf("%[^\n]s",str); 를 입력하면 \n이 나올 때까지 입력받게 되어, 공백을 포함한 문자열을 입력받을 수 있다. 2. 버퍼 비우기 scanf로 입력을 받으면 버퍼가 비워지지 않아서 개행문자가 그대로 남는 등의 잘못된 입력을 받게 되는 경우가 있으므로 getchar();를 추가하여 해결할 수 있다. 코드 #include using namespace std; int main() { int n; scanf("%d",&n); for(int ..

문제 https://www.acmicpc.net/problem/17608 17608번: 막대기 아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 www.acmicpc.net 풀이 오른쪽에서 봤을 때, 몇 개의 막대기가 보이는지 맞추는 문제이다. 현재 가장 긴 막대기의 길이를 계속 업데이트해 가면서 막대기들을 하나하나 비교해 가면 된다. stack을 이용하여 풀이할 수 있는 문제이다. stack에는 가장 늦게 들어온 수가 맨 위에 존재하게 되므로 오른쪽부터 고려할 수 있게 된다. 스택의 맨 위에 있는 수가 가장 긴 막대기의 길이보다 길다면 결과값을 증가시킨다. 코드 #..

문제 https://www.acmicpc.net/problem/9933 9933번: 민균이의 비밀번호 첫째 줄에 단어의 수 N (2 ≤ N ≤ 100)이 주어진다. 다음 N개 줄에는 파일에 적혀있는 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 소문자로만 이루어져 있으며, 길이는 2보다 크고 14보다 작은 www.acmicpc.net 풀이 입력되는 문자열 중에서 특정 문자열이 반전된 문자열이 포함되었는지를 확인해야 하는 문제이다. 즉, 입력된 문자열 중 abc가 있고, cba도 있다면 이 문자열의 길이인 3과 가운데 글자인 b를 출력하면 된다. 특정 문자열이 존재하는지 아닌지를 확인하기 위해 set을 사용했다. 먼저 문자열들을 입력받아서 set에 계속 저장한다. 문자열을 입력받아서 반전 시킨 후, 그 ..

문제 https://www.acmicpc.net/problem/10826 10826번: 피보나치 수 4 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 풀이 n이 최대 10000의 값을 가지므로 연산 결과가 매우 큰 수가 될 수 있다. 일반적인 DP로 피보나치 수를 계산하는 방법을 사용하되, 결과값이 매우 큰 값이 될 수 있으므로 문자열로 연산해야한다. 코드 #include #include #include #include using namespace std; string arr[10002]; vecto..

문제 : https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 LCS는 최장 공통 부분 수열로 dp로 구현할 수 있다. 관련 포스팅은 --> https://qqs-diary.tistory.com/132 코드 #include #include #include using namespace std; int dp[1001][1001]; char s1[1001],s2[1001]; int main() { scan..

문제 https://www.acmicpc.net/problem/14490 14490번: 백대열 n과 m이 :을 사이에 두고 주어진다. (1 ≤ n, m ≤ 100,000,000) www.acmicpc.net 풀이 주어진 숫자 2개를 최대한 약분하여 출력하는 문제이다. 입력이 n:m의 형태로 주어지기 때문에 문자열로 입력받아서 : 를 기준으로 자른 후, 최대공약수를 구해야 한다. sstream 헤더만 입력하면 문자열 파싱과 문자열을 int로 바꾸는 것까지 가능하다. 두 수를 최대한 약분하려면 두 수의 최대공약수로 나눠주면 된다. 최대공약수는 유클리드 호제법으로 구할 수 있다. 두 숫자가 나누어 떨어지거나, 0이 될 때까지 나머지 연산을 반복하다 보면 최대공약수를 구할 수 있다. 코드 #include #in..