-
programmers
[Programmers] 프로그래머스 추석 트래픽
https://programmers.co.kr/learn/courses/30/lessons/17676
-
programmers
[Programmers] 깊이/너비 우선 탐색(DFS/BFS) > 여행경로(c++)
https://programmers.co.kr/learn/courses/30/lessons/43164# 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr DFS를 사용해서 해결했다. 처음에는 모든 여행경로를 다 따져서 result 2차원배열에 모두 넣어두고, 그 안에서 알파벳 오름차순으로 정리하는 방법을 사용했는데, 정답 후보개수가 많아져서 답이 제대로 나오지않는듯 해서 방법을 바꿨다. tickets에 들어있는 경로들을 제일먼저 알파벳 오름차순으로 정렬 후에 처음으로 나오는 경..
-
programmers
[Programmers] 깊이/너비 우선 탐색(DFS/BFS) > 단어 변환(c++)
https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr *begin = "hit" 에서부터 target= "cog" 까지 DFS횟수(=cnt)를 모두 result에 저장해서 그 중 최솟값을 구하는 방법으로 풀었다. 1. words벡터 집합 중 target과 같은것이 없으면 Return 0 2. target과 같은 원소가 하나라도 있으면 DFS 실행 3. begin과 word..
-
programmers
[Programmers] 깊이/너비 우선 탐색(DFS/BFS) > 타겟 넘버(c++)
https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 문제에 대해 감이 잘 잡히지 않아서 구글 검색으로 솔루션을 찾아 각각 DFS와 BFS로 구현했다. DFS는 재귀로, 인덱스 1부터 numbers.size()까지 노드를 다 탐색했을 경우, sum값과 target값을 비교해 같을때 answer값을 1씩 증가시켰다. DFS DFS 코드 c++ void dfs(ve..
-
Baekjoon
[Baekjoon] 2589번 보물섬
https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 처음 풀때 DFS로 시도했었는데.. 최단거리를 구하는 문제라서 BFS로 풀어야 했다.. 처음부터 다시 풀었다,,,ㅠㅠ i=0, j=0부터 시작해서 treasure[i][j] = 'L' 인 경우에, 해당 위치에서 제일 먼 L까지 최단거리를 하나씩 다 구해주고, 그중에서 제일 큰 값을 Max에 넣어 출력해줬다. 최단거리는 i와j값을 q에 push하고, 해당 위치에서 상 하 좌 우 로 움직일 수 있는 곳으..
-
programmers
[Programmers]완전탐색 > 소수찾기(c++)
https://programmers.co.kr/learn/courses/30/lessons/42839# 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr DFS를 이용해서, 모든 경우를 탐색하면서 소수를 찾았다. 처음엔 어떻게풀어야하는지 감이 잡히지 않았는데 구글검색으로 DFS를 써서 풀수 있는걸 알았다. 1. num안에 numbers로 만들수있는 숫자를 하나씩 뽑아 저장한다. (예시가 17이면 1, 7, 17) 2. DFS안에 numbers[0]이 들어오면, isVisited[0] = true ..
