Let's Begin Programming

www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 미리 주어진 미로를 그래프라고 생각하고 주어진 위치 (N, M)까지 최소 거리로 이동하는 문제이다. 전형적인 BFS 문제로 (0, 0)부터 BFS를 시작해서 최종 목적지까지 이동하면 된다. 상, 하, 좌, 우로 이동하면서 다음 위치가 범위를 벗어나거나 이미 방문한 경우, 이동할 수 없는 위치인 경우에는 무시한다. 만약 이동할 수 있는 곳인데 아직 방문하지 않은 곳이라면 큐에 삽입하고 해당 정점의 값은 현재 내가 머물러 있는 위치의 정점 값에 ..

개발 공부 (알고리즘) 2021. 1. 31. 05:03

www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 이전에 풀었었던 '바이러스' 문제와 유사한 문제로 그래프에서 1로 이루어진 구역이 몇 개인지 구하는 문제이다. 먼저 1이 어디에 있을지 모르기 떄문에 모든 정점에서 출발해야 한다. 단, 이미 방문하거나 배추가 심어져 있지 않은, 0인 정점은 방문하지 않아도 된다. 정점에서 이동 가능한 방향은 상, 하, 좌, 우 4 방향이다. 방향을 미리 정해놓고 방문하지 않은 정점마다 반복문을 4번 돌면서 다음에 갈 정점을 정한다. 나는 ..

개발 공부 (알고리즘) 2021. 1. 31. 04:55

www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 이 문제는 연결되어 있는 정점끼리 분류하는 문제이다. 연결되어 있는 정점들의 그룹이 몇 개가 있고, 그 그룹들 안에는 각각 정점이 몇 개가 있는지를 출력하는 문제이다. 먼저 이 그래프를 탐색할 때 어느 방향으로 이동이 가능한지를 정해야 한다. 이번 문제에서는 인접해 있는 모든 정점을 살펴보아야 하므로 상, 하, 좌, 우 모두 이동이 가능하다. 또한 시작하는 정점을 정해야한다. 이번 문제에서는 어느 지점에 건물이 ..

개발 공부 (알고리즘) 2021. 1. 30. 23:31

www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 네트워크 상에 컴퓨터들이 연결되어 있을 때 바이러스가 걸리는 컴퓨터의 갯수를 출력하는 것으로 네트워크라는 단어를 들었을 때 바로 그래프가 생각난다. 문제가 BFS, DFS를 사용하는 것에 초점을 맞추었다는 생각이 든다. 정점과 간선 정보를 알고 있고 문제에서 무조건 1번 컴퓨터가 바이러스에 감염되었다고 조건을 달았기 때문에 입력 받은 그래프에서 1번 정점부터 DFS나 BFS로 순회하면서 탐색한 정점의 갯수를 세는 방..

개발 공부 (알고리즘) 2021. 1. 30. 23:20

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 함수를 구현하고 방문할 때마다 출력하는 방식으로 문제를 풀었다. 작은 수부터 출력하는 문제는 특정 정점을 방문했을 때 그 정점에 인접한 정점 리스트를 정렬한 상태에서 다음 방문을 처리하는 식으로 해결했다. [소스코드] from..

개발 공부 (알고리즘) 2021. 1. 30. 23:09

www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 문제를 읽으면 입력도 많고 굉장히 복잡해 보이는 문제이지만 차근차근 생각해보니 간단한 문제였다. 거리와 기름의 가격을 생각해서 최소한의 비용으로 이동하는 문제인데 그리디 알고리즘에 알맞은 문제라고 생각했다. 왜냐하면 미래에 대해 걱정하지 말고 지금 현 상황에 가장 적절한 해법을 찾으면 되기 때문이다. 최소 비용이 되는 방법은 1) 다음 도시의 기름 가격을 본다. 2) 지금 도시보다 다음 도시의 가..

개발 공부 (알고리즘) 2021. 1. 21. 04:18

[참고] www.acmicpc.net 그리디 알고리즘 단계 동전의 조건이 특별해서 동적 프로그래밍보다 빠르게 답을 찾을 수 있는 문제 www.acmicpc.net 학교다닐 때 뭔가 풀었던 것 같은 기억이 있는 문제였다. 당시에 스택을 공부하면서 풀었던 것 같다. 1. 숫자인 경우 2. +인 경우 3. -인 경우 세 가지 경우로 나누어 생각했다. 먼저 숫자인 경우는 그대로 스택에 저장한다. 숫자는 연산자가 나왔을 때 자릿수가 정해지므로 연산자가 나오기 전까지는 계속 저장한다. +인 경우는 지금까지 나온 숫자의 자릿수를 결정해주는 역할이다. +가 나오면 지금까지 저장해오던 숫자의 자릿수만큼 곱해서 숫자를 완성한다. 이 숫자는 sum이라는 변수에 저장한다. -인 경우는 현재 스택의 모든 것을 pop한다고 생각..

개발 공부 (알고리즘) 2021. 1. 21. 03:19

[참고] www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 회의실 배정과 비슷한 문제였지만 난이도는 더 낮았다. 운영체제라는 전공 수업을 들을 때가 생각났다. 작업 시간이 오래걸리는 프로세스가 앞에 스케줄링이 되면 뒤에 프로세스들은 계속 기다릴 수 밖에 없었다. 이러한 경우를 해결하기 위해 나왔던 CPU 스케줄링 기법 중 하나가 SJF(Shortest Job First) 였다. 작업 시간이 가장 짧은 작업을 앞에 배치하는 것이다. 이번 문제도 돈을 인출하는 시간이 가장 짧은 사람 순으로 정..

개발 공부 (알고리즘) 2021. 1. 21. 01:54