코딩 오름길

너비 우선 탐색(Breadth First Search)란?트리나 그래프를 탐색하는 기법 중 하나로, 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로 깊게 탐색하기 전에 넓게 탐색하는 것이다.두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다.미로 찾기 등 최단 거리를 구해야 할 경우 사용된다. 루트에서 시작한다 -> 큐: 1자식 노드들은 [1]에 저장한다. -> 큐: 2 3 4[1]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [2]에 저장한다. -> 큐: 3 4 5[2]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [3]에 저장한다. -> 큐: 4 5 6 7위의 과정을 반복한다.모든 노드를 방문하여 탐색을 마친다. Java..

그리디 알고리즘(탐욕법, Greedy Algorithm)이란"매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘이다그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다. 노드에서 가장 합이 높은 방법을 선택하는 방법은? 브루트 포스로 모두 살펴봐서 그중 가장 짧은 경로를 선택하는 경우 또는 외판원 순회 문제 문서에 나와있는 복잡한 전략을 쓸수 도 있음.일반적인 문제 해결 그리디 알고리즘을 사용할경우  그리디 알고리즘의 특징그리디 알고리즘은 탐욕 선택 속성(greedy choice property), 최적 부분 구조(optimal substructure) 특성을 가지는 문제들을 해결하는..

reduce란 JavaScript에서 배열을 순회하면서 누적된 값을 계산할 수 있게 도와주는 메소드입니다. 이 메소드는 배열의 각 요소에 대해 주어진 함수를 실행하며, 누적된 결과를 반환합니다. 이 함수는 배열을 하나의 값으로 축소(reduce)하는 역할을 합니다.기본 사용법reduce() 메서드는 다음과 같은 형태로 사용됩니다array.reduce(callback(accumulator, currentValue, currentIndex, array), initialValue);callback: 배열의 각 요소에 대해 실행되는 함수입니다.accumulator: 누적된 값 (처음에는 initialValue로 시작하고, 그 이후에는 이전 단계에서 반환된 값이 사용됩니다).currentValue: 현재 처리되는..

문제 화성 탐사 기계가 존재하는 공간은 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..