코딩 오름길

문제 화성 탐사 기계가 존재하는 공간은 N x N 크기의 2차원 공간이며, 각각의 칸을 지나기 위한 비용(에너지 소모량)이 존재합니다. 가장 왼쪽 위 칸인 [0][0] 위치에서 가장 오른쪽 아래 칸인 [N-1][N-1] 위치로 이동하는 최소 비용을 출력하는 프로그램을 작성하세요. 화성 탐사 기계는 특정한 위치에서 상하좌우 인접한 곳으로 1칸씩 이동할 수 있습니다. 입력 조건 첫째 줄에 테스트 케이스의 수 T(1 = n: continue cost = dist + graph[nx][ny] # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우 if cost < distance[nx][ny]: distance[nx][ny] = cost heapq.heappush(q, (cost, nx, ny)) ..

다익스트라 알고리즘이란? 다이나믹 프로그래밍을 활용한 대표적인 최단경로(Shortest Path) 탐색 알고리즘입니다. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줍니다. 다만 이 때 음의 간선은 포함하지 않는데. 음의 간선이 존재하지 않기 때문에 다익스트라는 현실 세계에 사용하기 매우 적합한 알고리즘 중 하나입니다. 다익스트라 알고리즘 1. 출발지를 s로 정하고, 다음과 같이 표시한다. (s, t, x, y, z 순) 거리 = [0, inf, inf, inf, inf] 방문 = [True, False, False, False, False] 2. 갈 수 있는 노드들의 최소거리를 측정한다. s->t: 10 s->y: 5 (s, t, x, y, z 순) 거리 = [..

문제 도현이의 집 N개가 수직선 위에 있습니다. 각각의 집의 좌표는 x1, x2, ...., xn이고 , 집 여러 개가 같은 좌표를 가지는 일은 없습니다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 합니다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게하여 설치하려고 합니다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하세요. 입력 조건 첫째 줄에 집의 개수 N(2

문제 고정점(Fixed Point)이란, 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미합니다. 예를 들어 수열 a = [15, -4, 2, 8, 13]이 있을 때 a[2] = 2이므로, 고정점은 2가 됩니다. 하나의 수열이 N개의 서로 다른 원소를 포함하고 있으며, 모든 원소가 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 고정점이 있다면, 고정점을 출력하는 프로그램을 작성하시오. 고정점은 최대 1개만 존재합니다. 만약 고정점이 없다면 -1을 출력합니다. 단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받습니다. 입력 조건 첫째 줄에 N이 입력됩니다. ( 1

문제 N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있다. 이 때 이 수열에서 x가 등장하는 횟수를 계산하세요. 예를 들어 수열 [1, 1, 2, 2, 2, 2, 3} 이 있을때 x =2 라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력합니다. 단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받습니다. 입력 조건 첫째 줄에 N과 x가 정수 형태로 공백으로 구분되어 입력됩니다. (1

문제) 동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자. 가게의 부품이 총 5개 N = 5 [8, 3, 7, 9, 2] 손님은 총 3개의 부품이 있는지 확인요청 N = 3 [5, 7, 9] Output: No yes yes 접근 방식)가게의 부품을 sort 함수를 이용해 오름차순으로 정렬시키고 target을 손님의 요청사항 하나하나씩 이진탐색을 써서 찾아보자! 코드 1) 이진탐색 def binary_search(nums..

https://leetcode.com/problems/sort-colors/ Sort Colors - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 설명 - 빨간색을 0, 흰색을 1, 파란색을 2라 할 때 순서대로 인접하는 제자리 정렬을 수행하라 입력 [2, 0, 2, 1, 1, 0] 출력 [0, 0, 1, 1, 2, 2] 코드 from typing import List def sortColors(self, nums: List[int]) -> None: r..

https://leetcode.com/problems/k-closest-points-to-origin/ K Closest Points to Origin - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제) 평면상에 points 목록이 있을 때, 원점 (0, 0)에서 k번 가까운 점 목록을 순서대로 출력하라. 평면상 두 점의 거리는 유클리드 거리로 한다. 풀이) import heapq import math def cal_dist(point): return ma..

merge(머지)가 merge?(머지?) - merge는 합친다는 의미입니다. mergesort 개요 설명은 다음과 같다. [1, 2, 3, 5] # 정렬된 배열 A [4, 6, 7, 8] # 정렬된 배열 B [] # 두 집합을 합칠 빈 배열 C ↓ 1단계 : [1, 2, 3, 5] ↓ [4, 6, 7, 8] 1과 4를 비교합니다! 1

퀵소트 - 분할 정복을 통해 주어진 배열을 정렬하는 알고리즘 - 배열에서 기준 (pivot)을 잡고, 기준보다 값이 작은 집합과 큰 집합으로 나누고, 그 사이에 기준을 위치시킨다. - 작은 집합과 큰 집합을 대상으로 재귀호출하여 정렬한 뒤 결과를 합치면 정렬된 배열을 얻을 수 있다. 설명은 다음과 같다. [1, 6, 2, 9, 4] # 정렬되지 않은 배열 1단계: [1, 6, 2, 9, 4] 마지막 원소인 4를 pivot으로 삼습니다. pivot보다 작은 집합의 인덱스 i를 -1로 설정합니다. (i=-1) 2단계: [1, 6, 2, 9, 4] j를 0에서부터 3까지 살펴봅니다. j가 0이므로 지금 살펴보고 있는 값은 1 입니다. 1는 pivot(4)보다 작습니다. i를 1 증가시켜 0으로 만듭니다. i ..