Algorithm

백준 17143 낚시왕 (구현, 시뮬레이션)

17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 삼성 SW 역량 테스트 기출 문제랑 매우 유사한 문제이다. 상어가 움직이면서 다른상어를 잡아먹고 방향대로 이동하고 그대로 구현하면 되는 시뮬레이션 문제이다. 여기서 포인트는 1. 상어가 움직일 때 for 속력해서 하나하나 잡아주게 되면 시간초과가 난다. 2. 상어들이 움직인 다음에 다른 상어를 잡아먹을 ..

SWEA 1953 탈주범 검거(BFS, 구현)

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 구현단계에서 생각보다 애를 먹었던 문제다. 문제접근은 시작점에서 bfs를 돌리면서 인접한 노드의 파이프모양에 따라 나아갈 수 있는 방향이 정해지고 그것을 카운트하는 방식인데 어떤 모양인지 체크하고 어떤 방향으로 갈지 체크하는 로직을 짜는데 시간이 많이 걸렸다. 먼저 상하좌우에 따라 각각 갈 수 있는 파이프의 번호를 저장해둔다(dir 배열) dx, dy 방향벡터는 상하좌우로 이동할 수 있지만 지금 내가 위치한 파이프의 모양에 따라 상하좌우 중 특정 방향으로만 갈 수 있기 때문에 상하좌우의 벡터를 파이프의 개수 7개 만큼 dx[7][4], dy[7][4]로 만들어 이..

SWEA 1952 수영장(DFS, DP)

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 수영장을 어떠한 기준으로 끊어야할지 모르기 때문에 모든 경우를 봐줘야한다. DFS의 구조를 트리로 그리면 이해가 쉬워진다. 기간은 1년이기 때문에 1년에 해당하는 부분은 상수(final)일 것이고 1일, 1개월, 3개월 단위로 어떤 순서로 할지 모든 경우를 탐색한 다음 비용을 갱신해주면서 답을 찾는다 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Solution{ static int[] price, data; static ..

백준 19238 스타트 택시(BFS, 구현)

19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 택시가 서있는 위치에서 여러손님들 가운데 최단거리에 있는 손님 먼저 채우고 손님 목적지 까지 태우는 단순한 구현 문제이다. 이 문제가 까다로웠던 이유는 한 손님의 운송이 끝나면 그 손님에 대한 방문처리를 해줘야하는 것과 어떤 손님을 먼저 태울지에 대한 우선순위 조건이 2개나 있어서 조건문을 구현하기 힘들어서 어려웠다. 최단경로를 구할려 할 때 플로이드-와샬을 쓰려고 했지만 가중치가 나오지 않았기 때문에 그냥 BFS를 써서 그..

Coding Test(Topological Sort)

위상 정렬(Topological Sort) 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열 선행 조건들을 만족하는 일의 수행 순서 특정 노드를 방문하려면, 조건으로 갖는 다른 노드들이 방문된 상태여야함 DAG(Directed Acyclic Graph, 방향성이 있으며 사이클이 없는 그래프) 여야 한다 위상정렬에서 중요하게 쓰이는 개념인 진입차수와 진출차수 1. 진입차수가 0인 모든 노드를 큐에 넣는다(진입차수가 0이라는건 시작점이라는 뜻) 2. 큐가 빌 때 까지 다음의 과정을 반복한다 2-1) 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거 2-2) 새롭게 진입차수가 0이 된ㄷ 노드를 큐에 넣는다 => 결과적으로 각 노드가 Queue에 들어온 순서가 위상 ..

백준 2623 음악프로그램(위상정렬, DFS, BFS)

2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 재미있는 문제였다. 각 PD들이 가수들의 무대순서를 정하고 각각 PD에 요청에 모두 부합하는 완벽한 순서를 만들어내는 것이 문제다. 먼저 문제를 읽고 생각을 해봤을 때 순서라는 점이 가장 Key-Point라는 생각이 들었다. 따라서 순서라는 점을 계속 기억하고 인지하기 위해 Queue, Stack이라는 자료구조를 통해서 기억했으면 좋겠다라는 생각을 했고 더 나아가서 이 자료구조를 통해서 Next step까지 생각하는거니까 DFS, BFS문제구..