C++ 코딩 문제 풀이151 [Baekjoon] 16236번: 아기 상어 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 해결 과정 착안 문제에서 아기 상어가 물고기를 먹기 위해 이동하는 최소 경로가 크기에 따라 달라지는 상황에서, 아기 상어가 먹이를 찾아 탐색하는 과정을 구현하는 문제이다. 문제를 처음 접했을 때, 아기 상어의 1 초당 이동 반경을 중심으로 전방향으로 탐색을 하는 방법을 생각해보았다. 즉, 너비 우선 탐색(breadth-first search, BFS)의 원리에 기반하여 주어진 공간 내.. 2023. 5. 30. [Baekjoon] 2908번: 상수 https://www.acmicpc.net/problem/2908 2908번: 상수 상근이의 동생 상수는 수학을 정말 못한다. 상수는 숫자를 읽는데 문제가 있다. 이렇게 수학을 못하는 상수를 위해서 상근이는 수의 크기를 비교하는 문제를 내주었다. 상근이는 세 자리 수 두 www.acmicpc.net 문제 해결 과정 착안 숫자를 뒤집어 읽었을 때의 대소 비교는 주어진 숫자들을 일의 자리의 수부터 차례로 십의 자리 수, 백의 자리 수를 비교하는 과정을 통해 빠르게 확인할 수 있으므로 이를 활용하여 문제를 해결하고자 하였다. * 문제에서 주어지는 숫자가 반드시 세 자리 숫자이며, 서로 다른 숫자라는 조건이 있기 때문. 구현 [스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~ 더보기 #includ.. 2023. 5. 29. [Baekjoon] 2675번: 문자열 반복 https://www.acmicpc.net/problem/2675 2675번: 문자열 반복 문자열 S를 입력받은 후에, 각 문자를 R번 반복해 새 문자열 P를 만든 후 출력하는 프로그램을 작성하시오. 즉, 첫 번째 문자를 R번 반복하고, 두 번째 문자를 R번 반복하는 식으로 P를 만들면 된다 www.acmicpc.net 문제 해결 과정 착안 문제에서 요구하는 것과 같이 주어지는 반복 횟수와 문자열에 대해, 문자열 내의 문자 별로 반복 횟수 만큼 단순하게 반복하여 출력하는 코드를 작성하고자 하였다. 구현 [스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~ 더보기 #include #include using namespace std; int main() { ios::sync_with_stdio(.. 2023. 5. 28. [Baekjoon] 10809번: 알파벳 찾기 https://www.acmicpc.net/problem/10809 10809번: 알파벳 찾기 각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다. 만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출 www.acmicpc.net 문제 해결 과정 착안 요소의 수가 26 개인 배열을 만들어, 알파벳 순으로 각 인덱스를 지정($a : 0, b : 1, \cdots, z : 25$)해 처음 나온 위치를 저장하고자 하였다. 알파벳이 중복으로 나오는 경우는 이미 처음 나온 위치가 $-1$ 이 아닌 값으로 저장되어있으므로 계산하지 않고 건너 뛰도록 구현하고자 했다. 구현 [스포 주의] 아래 '더보기'를 누르면 코드가 나오.. 2023. 5. 28. [Baekjoon] 1976번: 여행 가자 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 문제 해결 과정 착안 도시들이 각각 서로 다른 번호로 구분되고(정수형 데이터), 도시들 사이의 연결 여부가 문제에서 주어지고 있으며 여행 경로에 해당하는 도시를 방문하기 위해 다른 도시를 중복으로 방문이 가능하다. 여행 경로가 주어졌을 때 시작 도시에서 경로 내에 있는 도시들을 방문이 가능한지의 여부만 확인하면 되는 문제이므로, 트리 또는 그래프의 구조를 활용해 탐색을 빠르게 수행하는 것을 목표로.. 2023. 5. 26. [Baekjoon] 1904번: 01타일 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 문제 해결 과정 착안 처음에는 문제를 해결할 마땅한 방법이 잘 안떠올라서 모든 가능한 문자열을 실제로 전부 구해보고(브루트 포스, 무차별 대입) 길이가 $N$이 될 때 Count를 하나씩 늘리는 방식으로 프로그래밍 했는데, 문자열이 길어짐에 따라 분기가 크게 늘어나므로 너무 많은 수의 재귀 호출이 일어나 메모리 초과로 실패했다. 이런 상황을 어떻게 해결할지 한참 고민하다가 아래와 같이 단계를 나누고, .. 2023. 5. 25. 이전 1 ··· 16 17 18 19 20 21 22 ··· 26 다음
