메모장

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

개요 https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 브롱즈급 브루트포스 문제다. 본문 풀이 생각보다 오래 걸렸다,,!! 난쟁이 9명 중 7명을 추려내려고 하니 여간 복잡한 게 아니었는데,, 반대로 생각해 보니 2명만 빼면 되는 것이었다. 브루트포스로 정답을 골라낸 후 1000으로 바꿔주었다.(모든 입력 값은 100 이하) 주의할 점은 값을 오름차순으로 정렬 후 출력해야 한다는 점! 코드 #include #include using namespace st..

개요 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 실버 2급 DFS와 BFS 기초 문제다. 본문 풀이 인접 리스트 기반(vector)으로 구현했다. 각각 DFS는 stack, BFS는 queue를 사용했다. 정점의 번호가 작은 순으로 탐색하라는 조건이 있기 때문에 리스트(vector)를 정렬해주어야 한다. DFS는 스택으로 후입선출이기 때문에 내림차순으로, BFS는 큐로 선입선출이기 때문에 오름차순으로 ..

개요 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 실버 3급 그래프 탐색 문제다. 본문 풀이 그래프 탐색 문제 중 저 난이도 문제인듯하다. 제한이 크게 없어 BFS, DFS 중 어느 것을 사용해도 문제가 없을 것이라 판단했다. queue를 활용한 인접 리스트(vector) 기반 BFS로 풀었다. 1번 컴퓨터는 제외이기 때문에 이 점에 유의해야 한다. 코드 #include #include #include #include using namespace..