나쿠리 개발 메모장

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

개요 https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 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문제다. 풀이 https://nakuri.tistory.com/35 위의 벽 부수기 1 코드와 거의 일치한다. 다른 점이라면 벽을 부실 수 있는 기회가 한 번이 아니라 여러 번인데, 애초에 여러 번 할 수 있는 확장성을 고려하고 작성했었던 코드라 아주 살짝만 수정하면 됐다. 코드 #include #include #include using nam..

개요 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 골드급 BFS 문제다. 풀이 처음에는 구조체에 카운터 변수(cnt)와 부실 기회 변수(brk)를 추가해서 그냥 BFS 돌리면 될 줄 알았다. 테스트 케이스는 통과했지만 오답이 나왔다. 문제는 visited 배열에 있었다. 초반에 벽을 부순 경우의 수가 특정 위치에 방문을 먼저 해버리면 그렇지 않은 경우의 수 들은 전부 방문할 수 없게 된다. 하지만 나중에 벽을 부수어..

개요 https://www.acmicpc.net/problem/26162 26162번: 인공 원소 원자 번호 43번을 가진 테크네튬은 세계 최초의 인공 방사성 원소이자, 가장 가벼운 방사성 원소이다. 테크네튬의 최초 발견은 특이하게도 자연이 아닌 인공 합성을 통해 이루어졌는데, 원자 번 www.acmicpc.net 실버급 소수판정&브루트포스 문제다. 풀이 에라토스테네스의 체로 소수를 판별한 후, 브루트포스로 답을 구했다. 근데 풀고나니까 골드바흐의 추측이란걸 이용하면 훨씬 더 간단히 구할 수 있다는 사실을 알아 버렸다,, 골드바흐의 추측 2보다 큰 모든 짝수는 두 개의 소수(Prime number)의 합으로 표시할 수 있다는 것 코드 #include using namespace std; constexpr..

개요 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 골드급 BFS문제다. 풀이 [BOJ] 7576 토마토 C++ 위 토마토 문제랑 풀이가 98% 같다. 2차원으로 풀었던 것을 3차원으로 바꿔주기만 하면 된다. 코드 #include #include #include using namespace std; constexpr int LIMIT = 102; struct Box { int z; int y; int x; int cnt..

개요 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 골드급 BFS문제다. 풀이 토마토가 모두 익는 최소 일 수를 출력해야 하기 때문에 BFS를 사용해야 한다. 토마토를 입력받은 후 큐에 입력 받은 익은 토마토를 전부 넣어주었다. 이렇게 하면 익은 토마토들에서 동시에 점점 퍼져나가서 다른 토마토를 익게 할 것이다. 상하좌우로 탐색하기 때문에 OutOfBounds가 나지 않게 조심해야 한다. 또한 처음이 아닌데(firstSize ..

개요 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 골드급 BFS 문제다. 풀이 우선 각기 다른 섬부터 구해야 한다. [BOJ] 2667 단지번호붙이기 C++ 위 문제를 풀었던 방식으로 DFS를 이용하여 섬을 구별하기 위한 이름(1,2,3...)을 구해서 붙여줬다. 이제 섬 간의 거리는 BFS를 사용하면 된다. 바다를 제외한 모든 위치에서 다른 섬으로 가는 최단 거리를 전부 구하고, 이 중 다시 최단 거리를 추려냈다. 그냥 바다고 섬이고 돌려도 될..