세상을 바꾸는 데이터

문제 링크: https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 이 문제는 "이것이 코딩 테스트다" 책 유형별 기출문제 21번에 해당한다. 풀이 유형: 구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 시물레이션 ★문제풀이 Point★ 1. 모든 나라의 위치에서 상, 하, 좌, 우로 국경선을 열 수 있는지 확인(bfs) 2. 같은 연합끼리 인구를 동일하게 분배 풀이 과정: 이 문제는 각 나라의 인구수가 주어졌을 때, 인구 이동이 ..

문제 링크: https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 풀이 유형: 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색, 너비 우선 탐색 풀이 과정: 이 문제는 다이나믹 프로그래밍(DP)로 풀지 않고 딕셔너리를 이용한 bfs로 풀었다. bfs 대부분의 문제는 방문 표시를 가능한 전체 인덱스 수만큼 만들어서 해결하는데, 이 문제는 다르다. 이 문제는 현재 이모티콘의 개수와 클립보드에 있는 이모티콘 개수 2가지를 이용해 bfs로 풀어야 한다. 방문..

문제 링크: https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 유형: 그래프 이론, 그래프 탐색, 너비 우선 탐색 풀이 과정: 이 문제는 숨바꼭질 문제를 응용한 문제로서 난이도가 조금 높아졌다. 기본 숨바꼭질 문제는 다음 링크를 참조하자. https://data-flower.tistory.com/78 [백준 1697번] 숨바꼭질 - 파이썬 문제 링크: https://www.acmicpc.net/problem..

문제 링크: https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 유형: 그래프 이론, 그래프 탐색, 너비 우선 탐색 풀이 과정: 이 문제는 1차원상의 좌표에서 수빈이가 동생을 만나기 위한 최소 시간을 도출하는 것이다. 먼저 모든 좌표(100000개)를 0으로 초기화한 리스트를 만든다. 여기에 BFS를 실행하여 특정 위치를 방문하면, 방문한 시간을 표시해준다. deque을 이용해 큐를 사용하여 풀어보자. 풀이 코드: ..

문제 링크: https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 풀이 유형: 브루트포스 알고리즘, 백트래킹, 깊이 우선 탐색, 너비 우선 탐색 풀이 과정: 이 문제의 풀이 과정은 2가지가 있다. ★ 첫 번째 방법은 필자가 풀은 방법인 순열 라이브러리와 BFS를 이용한 방법이다. 먼저 연산자의 기호들을 차례대로 받아 순열을 이용해 가능한 모든 경우의 수를 계산하여 큐에 삽입한다. (예를 들어 '..

문제 링크: https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 풀이 유형: 구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색 풀이 과정: 이 문제는 너비 우선 탐색(BFS)을 이용하여 해결할 수 있다. 이 문제의 포인트는 바이러스가 낮은 번호부터 증식한다는 점이다. 이는 정렬을 이용하자. 낮은 번호부터 증식하므로, 초기에 큐에 원소를 삽입할 때는 낮은 바이러스의 번호부터 삽입한다. 이후에 BFS를 수행하여 방문하지..

문제 링크: https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 과정: 이 문제는 DFS(깊이 우선 탐색 알고리즘)과 BFS(너비 우선 탐색 알고리즘)의 가장 기초가 되는 문제이다. DFS에서는 인접 행렬(이웃해 있는 행렬의 값이 모두 일치)을 이용하여, BFS에서는 데크(deque)를 호출해 큐(queue)를 이용하여 문제를 풀었다. DFS는 스택의 자료 구조와 같다고 말할 수 있는 재귀 함수(자기 자신..