세상을 바꾸는 데이터

문제 링크: 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/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 백준 14502번 연구소 문제는 삼성 SW 역량테스트 기출문제이다. 풀이 유형: 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 구현 풀이 과정: 이 문제는 벽을 3개 설치하는 모든 경우의 수를 다 계산해야 한다. 전체 맵의 크기가 최대 8 x 8이므로, 벽을 설치할 수 있는 최악의 경우 64C3이다. 이는 100,000보다 작은 수이므로, 모든 경우의 수를 고려해도 제한 시간..

문제 링크: https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 풀이 유형: 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색 풀이 과정: 이 문제의 핵심 포인트는 모든 도로의 거리가 1이라는 점이다. 모든 간선의 비용이 동일할 때는 너비 우선 탐색(BFS)을 이용하여 최단 거리를 찾을 수 있다. 먼저 특정한 도시 X를 시작점으로 BFS를 수행하여 모든 도시까..

문제 링크: https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 백준 3190번 뱀 문제는 삼성 SW 역량테스트 기출문제이다. 풀이 유형: 구현, 자료구조, 시물레이션, 덱, 큐 풀이 과정: 이 문제도 앞서 풀은 테트로미노와 마찬가지로 복잡한 구현을 하는 문제이다. 특히 사과를 먹으면 알아서 맵에서 지워줘야 하는 센스가 필요, 뱀의 형태를 담을 자료구조도 알아야 하는 문제이다. 문제를 꼼꼼이 읽어야 주어진 조건을 놓치지 않는다. 1. 2차원 배열상의 맵에..

문제 링크: https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 백준 14500번 테트로미노 문제는 삼성 SW 역량테스트 기출문제이다. 풀이 유형: 구현, 브루트 포스(완전 탐색) 알고리즘, DFS 풀이 과정 1 1. 테트로미노 모양은 5가지가 있다. 이 모양에 해당하는 함수들을 모두 만들어 계산한다. 2. 모양에 따라 회전하는 함수와 대칭하는 함수 2개를 모두 만들어야 하기 때문에 코드가 매우 길어진다. 3. 필자는 DFS방식을 이용하지 않고 브..

문제 링크: https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 과정: 이 문제는 기존에 존재하는 치킨집을 줄여서 최대 M개로 유지하면서, 일반 집들로부터 M개의 치킨집까지의 거리를 줄이는 것이 목표이다. 이후 도시의 치킨 거리의 최솟값을 계산하면 된다. 1. N개의 치킨집 중 M개를 골라야 한다면 조합을 이용한다. 파이썬에서 조합(combinations) 라이브러리를 제공하므로, 이를 이용하면 모든 경우를 간단히 계산할..

문제 링크: https://www.acmicpc.net/problem/2847 2847번: 게임을 만든 동준이 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어 www.acmicpc.net 풀이 과정: 이 문제는 사고의 전환이 필요한 그리디 문제이다. 맨 처음 레벨부터 점수를 감소시키는 것이 아닌, 맨 마지막 레벨부터 점수를 감소시켜야 한다. 그 이유는 쉬운 레벨을 클리어할 때 점수 < 어려운 레벨을 클리어할 때 점수를 부여하기 때문이다. 일반적으로 우리가 사용하는 for 구문에 사용되는 range(start, end, step) 함수에서 start보다 end가 큰 값..

문제 링크: 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는 스택의 자료 구조와 같다고 말할 수 있는 재귀 함수(자기 자신..