출처: 프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/42842 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 카펫 문제 풀이 class Solution { fun solution(brown: Int, yellow: Int): IntArray { var width = 3 var height = 3 while (width >= height) { val y = (width - 2) * (height - 2) val b = width * height - y if (y == yellow && ..

다익스트라 알고리즘 다익스트라 알고리즘은 무엇인가요?? 다익스트라 알고리즘은 대표적인 최단 경로 탐색 알고리즘입니다. 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줍니다. 언제 사용하나요?? 말했다시피 목적지로 가기 위한 최단 경로를 구하기 위해 사용합니다. 특징은 음의 간선이 포함되지 않아 현실 세계에 데이터를 가지고 사용하기 좋습니다. 그래서 인공위성 GPS 내비게이션 등 다양한 곳에서 사용합니다. 문제가 그래프로 나와 최단 경로를 구해야 한다면 생각해 볼 만합니다. 왜 사용하나요?? 다익스트라 알고리즘은 다이내믹 프로그래밍입니다. 최단 경로로 가기 위해서는 가는 길도 최단 경로여야 합니다. 이전까지의 최단 경로를 저장해 구하려는 최단 경로를 구하기 때문에 작은 문제를 가지고 큰 문제를 ..

DFS ( Depth First Search ) 깊이 우선 탐색 / BFS( Breadth First Search ) 너비 우선 탐색 DFS와 BFS는 그래프의 전체를 탐색하는 완전 탐색 알고리즘의 기법 중 하나입니다. 아래에 애니메이션이 있습니다. 그림을 보시면 이해하기 수월하실 것입니다. 왼쪽의 그림은 DFS이고 오른쪽이 BFS 입니다. 먼저 DFS는 맨 위 정점부터 끝에 도달하면 돌아가 분기의 처음으로 돌아가 넘어가는걸 보실 수 있습니다. 이처럼 DFS는 가장 끝까지 가보고 그 다음 경우의 끝까지 계속해서 확인하며 가는 경우입니다. 오른쪽의 BFS는 갈 수 있는 분기를 하나씩 처리하며 가는 경우입니다. a가 b, c 로 갈 수 있고 b는 d,e c는 f,g 로 방문 처리를 하며 끝까지 갈 수 있습니..

아래에 3개의 문제가 있습니다. 1. 디펜스 게임 https://school.programmers.co.kr/learn/courses/30/lessons/142085 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 시소 짝꿍 https://school.programmers.co.kr/learn/courses/30/lessons/152996 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 3. 입국 심사 ..

플로이드 와샬 알고리즘 - 최단 거리 알고리즘 (2) 최단 거리 알고리즘 중에 하나인 플로이드 와샬 알고리즘을 알아보겠다. 그래프를 보면 1번에서 5번으로 가기 위한 방법은 아주 많은데 플로이드 와샬 알고리즘은 어떻게 가장 짧은 거리를 알 수 있을까? 그래프 초기화 1 2 3 4 5 6 1 0 5 9 14 many many 2 5 0 36 many 47 many 3 9 36 0 22 55 88 4 14 many 22 0 many 31 5 many 47 55 many 0 11 6 many many 88 31 11 0 먼저 그래프를 초기화한다. 그림은 무방향인데 방향이 있어도 똑같다. 방향이 있다면 없는 방향은 그냥 many라고 생각하고 큰 수를 넣어주든가 하자. 다만 +의 영향으로 Int.Max value..

노드 정점들을 연결하는데 가장 적은 비용으로 연결하려면 어떻게 해야할까?? 위의 질문에 해결하기 위한 대표적인 방법으로 크루스칼 알고리즘을 들 수 있습니다. 크루스칼 알고리즘으로 모든 노드를 지나면서 사이클이 생기지 않고 가장 적은 비용을 가는 경로를 알 수 있습니다. 아래에 4개의 그림이 있습니다. 4개의 그림 모두 그래프의 모든 정점을 지납니다. 또한 순환고리 즉 사이클이 생기지 않은 연결들입니다. 이러한 연결들을 신장 트리라고 합니다. 각 각의 그림의 가중치 합은 다음과 같습니다. 왼쪽 위 : 3+4+1 = 8 오른쪽 위 : 4+3+2 = 9 왼쪽 아래 : 4+5+2 = 11 오른쪽 아래 : 3+2+1 = 6 가장 적은 가중치의 합을 가진 그림은 오른쪽 아래에 있는 그래프입니다. 가장 작은 값을 갖..