메모장

개요 https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 실버2 난이도 문제다. 풀이 2를 곱하기, 1을 가장 오른쪽에 추가하기 두 가지의 선택지가 있다. 어느 선택지가 먼저일지 알 수 없으므로 모든 경우의 수를 따져봐야 한다고 판단했다. 그래서 BFS를 사용했다. n * 10 + 1과 n *2를 큐에 넣으며 BFS 하면 된다. n의 int형 overflow 때문에 한 번 틀렸다. long long으로 해결했다. 코드 #include #include using namespace std; struct Node { long long n; int cnt; }; long long..

개요 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 골드4 탐색 문제다. 풀이 1697번 숨바꼭질 위 문제와 거의 유사하고, 차이점으로 가장 빠른 방법의 수를 추가로 출력해주어야 한다. 가장 빠른 경로가 탐색이 됐을 때, ans 변수에 시간(cnt)을 저장한다. 만약 도착지에 도착했을 때 걸린 시간과 ans의 시간이 일치할 경우 경우의 수(ansCnt)를 증가시킨다. 시간이 ans를 넘은 경우의 수는 co..

개요 https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 골드4 탐색문제다. 풀이 13549번 숨바꼭질 3 위 문제와 유사하지만, 가장 빠른 경로도 함께 출력해야하는 차이점이 있다. 처음에는 원소(구조체)마다 queue route를 추가해서 원소마다 루트를 계속 추가시키고, 도착했을때 해당 원소의 route를 출력시키는 식으로 구현했다. 결과는 시간 초과,, 이전 위치를 저장하는 parent 배열을 만들었다. 계속..

개요 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 골드5 탐색 문제다. 풀이 1697번 숨바꼭질 위 문제와 거의 유사하지만 순간이동을 할때 시간이 증가하지 않는 다는 차이점이 있다. 똑같이 BFS로 풀었지만, 순간이동을 먼저 큐에 넣어주어 경우의 수를 먼저 탐색할 수 있도록 했다. 코드 #include #include using namespace std; constexpr int LIMIT = 100000;..

개요 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 실버1 탐색 문제다. 풀이 수빈이가 동생을 찾는 가장 빠른 시간을 찾는 문제이기 때문에 BFS를 사용했다. 코드 #include #include using namespace std; constexpr int LIMIT = 100000; struct Info { int x; int cnt; }; int N, K; bool visited[LIMIT + 2]; int a..

개요 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 골드급 DFS + DP 문제다. 풀이 처음에는 재귀를 활용한 DFS로 접근했다. 모든 구간에서 DFS로 탐색했고, 최대값을 구했다. visited 배열에 판다가 이동한 값의 최대 값을 기록하며 가지치기 해줬다. (다음 칸이 현재 칸보다 높은 값일 경우 continue) 하지만 결과는 시간 초과 행렬 기반 DFS는 O(V^2)다. 500*500을 25,000이라고 착각해서,,,, 2..

개요 https://www.acmicpc.net/problem/11123 11123번: 양 한마리... 양 두마리... 얼마전에 나는 불면증에 시달렸지... 천장이 뚫어져라 뜬 눈으로 밤을 지새우곤 했었지. 그러던 어느 날 내 친구 광민이에게 나의 불면증에 대해 말했더니 이렇게 말하더군. "양이라도 세봐!" www.acmicpc.net 실버급 BFS/DFS 문제다. 풀이 DFS를 사용해서 풀었다. 입력이 문자열인 점, 모든 위치에서 탐색을 수행해야 된다는 점을 제외하면 기본적인 DFS/BFS 문제와 동일하다. 한 노드에서 시작된 탐색이 끝날 때마다 memset 함수로 visited 배열을 초기화해 줬다. memset 사용 시 cstring 헤더를 include 하지 않으면 컴파일 에러가 나니 주의해야 한..

개요 https://www.acmicpc.net/problem/11931 11931번: 수 정렬하기 4 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 실버급 정렬 문제다. 풀이 STL의 sort로 간단하게 해결할 수 있다. algorithm 헤더를 include 해서 사용할 수 있다. std::sort는 intro sort라는 방식을 사용하는데, quick sort의 개선 방식이라고 한다. 기본적으로 퀵 정렬의 빠른 성능을 내지만 최악의 경우에도 O(nlogn)을 보장한다. // 오름차순(기본) sort(begin, end..

개요 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 실버급 백트래킹 문제다. 풀이 배열을 재귀로 탐색하다 조건이 맞으면(수열의 길이가 M이 됐을 때) 리턴시켜줬다. 방문이 끝나면 다른 경우의 수에서도 인덱스를 방문 할 수 있도록 방문 배열을 다시 false 시켜주어야 한다. 코드 #include #include using namespace std; constexpr int LIMIT = 10; int N, M; int num[LIMIT]; ..

개요 https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 골드급 BFS 문제다. 풀이 [BOJ] 2206 벽 부수고 이동하기 C++ [BOJ] 14442 벽 부수고 이동하기 2 C++ 위 문제에서 이어지는 문제다. 낮과 밤, 정지라는 개념이 추가되었다. visited 배열의 차원을 하나 늘려서 어느 시간에 왔는지를 체크할 수 있도록 해주었다. 벽에 있을 때 밤인 경우 부시는 기회를 감소시키고, 낮에 벽에 왔을 경..