본문 바로가기

C++7

[백준 BOJ] 4963 : 섬의 개수 (C++) https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 아이디어 흐름 1. 아이디어 구상 1. 해당 위치에서 주변으로 뻗어나가는 탐색이 필요 => DFS, BFS 모두 가능할 것 같다. 2. 가로, 세로, 대각선 모두 연결을 확인해야 하므로 탐색은 dx = { 1, 1, 0, -1, -1, -1, 0, 1 } dy = { 0, 1, 1, 1, 0, -1, -1, -1 } dx[i], dy[i] 인덱스를 이동시키는 방식으로 상하좌우 대각선 탐색 (.. 2021. 8. 14.
[백준 BOJ] 1260 : DFS와 BFS(C++) https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net #include #include #include #include using namespace std; bool visited[1001]; vector graph[1001]; // 1. 방문처리 // 2. 현재 노드 출력 // 3. 현재 노드의 인접 노드 개수만큼 반복문 실행 // 4. 반복문에 의한 인접 노드가 방문되지 않았다면 dfs 재귀호출 void dfs.. 2021. 8. 10.
[백준 BOJ] 6588 : 골드바흐의 추측(C++) https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 아이디어 흐름 1. 아이디어 구상 소수에 대한 문제가 크게 특정 범위 안의 소수를 알아야하는 경우, 해당 수가 소수인지 판별하는 경우 이렇게 두 가지가 있다고 생각하는데, 해당 문제는 1,000,000 까지의 소수를 알아야했으므로 에라토스테네스의 체를 이용하기로 했다. 또한 그렇게 소수를 판별하고, 소수만을 따로 모은 prime_arr 를 만들어서 int tmp = num .. 2021. 8. 5.
[백준 BOJ] 2579 : 계단 오르기 (C++) https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 아이디어 흐름 1. 아이디어 구상 이전에 풀었던 dp문제들에 견주어 이 문제 또한 '내가 i번째에 있을 때 이것을 선택할때, 하지 않을 때' 라는 측면에서 먼저 생각해보았다. 세 가지를 연속으로 선택할 수 없다는 조건을 생각해보고 dp[i] = dp[i - 3] + max((arr[i - 2] + arr[i - 1]), (arr[i - 2] + arr[i]), (arr[i - 1] + arr[i])) 위와 같.. 2021. 7. 28.
[백준 BOJ] 1149 : RGB거리 (C++) https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 아이디어 흐름 1. 아이디어 구상 문제의 조건이 앞의 색과 다른 색으로만 칠하면 된다는 의미이기 때문에 arr[1001][3] 배열을 선언한 후 각 집의 R, G, B 값을 모두 저장 현재 i번째 인덱스를 진행중일 때, 점화식은 dp[i] = dp[i - 1] + min(arr[i][0], arr[i][1], arr[i][2]) 기저조건(초기값)이 가장 작은 값으로 시작한다고.. 2021. 7. 20.
[백준 BOJ] 2954 : 창영이의 일기장 (C++) https://www.acmicpc.net/problem/2954 2954번: 창영이의 일기장 창영이는 매일 밤 하루동안 일어난 일을 일기장에 남긴다. 일기장을 쓰면서 영어 공부도 같이 하기 위해서 영어로 일기를 쓴다. 또, 남들이 자신의 일기장을 보는 것을 막기 위해서 모음('a','e','i www.acmicpc.net 굉장히 간단한 문제인데 조금 더 생각을 하지 못하고 문제의 조건 곧이 곧대로 푸느라 효율적이지 못했던 것 같다.... 아이디어의 흐름 1. 아이디어 구상 모음이 온 다음에는 무조껀 'p + 모음' 이 삽입되는 것이므로, 입력받은 문자열을 처음부터 끝까지 순회하며 모음인 a e i o u를 만나게 되면 앞으로 올 두 원소를 삭제해주는 방향으로 생각하였다. 문자열 입력은 getlin()으.. 2021. 7. 13.

티스토리툴바