출처 : 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr # n개의 노드가 있는 그래프에서각 노드는 1~n으로 주어짐 # 가장 멀리 떨어진 노드란 최단경로로 이동 했을 때 간선의 개수가 가장 많은 노드 # 1번 노드로부터 가장 멀리 떨어진 노드의 개수 더보기 먼저, 생각해야 할 부분 1. 1번 노드로부터의 최단 경로를 찾고 있다 -> 다익스트라 알고리즘 2. BFS를 이용한 풀이 역시 가능하다. 다익스트라를 이용한 풀이 from ..
출처 : 이것이 취업을 위한 코딩테스트다 with Python, 숨바꼭질 이것이 취업을 위한 코딩 테스트다 with 파이썬 IT 취준생이라면 누구나 가고 싶어 하는 카카오, 라인, 삼성전자의 2016년부터 2020년까지의 코딩 테스트와 알고리즘 대회의 기출문제를 엄선하여 수록하였다. hanbit.co.kr 더보기 다익스트라 풀이 import sys from collections import Counter from heapq import heappop, heappush INF = float('inf') def solution(n, pass_list): #1번으로부터 최단 거리가 가장 먼 노드를 찾음. ad_matrix = [[INF for _ in range(n)] for _ in range(n)] # 인..
다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘은 그래프의 한 노드에서 모든 노드까지의 최단 거리를 구하는데 사용됩니다. 플로이드 워셜 vs 다익스트라 플로이드 워셜은 모든 노드에서 다른 모든 노드까지의 최단 거리를 구하는 용도인 반면, 다익스트라는 시작점을 1개의 노드로 정하고 이 노드로부터 다른 모든 노드까지의 최단 거리를 구합니다. BFS vs 다익스트라 BFS와 다익스트라 모두 최단 거리를 구하기 위한 알고리즘으로 사용될 수 있습니다. 단, BFS는 가중치가 없는 그래프인 경우에 최단 거리 문제를 푸는 방법이고, 다익스트라는 가중치가 다양한 경우에 최단 거리 문제를 푸는 방법입니다. 가중치가 없는 경우 모든 칸에 대해서 1번 이동하는 것이 동일한 가중치를 가진다 볼 수 있기 때문에, 가장..
출처 : 이것이 취업을 위한 코딩테스트다 with Python, 화성 탐사 이것이 취업을 위한 코딩 테스트다 with 파이썬 IT 취준생이라면 누구나 가고 싶어 하는 카카오, 라인, 삼성전자의 2016년부터 2020년까지의 코딩 테스트와 알고리즘 대회의 기출문제를 엄선하여 수록하였다. hanbit.co.kr 더보기 먼저, 생각해야 할 부분 1. 한 곳에서 다른 곳까지 이동할 때 최소 비용을 구하는 문제이다. (최단 거리 문제) 단, 이동 시 가중치가 다 다르다 -> 다익스트라로 풀어야한다. 2. 가중치 그래프 설정 방법 - 하나의 칸에 있는 값을 칸을 나가기 위한 값으로 설정한다 - 칸에 도착할 경우에도 에너지가 소모되므로, 이 경우 최단 거리 return 시 마지막 칸의 값을 별도로 더해주어야한다. 풀..
출처 : 이것이 취업을 위한 코딩테스트다 with Python, 정확한 순위 이것이 취업을 위한 코딩 테스트다 with 파이썬 IT 취준생이라면 누구나 가고 싶어 하는 카카오, 라인, 삼성전자의 2016년부터 2020년까지의 코딩 테스트와 알고리즘 대회의 기출문제를 엄선하여 수록하였다. hanbit.co.kr 더보기 먼저, 생각해야 할 부분 1. n명 중 정확한 순위를 알 수 있다는 것은 내 아래로 A명과 내 위로 B명을 더했을 때 n-1 명이라는 것과 같다. 2. 내 점수보다 아래 혹은 위임을 알 수 있는 방법은 해당 노드를 방문할 수 있는지 여부를 통해 알 수 있다. 3. r = 점수가 낮은 학생, c = 점수가 높은 학생으로 정했을 때, 1번 행은 1보다 1번 학생보다 점수가 높은 학생들의 방문 가..
플로이드-워셜(Floyd-Warshall) 알고리즘 플로이드 워셜 알고리즘은 그래프의 모든 노드에서 다른 모든 노드로 가는 최소 비용을 구하는 알고리즘입니다. 원리 1에서 3으로 가는 최단 거리를 구한다고 생각해봅시다. 1에서 3으로 바로 가는 거리는 13입니다. 하지만, 1에서 2로 갔다가, 2에서 3으로 가는 거리는 2 + 3으로 5입니다. 즉, 2를 거쳐가는 1 -> 2 -> 3이 최단 거리가 됩니다. 위와 같이 플로이드 워셜 알고리즘은 현재 내가 알고 있는 최단 거리와 다른 노드를 거쳐갈 때의 최단 거리를 비교하여 갱신합니다. 이를 점화식으로 나타내면 다음과 같습니다 # A에서 B로 가는 최단 거리 D[A][B] # 경유 노드 K D[A][B] = min(D[A][B], D[A][K] + D[K]..
출처 : 백준, https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net # n개의 도시 사이를 운행하는 m개의 버스가 있음 # A B C -> A 도시에서 B 도시로 가는 비용 C # 가격이 다른 동일 노선이 존재할 수 있음. # 각 도시에서 다른 도시로 가는 최소 비용을 출력 # 갈 수 없을 경우 0 출력 더보기 먼저, 생각해야 할 부분 1. 가격이 다른 동일 노선이 존재할 수 있다. 2. 모든 도시에서 모든 도시로 가는 최소 비용을 구해야한다. -..
출처 : 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/178870 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr # 비내림차순 정렬(점점 증가하는 수열)이 주어질 때 # 시작idx와 길이가 가장 작으면서 내부 요소 총합이 k인 부분 수열의 [시작 idx, 끝 idx]를 return 더보기 먼저, 생각해야 할 부분 1. 조합으로 풀기에는 sequence가 1,000,000개까지 존재할 수도 있다. 수열의 부분합을 빠르게 구할 수 있는 다른 방법은 무엇이 있을까? Two Pointer를..
출처 : 백준, https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net # NxN의 지도가 주어진다 # 모든 칸의 높이가 같으면 길 # 길이가 다른 경우에는 경사로를 놓아서 길을 만들 수 있다. # 경사로의 높이는 항상 1이고 높이는 L # 경사로는 낮은 칸에 놓고, L개의 연속된 칸에 모두 접해야함. # 경사로의 낮은 칸과 높은 칸의 차이는 1이어야한다. # 경사로를 놓을 낮은 칸의 높이는 모두 같아야하고, L개의 연속된 칸이 있어야함. # 지나갈 수 있는 길의 갯수 더보..
출처 : 백준, https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net # n x n의 격자, m개의 파이어볼 # 1:n은 연결되어있다 # 파이어볼은 r, c, m, d, s의 정보로 주어진다 # 1 ≤ ri, ci ≤ N -> 1부터 시작함. # d는 0~7까지 12시 기준 시계 방향 8방향, s는 한번 움직이는 칸 수 # 이동이 모두 끝나고, 2개 이상의 파이어볼이 같은 칸에 있다면 # 모두 합친 후 4개로 ..
출처 : 백준, https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net # 배열의 크기는 3 x 3 # 정렬은 1초마다 빈도 -> 숫자 순으로 오름차순 정렬하되 [숫자, 빈도, 숫자, 빈도, ...] 꼴로 새로운 배열은 만듬 # 정렬 시 0은 세지 않음 # 행의 개수와 열의 개수를 비교해서 행이 같거나 크면 행을 기준으로, 열이 크면 열을 기준으로 정렬 # 길이가 다를 경우 가장 긴 배열을 기준으로 모자란 길이를 0으로 채움 # 길이가 1..
출처 : 백준, https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net # 1초 동안 # 미세먼지가 모든 칸에서 동시에 확산 # 인접한 네방향으로 그 칸 // 5만큼 확산 # 확산시킨 칸의 미세먼지는 원래 미세먼지 - (원래 미세먼지 // 5) * 확산한 방 수 # 공기청정기가 있거나 칸이 없다면 확산 X # 공기 청정기 작동 # 위쪽은 반시계, 아랫쪽은 시계 방향으로 미세먼지가 한 칸 씩 이동 # 공기 청정기는 1열(0)에 있고 2칸을 차지하며 -..
