웹개발 성장기

9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 풀이 BFS로 네 가지 경우 (DSLR)를 전부 탐색한다. int, String을 저장하는 custom class DSLR을 구현했다. 큐에는 (현재 숫자, 지금까지 부른 명령어)를 저장한다. 탐색하다가 현재 숫자가 B가 되면 지금까지의 명령어를 출력한다. visited[]로 숫자 중복 여부를 확인한다. D, S, L, R을 method로 만들어서 사용했다. 코드 import java.io.*; import java.util.*; public cla..

19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 풀이 시간초과가 났던 문제. 검색하여 찾아보니 연료를 무한으로 충전할 수 있어서 그렇다고 한다. 문제에는 적혀있지 않은 예외사항이 두 가지 있다. 택시 기사가 승객의 위치까지 도달할 수 없는 경우 (거리 = INF) 승객을 도착지까지 태울 수 없는 경우 (거리 = INF) 되는지 안되는지 판단할 때 단순히 거리와 연료량 여부로 판단하면 안되고 이 부분도 고려해야 문제가 통과한다. 구현문제라 문제에 충실하면 생각보다 어렵지 않..

1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 풀이 다양한 방법이 있는 것 같지만 다익스트라로 풀었다. 우선 여행 계획에 있는 도시들은 중복될 수 있으므로 순서를 배열로 입력받음과 동시에 HashSet으로 받았다. HashSet에 있는 도시들만 다익스트라 알고리즘으로 경로를 갱신했다. 만약 위치가 INF로 남아있으면 그 도시로는 방문이 불가능하다는 의미이다. 마지막으로 여행 계획에 있는 도시들을 for문으로 순회하면서 INF가 나오면 바로 "NO"를, 그렇지 않으면 "YES"를 출력하게 했다. 코드 impo..

1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 풀이 일단 이 문제는 다익스트라가 맞다. 틀려서 결국 구글링을 하긴 했는데 대부분 이분탐색과 BFS를 조합하여 했지만 이분탐색으로 풀면 뭔가 문제의 취지에 안맞는 느낌(?)이 들어서 다익스트라 코드도 찾아봤다. 다익스트라로 풀 경우 우선순위큐를 사용하여 중량 기준 내림차순으로 들어가도록 한다. 일반적인 최단경로 찾기의 경우 시작노드 기준 거리 정보를 업데이트를 하는 dist[]을 두는데, 여기선 해당 위..

1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이 우선순위큐를 이용한 다익스트라를 3번 실행한 후 경로가 존재하면 최단경로 출력, 없으면 -1을 출력하면 된다. 출발점, 도착점, 거치는 두 정점을 각각 A, B, X, Y라고 하면 A -> X, Y X -> Y, B Y -> X, B 이렇게 각 정점에서의 최단경로를 구한다. 최단경로는 dist[3][N + 1] 이렇게 이차원 배열을 만들어서 저장했다. A -> X -> Y -> B, A -> Y -> X -> B..

1219번: 오민식의 고민 첫째 줄에 도착 도시에 도착할 때, 가지고 있는 돈의 액수의 최댓값을 출력한다. 만약 오민식이 도착 도시에 도착하는 것이 불가능할 때는 "gg"를 출력한다. 그리고, 오민식이 도착 도시에 도착 www.acmicpc.net 풀이 이해가 안됐는데 이 블로그를 참고하여 겨우 이해할 수 있었다... 벨만-포드를 이렇게도 풀 수 있구나 했던 문제 특이하게 negative cycle이 아닌 positive cycle을 찾는 문제이다. 일반적인 벨만-포드는 N-1까지 최단 경로를 갱신한 후 마지막으로 한번 더 돌아다니면서 사이클 여부를 판정한다. 하지만 이 문제에선 사이클이 있는지 검사 뿐만 아니라 시작 지점부터 도착 지점까지의 경로가 있는지도 알아야 한다. 따라서 충분한 edge rela..

9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 풀이 처음에 사이클 체크를 어떻게 해야 하는지 엄청 고민했다... 결국 구글링하여 솔루션들을 참고했다 ㅠ 내가 시도하려는 풀이에선 방문체크 배열이 두 개가 필요함을 알 수 있었다. 방문 체크를 할 배열, 완전히 방문이 끝났음을 알리는 배열 두 개의 visited를 확인할 배열이 필요 visited[n] = false: 아직 방문안한 곳이므로 DFS 다음 탐색 node는 n visited[n] = true & finished[n] = false 방문은 했으나 완전히 방..

1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 풀이 벨만-포드 알고리즘을 몰라서 구글링하며 풀이ㅠ 알고리즘 이해에 참고한 글 👍🏻👍🏻👍🏻 코드 작성에 참고한 글 벨만포드 알고리즘이란? 최단 경로를 찾는 알고리즘 중 하나 가중치가 음수일 경우 다익스트라 알고리즘을 사용하면 무한 루프에 빠지게 된다. 따라서 음수 가중치를 다룰 수 있는 벨만-포드 알고리즘을 사용해야 한다. 간단한 원리는 다음과 같다. 노드 수를 V라 하면 시작점에 대해 최대 연결된 간선 개수는 V-1개이다. 시작점을 기준으로 V-1..