문제 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이문제를 보고 인물들의 계층 구조를 보고 먼저 생각한 알고리즘은 DFS이다. 이 문제의 경우 재귀를 이용하는 방법 대신 Stack으로 탐색 노드를 저장해 pop하여 탐색할 수 있도록 설계했다. 이 문제에서 햇갈렸던 점이 소개해 준 사람이 얻는 이득을 계산하는 로직이였는데, 이는 이득의 합 계산이 아닌 각 이득의 10퍼씩 전달해야한다. 이말은 (10 + 20 + 30) * 0.1이 아니라 (10 * 0.1)+(20 * 0.1)+(30 * 0.1)으로 계산해야 한다. 코드function solution(enroll, referral, seller, a..
그래프 탐색
문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이이번 문제는 단방향 그래프를 이용해 탐색을 진행할 것이다. 양방향 그래프 탐색을 생각도 해봤지만, 양방향을 사용하게 되면 모든 경로를 다시 처리해야하는 번거로움이 있기 때문에 단방향 그래프를 이용했다. DFS 알고리즘을 적용했으며, 각 탐색시 현재 위치, 양의 수, 늑대의 수, 방문할 노드를 전달한다. 이때 알고 가야하는 로직이 있는데, 방문할 노드를 결정할 때 방문할 노드에 있는 현재 노드를 현재 노드의 자식 노드들로 바꿔주어야 한다. 그래야지 중복으로 노드를 방문하지 않고 완전탐색을 진행할 수 있기 ..
문제https://school.programmers.co.kr/learn/courses/30/lessons/42861# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 해당 문제는 크루스칼 알고리즘을 이용해 최단 신장 트리를 구하며 풀이하는 문제이다.크루스칼 알고리즘을 이 문제를 통해 처음 알게되었는데, BFS 그래프 탐색인데 cost를 오름차순으로 정렬해 부모를 비교해 처리하는 알고리즘이라 생각한다. 코드const find = (parent, x) => { if (parent[x] === x) { return x; } return parent[x]..
문제https://level.goorm.io/exam/195694/%EB%B0%9C%EC%A0%84%EA%B8%B0/quiz/1 구름LEVEL난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다.level.goorm.io 풀이해당 문제는 그래프 탐색 문제이며 각 집이 연결되어있는지 확인하는 문제이다. 어떻게 보면 DFS 로 풀면 될거 같지만, DFS로 풀이를 진행하면 각 노드에서 재귀적으로 4방향씩 호출되어 시간초과 오류를 만날 수도 있다.... 코드const readline = require('readline');let rl = readline.createInterface({ input: process.stdin, output: process.stdout,});let n = null;l..
문제https://www.acmicpc.net/problem/16234 풀이이 문제는 BFS를 학습하기 위해 풀어본 문제이며 이 문제를 통해 BFS를 조금 알기 시작했다.... 문제에서는 각 칸마다 연합을 연결할 수 있는 나라인지 확인한 뒤 계속 인접 칸으로 이동해야 한다. 이러한 풀이 방식에서 인접 노드 탐색을 진행하는 BFS를 적용해야한다. bfs 함수를 실행하는 이중 for문은 각 칸마다 연합을 만들 수 있는지 검증하는 경우를 구현하기위해 사용했고, 해당 노드가 방문했던 노드임을 나타내는 visited 배열을 생성했으며 이 배열을 bfs 함수에 전달해 함수 내부에서 방문 여부를 확인해 방문 하지 않고, 함수에서는 상하좌우 방향의 노드와 현 위치의 노드 간의 차이가 문제에서 주어진 범위 안에 있다면 ..
1. 정의 우선 DFS와 BFS의 정의부터 간략하게 다시 알고 가도록 하자. DFS 깊이 우선 탐색이라는 이름에 맞게 탐색할 노드를 깊이를 우선으로 탐색하는 알고리즘이다. DFS의 구현은 Stack 또는 재귀적인 특징을 이용해 구현한다. BFS 너비 우선 탐색은 넓게 바로 아래 하위 노드를 모두 넓게 탐색한 뒤 그 아래의 노드들을 탐색하는 알고리즘이다. 큐를 이용해 탐색을 관리한다. 2. 구분 방법 그렇다면, 실제 코테나 문제를 해결할 때 무엇을 언제 사용해야하나? 우선 그 문제를 분석해봐야한다. 그래프 탐색에서 모든 정점을 방문하는가? DFS와 BFS 둘 다 가능하다. 경로의 특징을 저장 혹은 조합, 순열을 구해야 하는 문제인가? 고로타면 DFS를 이용하는게 유리하다. 최단 경로, 최단 거리를 구해야 ..
