본문 바로가기

Algorithm43

[백준] 1753 최단경로(자바/다익스트라) 문제 접근 이 문제는 방향 그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하는 문제입니다. 이때, 생각해볼 수 있는 알고리즘은 BFS, 다익스트라, 플로이드 워셜 등이 있습니다. 문제에는 다음과 같이 가중치가 10 이하라는 조건이 주어집니다. 이때, BFS 알고리즘의 경우 가중치 개념이 없는 문제에서 사용할 수 있으므로 적합하지 않다고 판단하였습니다. 따라서, 다익스트라 알고리즘이 가장 적합하다고 판단하였습니다. 문제 풀이 저는 최단거리를 저장하는 배열 + 우선순위 큐를 사용하여 다익스트라 알고리즘을 구현하였습니다. 이때, 우선순위 큐를 사용하는 이유는 시작 정점에서 가장 가중치가 작은 정점으로 방문하기 위해서입니다. package boj.p1753; impo.. 2022. 12. 16.
[SWEA] 2112. [모의 SW 역량테스트] 보호 필름(자바/DFS) 문제 접근 방법 문제 조건은 다음과 같습니다. 따라서, 저는 한 줄씩 A, B 두 가지 경우로 바꾸어보며 성능 검사를 통과하는 경우에는 재귀를 탈출시켰습니다. 이를 구현하기 위해 DFS를 사용하였습니다. 문제 풀이 1. DFS 기저 조건 : 모든 세로 줄에대한 성능 검사를 실시하여 전부 통과하는 경우 재귀를 탈출시킵니다. 2. A, B 투입하는 경우에 대한 경우의 수를 확인 후 값을 원상 복귀시켜야 합니다. 이를 위해 처음에 copyMaps라는 배열을 하나 만들어 maps[i] = Arrays.copyOf(copyMaps[i], W); 를 통해 값을 원복시켰습니다. 3. 성능 검사 확인 method : 저는 성능 검사를 위해 메서드를 하나 만들었습니다. maps[r][c] 와 maps[r+1][c] 같이.. 2022. 11. 27.
[SWEA] 1949. [모의 SW 역량테스트] 등산로 조성(자바/DFS) 문제 조건 문제 접근 1. 가장 높은 봉우리에서 시작해야 한다 따라서, 가장 높은 봉우리들을 찾아 이에 대한 DFS 탐색을 모두 진행해야 한다. 2. 높은 지형에서 낮은 지형으로 연결되어야 한다. 따라서, 탐색할 지형(maps[nextX][nextY])이 현재 지형(maps[nowX][nowY])보다 크거나 같은 경우 지형을 깎아줘야 한다. 하지만, 3번 조건에 따라 이전에 지형을 깍은 경우에는 지형을 깎을 수 없다 3. 긴 등산로를 만들기 위해 딱 한 곳만 정할 수 있다. 따라서, boolean 변수를 선언하여 지형을 깍는 경우 true로 세팅하여 한 곳만 깎을 수 있게 조건을 준다. 4. DFS로 문제를 접근한 이유 만들 수 있는 가장 긴 등산로 길이를 구해야한다. DFS로 탐색하면 갈 수 있는 곳까.. 2022. 11. 14.
[SWEA] 1486. 장훈이의 높은 선반(부분집합/자바) 문제 요약 탑의 높이가 B 이상인 경우 선반 위의 물건을 사용할 수 있는데 탑의 높이가 높을수록 더 위험하므로 높이가 B 이상인 탑 중에서 높이가 가장 낮은 탑을 알아내려고 한다. 문제 접근 방법 점원들의 키에 대해 일부를 선택하여 선택한 점원들의 키의 합이 B보다 큰 경우 결과 값에 대해 갱신한다. 점원들 중에서 일부를 선택하는 것은 부분 집합으로 구현해볼 수 있다. 현재 점원을 선택한 경우와 선택하지 않는 경우에 대해 재귀 함수를 호출한다. 특히, 현재 점원의 선택 여부를 확인하기 위해서 boolean 배열을 사용하였다. 현재 점원을 선택하면 true, 그렇지 않은 경우는 false로 세팅한다. 재귀 함수의 탈출 조건은 선택한 점원의 수가 N명이 되는 경우이다. 이 경우에 점원들의 키의 합을 구하고,.. 2022. 11. 5.

티스토리툴바