나쿠리 개발 메모장

개요 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를 사용하면 된다. 바다를 제외한 모든 위치에서 다른 섬으로 가는 최단 거리를 전부 구하고, 이 중 다시 최단 거리를 추려냈다. 그냥 바다고 섬이고 돌려도 될..

개요 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 실버급 DFS, BFS 문제다. 풀이 재귀를 활용한 DFS로 풀었다. 반복문으로 배열(N*N)을 하나씩 체크하고, 1을 발견하면 DFS로 크기를 체크하고 단지수를 증가시키도록 했다. 단지 수는 재귀가 처음 호출 될 때에만 증가할 수 있도록 isFirst(bool) 변수를 사용했다. 마지막 출력 값(각 단지 크기)을 오름차순 정렬하여 출력해야 함에 주의해야 한다. 정렬 안 해서 몇 번 틀렸다(!..

개요 https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 실버급 수학 및 해시 문제다. 풀이 경우의 수를 구할 식만 떠올리면 된다. 분류별 옷의 수 + 1(벗은 상태)를 전부 곱해주면 된다. 주의할 점은 알몸인 상태는 제외라고 나와있으니 이 결과에 -1을 해주어야 한다. map을 사용해 구현했다. 코드 #include #include #include #in..

개요 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 실버급 BFS 문제다. 풀이 가장 빠른 길을 출력해야한다. BFS를 활용한다면 가장 먼저 도착하는 길을 구분할 수 있기 때문에 BFS를 떠올렸다. 구조체로 현재 좌표와 거리를 정의하고, 현재 위치의 상하좌우로 넓혀가며 탐색했다. 입력은 숫자를 붙여서 받기 때문에 scanf("%1d", &array[i][j])와 같은 방식으로 받았다. IDE에서 답은 계속 맞게 나오는데 제출하면 자꾸 틀리는 문제가 있었다. ios_base:..

개요 https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 실버급 DFS 및 BFS 기본 문제다. 본문 풀이 연습해 볼 겸 인접행렬로 구현해 봤다. 스택을 활용한 DFS로 풀려고 한참 고민했는데, 카운트하는 부분에서 계속 막혔다. 그래서 재귀로 DFS를 구현했더니 바로 풀렸다,,내 시간 스택으로도 풀 수 있을 것 같은데 조금 더 복잡해질 듯하다. 주의할 점으로는 연결되지 않는 상황(-1 출력)을 고려해야 한다. 코드 #includ..