세상을 바꾸는 데이터

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

문제 링크: https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 풀이 과정: 이 문제는 ★전형적인 시물레이션 문제★이다. 별도의 알고리즘이 필요하기보다는 문제에서 요구하는 내용을 오류 없이 성실하게 구현만 할 수 있다면 풀 수 있다. 1. 방향을 설정해서 이동하는 문제 유형에서는 dx, dy라는 별도의 리스트를 만들어 방향을 정하는 것이 효과적이다. 2. 리스트 컴프리헨션 문법을 이용해 2차원 리스트를 초기화하면 효율적이다. 풀이 코드: # 14..

문제 링크: https://www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 과정: 이 문제는 BFS(너비 우선 탐색)이 아니라 일일이 조건을 설정하여 답을 도출해야 하는 문제이다. 문제만 보면 방문할 수 있는 칸의 개수가 최댓값을 답을 (m-2)로 착각할 수 있다. 그러나 모든 답이 그렇지만은 않다. 세로와 가로의 길이를 설정하여 다음 풀이코드와 같이 풀어야 올바른 답을 도출할 수 있다. 풀이 코드: # 1783번 병든 나이트 n, m = map(int, input().split()) # 세로가 1일 경우 시작지점만 ..