QQ의 다이어리

문제 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 풀이 플로이드 와샬 알고리즘을 이용해서 푸는 문제이다. 플로이드 와샬은 시작에서 목표로 가는데 이 사이에 어떠한 중간지점을 껴서 가는 게 더 짧다면 이 짧은 거리로 경로를 갱신함으로써 최단 경로를 탐색하는 알고리즘이다. 3중 for문을 돌면서 모든 정점을 비교해보면 된다. 입력으로 같은 경로의 다른 비용인 입력이 주어질 수 있으므로, graph 배열에 저장할 때, 현재 저장되어 있는 값보다 ..

1. 플로이드 워셜 * 이론 모든 지점에서 다른 지점까지의 최단거리를 계산할 때 쓰임. 시작지점을 잡고 목표지점을 잡는다 시작에서 목표로 가는데 이 사이에 어떠한 중간지점을 껴서 가는 게 더 짧다면 이 짧은 거리로 경로를 갱신 이거를 모든 곳에서 함 (모든 시작 모든 목표 모든 중간에서 함) 비어있는 곳은 엄청큰수(inf)로 설정 후 진행 * 구현 for문 세 개 쓰면 됨(중간 - 시작 - 끝 순서로) 만약 그래프의 특정 경로가 중간 지점 거친 경로보다 더한 게 더 크면 갱신 for (int k=0; k 노드 개수 많으면 쓸 수 없음 2. 다익스트라 * 이론 1개의 노드에서 다른 모든 노드로 가는 최단거리 하나의 최단거리를 구할 때 이전까지 구했던 최단 거리 정보를 이용한다. 현재까지 알고 있던 최단 경..

문제 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..

DFS는 스택/재귀로 구현 가능 -> 모든 노드 방문 BFS는 큐로 구현 가능 -> 최단 거리 1. 흐름 1) DFS - 재귀 시작 노드 받아서 방문했다 표시해주고 그래프 사이즈만큼 돌면서 그 그래프에 붙어있는 애들 하나씩 빼서 만약 방문하지 않은애면 다시 dfs 돌기 2) DFS - 스택 시작값 스택에 넣고, 방문했다 표시 스택이 빌때까지 스택의 맨 위에 있는 애한테 붙어있는 애들 하나씩 빼서 만약 방문하지 않았으면 방문했다하고 스택에 추가 더이상 방문하지않거나, 인접한 노드 없으면 스택에서 pop 3) BFS 시작 노드 받아서 큐에 넣고 방문했다 표시 큐가 빌때까지 큐의 앞에서 값 빼내고 아까 빼낸애한테 붙어있는 애들 개수만큼 돌면서 하나씩 빼내서 방문하지 않은애면 큐에 넣고 방문했다 표시 2. 구현..

문제 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에 계속 저장한다. 문자열을 입력받아서 반전 시킨 후, 그 ..