차가운오미자님의 유리병

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=934&sca=99&page=7 JUNGOL www.jungol.co.kr 문제 이해 최단 거리를 구하는 문제이므로 BFS를 사용하면 된다. 출발지로부터 모든 상하좌우를 탐색하면서 방문하다가 목적지에 도착하면 거기까지의 거리를 return해주면 된다. 여기서 주어진 map의 0인 부분만 탐색해야 한다. 시간복잡도는 맵의 모든 부분이 0이어서 모든 곳을 탐색하는 경우 (100*100) 정도 이다. 충분히 시간 내에 해결할 수 있다. 작성 코드 #include #include using namespace std; int Y, X; int sy, sx, ey, ex; char map[100 * 10][100 * ..

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=386&sca=30 JUNGOL www.jungol.co.kr 문제 이해 현재 말의 위치에서 졸의 위치까지 최단 거리로 이동하는 문제이므로 BFS를 사용하면 된다. 모든 경우를 탐색하는 경우가 아니라, 졸의 위치에 도착하면 BFS를 끝내면 된다. 시간복잡도: 현재 위치에서 BFS를 수행하므로 약 100*100 (가로세로 최대길이)만큼을 반복할 것이다. 작성 코드(C) #include int N, M; // 행, 열 int R, C; // 말이 있는 행, 열 int S, K; // 졸이 있는 행, 열 int visited[100 + 10][100 + 10]; // 방향 벡터 int dy[] = { -2, -2..

https://www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 문제 이해 최단 거리를 구하는 문제이므로 BFS를 사용하면 된다. 모든 땅 중 두 개를 골라 그 사이의 최단거리를 구해야 하고, 그렇게 나온 최단거리들 중에 최장 거리를 고르는 것이 답이다. 그러므로 모든 땅들 중 두 개씩 짝지어서 모두 BFS를 해야한다. 시간 복잡도를 살펴보면, 가로 세로 최고 50개이니까, 50*49번의 BFS가 일어나고, 각 BFS별로 약 50*50번의 루프가 발생한다치면 25..

https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 이해 Backtracking을 하면서 모든 경우를 탐색하면 된다. DFS를 사용한다. 작성 코드 #include using namespace std; int N, M; int ans[9]; void BackTracking(int cnt){ if(cnt == M){ for(int i = 0; i

https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 이해 DFS를 이용해서 모든 수열을 구하면 된다. 작성 코드 #include using namespace std; int N, M; int visited[9]; int ans[9]; void Check(int cnt, int start){ if(cnt == M){ for(int i = 0; i

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트랙킹 알고리즘을 사용하면 된다고 한다. 백트랙킹 알고리즘은 가능한 Decision Space를 검토하면서 불가능한 상황들을 제거해 나가는 방식이다. 잘 이해는 안되고, 보통은 recursive한 문제풀이를 이용한다고 한다. 작성 코드 #include using namespace std; int N, M; int visited[9]; int ans[9]; void Check(int cnt){ ..

upper_bound https://www.cplusplus.com/reference/algorithm/upper_bound/?kw=upper_bound upper_bound - C++ Reference function template std::upper_bound default (1)template ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val); custom (2)template ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T www.cplusplus.com 배열 (vector)에서 key 값을 ..

1. iterator 사용법 vector v; 1. 선언 vector::iterator it; 2. 반복문에 사용하기 for(it = v.begin(); it != v.end(); it++){ //+, - 연산 가능) cout

https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 문제 이해 1. 나이 증가하는 순으로 정렬 2. 나이가 같으면 먼저 가입한 사람 순으로 정렬 정렬 함수를 위의 기준으로 만들면 되는데, 먼저 가입한 순서, 나이, 이름을 저장해야 해서 이중 pair를 사용했다. 작성 코드 #include #include #include #include using namespace std; int N; vector v; bool compare(pair a, pair b)..

https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 문제 이해 이것도 그냥 compare함수를 잘 설계하면 되는 문제이다. 작성 코드 #include #include #include #include using namespace std; int N; vector v; bool compare(string a, string b){ if(a.length() < b.length()) return true; else if(a.length() == ..