https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 💡IDEA BFS를 사용하는 문제이다. 자주 접했던 문제라 정말 금방 풀었다. 조금 다른 점은 방향이 8방향 인 점 정도이다. 모든 행열을 돌면서 섬이 있는 곳을 발견하면 거기서부터 갈 수 있는 모든 곳을 탐색하고 방문 기록을 한 후 돌아온다. BFS를 한 번 수행하는 게 한 번 카운트 하는 것이다. 방문 기록은 따로 배열을 만들기보다 기존에 받아온 이차원 배열에서 섬(1)인 곳을 바다(0)..
https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 💡IDEA DFS와 백트래킹을 사용하는 문제이다. 문제 자체는 쉽게 접근이 가능하지만 시간초과가 자꾸 발생해서 꽤 고생을 했다. 처음에는 방문 배열에 알파벳 자체를 넣었다 뺐다 하는 식으로 했지만 바로 시간초과가 발생했다. 알파벳을 쉽게 인식할 수 있는 방법을 생각해보다가 알파벳을 숫자로 바꾸어주는 ord 함수를 사용해서 알파벳 개수인 26개만큼의 길이의 배열을 만들어서 사용하기로 했다. ..
https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 💡IDEA 동적 계획법을 사용하는 문제이다. 규칙을 찾기 위해서는 직접 계산해보면서 찾는 것이 빠르다. K \ N 1 2 3 4 5 1 1 1 1 1 1 2 2 3 4 5 6 3 3 6 10 15 21 4 4 10 20 35 56 5 5 15 35 70 126 위의 표 처럼 K와 N 값에 따른 0부터 N까지 정수 K개를 중복 허용하여 더해서 N이 되는 경우의 수를 계산할 수 있다. K=1인 경우, 정수를 한 개만 사용해서 N을 만드는 경우는 N 한 경우 뿐이므로 모두 1이다. N=1인 경우, 정수 K개로 1을 만드는 경우는..
https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 💡IDEA 동적 계획법을 사용하는 문제이다. 2022.07.21 - [Algorithm/BOJ] - [BOJ][python] 2293. 동전 1 문제를 풀었던 것이 도움이 되었다. 가치의 합이 최대 10000이므로 10001 길이의 dp 배열을 사용해야 한다. 가치의 합이 0인 경우는 없으므로 0으로 초기화하고, k번째까지 dp를 구한다. 현재 동전을 포함하는 경우와..
https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 💡IDEA BFS를 사용하는 문제이다. 이 문제는 맥주를 50미터마다 하나씩, 20개씩 한 상자를 꾸준하게 마시고 편의점에서 채운다는 맥락에서 결국 1000미터 안에만 편의점이 있으면 된다는 것이 중요하다. 일반적인 BFS와 거의 유사하지만, 좌표 범위가 -32768 ≤ x, y ≤ 32767이므로 자주 사용하던 이차원 배열의 방문 확인용 배열을 만들기보다 그냥 방문한 좌표 자체를 저장하는 ..
https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 💡IDEA 스택을 사용하는 문제이다. 스택을 통해서 괄호를 확인하는 것은 잘 구현했는데, 점수를 매기는 부분에서 어려움을 겪었다. 처음에는 스택 하나로 '()'와 '[]'를 모두 해결하려 했지만 두 가지 경우 따로 스택을 만들어 주는 쪽이 계산하기 편했다. 여는 괄호가 나오면 tmp에 점수를 곱하고, 닫는 괄호가 나오면 바로 직전 값이 같은 유형의 여는 괄호인 경우에만 결과값에 더해주고 tmp를..
https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 💡IDEA 이분 탐색을 사용하는 문제이다. 2022.07.31 - [Algorithm/BOJ] - [BOJ][python] 2110. 공유기 설치 문제를 풀었던 것이 도움이 되었다. 랜선 길이를 찾기 위해서 왼쪽 값(l)은 1, 오른쪽 값(r)은 랜선 길이의 최댓값으로 초기화해주었다. N개 이상의 랜선을 가져야 하는데, 랜선의 개수는 모든 랜선을 이분탐색하며 중간 값(..
https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 💡IDEA 이분 탐색을 사용하는 문제이다. 문제의 분류를 보지 않으면 이분 탐색 문제라는 것을 알기 어려운 것 같다. 그리고 이 문제는 간격의 최대값을 찾는 문제이므로, 왼쪽 값과 오른쪽 값을 초기화 할 때 조심해야 한다. 왼쪽 값(l)은 최소 간격인 1, 오른쪽 값(r)은 최대 간격인 가장 작은 좌표값과 가장 큰 좌표값의 차이이다. 이분 탐색을..
https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 💡IDEA 동적계획법을 사용하는 문제이다. 현재 위치에 적혀있는 값만큼 오른쪽 또는 아래쪽으로 점프해서 이동하여 도착지점(0)에 다다르는 경로의 개수를 구해야 한다. 처음에는 BFS 문제인 줄 알았으나 DP로 풀 수 있는 문제였다. 시작점을 1로 두고 모든 행렬을 돌면서 점프한 후의 위치에 이전 DP값을 끌고가면 된다. 거치지 않는 부분은 0이므로 아무것도 더해지지 않고 계속 0이고, ..
https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 💡IDEA 구현하는 문제이다. 처음 문제를 보았을 때 BFS를 사용해야할 줄 알았으나, 간단하게 구현만 해주면 되는 문제였다. 구현하는 조건이 쉽지는 않아 조금 헤매긴 했다. 방향을 왼쪽으로 틀어준다는 점이 까다로워서 따로 함수를 만들어 현재 방향에 따른 왼쪽 방향 배열을 구했다. visited 배열을 사용하지 않고 하려면, 벽인 부분(1)과 방문한 부분(-1)을 구분해야한다. 현재 방향에 맞는..
