나쿠리 개발 메모장

개요 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..

개요 알고리즘 문제를 풀며 자꾸 오답이 나온다. memset 함수를 잘못된 방법으로 사용하고 있었다. 본문 배열의 값을 전부 1000으로 초기화시키고 싶어서 1000을 입력했었다. 이게 문제였다. memset 함수는 1바이트 단위로 초기화하기 때문에 int형(4byte)은 제대로 표현할 수가 없다.(1바이트인 char형은 가능) 만약 int형인 1을 인자로 전달하게 되면 될 것 같지만 실제로는 위처럼 작동한다고 하니 주의해야 한다. 그래서 위처럼 범위 기반 for문으로 초기화해 주었다.

개요 두 포인터(Two Pointers) 혹은 슬라이딩 윈도우(Sliding Window)라고 부른다. 1차원 배열에서 2개의 포인터를 조작하며 값을 얻는 기법이다. 본문 예를 들어 1차원 배열에서 구간 합의 경우의 수를 찾는 문제가 있다고 하자. 위와 같이 브루트포스로 경우의 수를 찾게 된다면 O(N^2)가 될 것이다. N의 범위가 10만을 넘기기만 해도 시간 초과가 나버리게 된다. 이럴 때 필요한게 두 포인터다. 두 포인터(Two Pointers) front와 back 처럼 두 개의 포인트를 잡고 시작한다. 현재 합이 20보다 작으므로 b를 뒤로 움직여 부분합을 증가시킨다. 합이 20보다 커질 때 까지 b 포인터를 뒤로 움직인다. 20이 된 경우의 수가 있다면 count를 증가시킨다. 위처럼 합이 2..

개요 https://nakuri.tistory.com/41 [BOJ] 1937 욕심쟁이 판다 C++ 개요 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, nakuri.tistory.com 위 문제를 풀다가 잘못된 코드로 인해 배열의 음수 인덱스에 접근을 했다. 제출했더니 에러가 나지 않고 정답이 나와버려서 궁금증에 한 번 알아봤다. 본문 C++에서는 잘못된 문법이 아니라고 한다. 배열과 포인터의 작동방식이 같기 때문에 이전 포인터를 참조하는 것이다. 하지만 초기화 되지 않은 공간을 참조했기 때문에 문제가 풀린 건 그냥 운..

개요 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 배열의 차원을 하나 늘려서 어느 시간에 왔는지를 체크할 수 있도록 해주었다. 벽에 있을 때 밤인 경우 부시는 기회를 감소시키고, 낮에 벽에 왔을 경..