본문 바로가기
반응형

Algorithm45

Level1. 프로그래머스 두 개 뽑아서 더하기 - JavaScript 접근 numbers array를 전달 받아 서로 다른 인덱스의 값 두개를 더해 만들 수 있는 수를 배열로 만들고 그 배열을 오름차순으로 정리하면 됩니다. 값을 더해 만들어진 수는 중복되면 안되는데 이때 자료구조 Set을 이용하면 쉽게 구현이 가능합니다. function solution(numbers) { const set = new Set(); for(let i=0; i 2020. 10. 20.
백준 1697 숨바꼭질 - C++ 접근 해당 문제는 BFS로 쉽게 접근할 수 있다. BFS나 DFS나 모든 정점을 1번만 방문하는 알고리즘인데 BFS는 간선의 가중치가 1이라는 조건일 때 최단 거리 구하는 문제에 응용할 수 있다. 문제에서 보면 어떤 정점 N에서 N-1, N+1, N*2의 정점에 도달하는데 걸리는 시간이 1이라고 한다. 여기서 시간 1은 정점과 정점을 연결하는 간선의 가중치가 될 수 있다. 문제는 다음과 같이 순차적을 처리 될 수 있다. 1. N과 K의 정점 입력 2. N을 큐에 푸쉬, N 방문 표시, N의 거리 표시 3. 큐가 빌 때까지 계속 돌기 4. 큐에서 한 정점을 빼서 이동 가능한 정점의 노드를 만든다. 5. 이동 가능 정점이 이동가능한 거리에 있는지 조건 확인 후 큐에 푸쉬, 방문 표시, 거리 표시를 한다. 6.. 2020. 9. 13.
백준 16947 서울 지하철 2호선 - C++ 접근 1. 순환선에 속하는 정점 파악 2. 순환선에 연결되어 있는 정점들의 최소거리를 구하기 순환선을 어떻게 구할지 부터 알아보면 다음과 같다. 순환선은 DFS를 이용하여 구할 수 있다. 먼저, 사이클을 형성하려면 최소 3개의 정점이 연결되어 있어야 한다. 그리고 1에서 시작한 정점이 다시 1로 돌아와 사이클을 형성하려면 3번의 이동이 필요하다. 사이클 형성 시 사이클에 속하지 않은 정점은 제외해주기 위해 사이클이 만들어질 때 시작 정점을 return값으로 주어야 한다. 예를 들어, 1 -> 2 -> 3 -> 1 탐색이 되었다고 하면 1 재방문시 이동거리가 3이어서 사이클이 형성된다. 그렇다면 return 하면서 cycle 기록을 해준다면 문제가 없다. 만일 4 -> 2 -> 1 -> 3 -> 2순으로 .. 2020. 9. 8.
백준 7562 나이트의 이동 - C++ 접근 나이트가 있는 위치 기준(x,y)으로 나이트가 이동할 수 있는 위치는 (x-1, y-2), (x-2, y-1), (x-2, y+1), (x-1, y+2), (x+1, y+2), (x+2, y+1), (x+2, y-1), (x+1, y-2) 이런식이다. 1. 주어진 x,y를 기점으로 갈 수 있는 곳에 표시를 한다. - bfs 탐색 알고리즘을 활용하여 똑같은 위치를 방문하지 않도록 한다. - 똑같은 위치는 0인지 아닌지로 판별한다.(0이면 아직 방문하지 않음) - 현재 위치에서 다음 위치로 이동할 때는 현재 위치 +1을 한다. 2. 계속 방문 하다가 현재 위치가 도착지 위치와 동일하면 얼마나 걸렸는지 출력 #include #include using namespace std; int A[301][301].. 2020. 7. 27.

티스토리툴바