일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
- HTTP
- 스프링 부트
- IntelliJ
- 해결
- 명령어
- 코딩테스트
- 프로그래머스
- 해시맵
- 배열
- 인텔리제이
- 스프링
- 구현
- 주니어
- 스타트업
- 문자열
- 구름LEVEL
- 개발자
- Linux
- 자료구조
- spring boot
- dfs
- 도커
- 스프링부트
- 이직
- docker
- spring
- Java
- HashMap
- bfs
- 백엔드
- Today
- Total
목록dfs (4)
마이의 개발 블로그
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 방식 노드끼리 연결된 네트워크가 등장한다면 대체로 BFS와 DFS를 떠올리면 된다. 최단거리를 구해야 한다면 BFS를, 완전 탐색이 필요하다면 DFS를 사용해야하는데 이 문제에서는 모든 연결점을 탐색하여 네트워크의 개수를 파악해야하므로 DFS가 필요했다. 노드의 방문여부를 체크하고 종료조건을 삽입하기 위해 isVisited 배열을 활용했다. 로직 설명 solution 메서드 - 종료조건을 기록할 int[] isVisited 배열 선언 - computers배열에서 모든 노드의 연결정보를 순차적으로 탐색하며..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 방식 DFS(실패) 맵에서 이동할 수 있는 모든 경우의 수를 탐색하며 최종 목적지에 도달할 때마다 최소값을 갱신하고, 경우의 수가 최대 10000개이므로 DFS로 풀면 되는 문제라고 판단했다. 다만 보통의 DFS문제들은 visited 배열을 별도로 선언하여 푸는 반면 여기서는 maps[][]가 주어지므로 방문한 경로는 벽으로 표시(0으로 표시)하는 방식으로 maps를 이용했다. 이동은 동서남북의 네 가지만 가능하므로, 한 회차마다 네 방향으로 이동가능여부를 체크하고 이동하도록 했다. 문제는 금방 풀었으나..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 방식 모든 던전을 탐색하면서 던전 진입이 가능한지 여부(최소 피로도를 충족하는가)를 체크하고, 그에 따라 발생하는 두 가지 선택지를 고려해야하는 문제이다. 두 가지 선택지는 다음과 같다: 1) 최소 피로도 충족: 던전에 진입해 던전을 탐험 후 소모피로도를 감소시킨 후에 다음 던전을 탐험 2) 최소 피로도 미충족: 현재까지의 탐험 횟수와 최대 탐험 횟수(max)를 비교하여 큰 쪽을 최대 탐험횟수로 변경 이러한 접근 방식을 고려하면 모든 경우의 수를 탐색해야하는데, 던전의 개수가 8개 이하이기 때문에 DFS..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 모든 경우의 수를 탐색해야하는 문제이다보니 재귀함수를 선언하여 DFS로 해결했다. - int[] numbers를 탐색하며 마지막 인덱스까지 각 idx의 숫자를 더하거나 뺌 - idx가 마지막인 경우, sum을 target과 비교하여 일치하면 경우의 수 1을, 일치하지 않으면 0을 반환함 - 반환할 때마다 경우의 수가 더해져 최초 호출된 메서드는 전체 경우의 수를 반환함 Note - 멤버 변수(lastIdx, targetNum, targetNums)는 메서드를 간단하게 작성하고 싶어 사용했다. - 간단한 문제인..