본문 바로가기

프로그래밍/Algorithm109

[프로그래머스 Programmers] 거스름돈 문제 설명 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5원을 거슬러 줘야 하고 1원, 2원, 5원이 있다면 다음과 같이 4가지 방법으로 5원을 거슬러 줄 수 있습니다. 1원을 5개 사용해서 거슬러 준다. 1원을 3개 사용하고, 2원을 1개 사용해서 거슬러 준다. 1원을 1개 사용하고, 2원을 2개 사용해서 거슬러 준다. 5원을 1개 사용해서 거슬러 준다. 거슬러 줘야 하는 금액 n과 Finn이 현재 보유하고 있는 돈의 종류 money가 매개변수로 주어질 때, Finn이 n 원을 거슬러 줄 방법의 수를 return 하도록 solution 함수를 완성해 주세.. 2023. 9. 1.
깊이 우선 탐색(Depth-first search, DFS) 깊이 우선 탐색이란? 분류 : 검색 알고리즘 자료 구조 : 그래프(Graph) 깊이 우선 탐색(Depth-first search, DFS)은 맹목적 탐색방법의 하나로 탐색트리의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표 도일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다. 의사 코드(Pseudo Code) DFS(G, u) u.visited = true for each v ∈ G.Adj[u] if v.visited == false DFS(G,v) init() { For each u ∈ G u.visited = false For each u ∈ G D.. 2023. 8. 30.
스택(Stack) 자료구조 스택(Stack)이란? 스택은 데이터를 후입선출(First-In Last-Out) 방식으로 저장하는 자료구조이다. 데이터를 제한적으로 접근 할 수 있는 구조이며, 한쪽 긑에서만 자료를 넣거나 뺄 수 있는 구조이다. 스택은 콜 스택(Call stack)이라 하여 컴퓨터 프로그램의 서브루틴에 대한 정보를 저장하는 자료구조로써 널리 활용된다. 컴파일러가 출력하는 에러도 스택처럼 맨 마지막 에러가 가장 먼저 출력되는 순서를 보인다. 또한 스택은 메모리 영역에서 LIFO 형태로 할당하고 접근하는 구조인 아키텍처 레벨의 하드웨어 스택의 이름으로도 널리 사용된다. 이외에도 꽉 찬 스택에 요소가 넘쳐서 에러가 발생하는 것을 스택 버퍼 오버플로(Stack Buffer Overflow)라고 부른다. 프로그래밍 관련 질의응.. 2023. 8. 30.
너비 우선 탐색(Breadth-first search, BFS) 너비 우선 탐색이란? 분류 : 검색 알고리즘 자료 구조 : 그래프(Graph) 너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 ㅇ낳은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. 의사 코드(Pseudo Code) def breadth_first_search(problem): # a FIFO open_set open_set = Queue() # an empty set to maintain visited nodes closed_set = set() # a dictionary to maintain meta information .. 2023. 8. 30.
그래프(Graph) 자료구조 그래프(Graph)란 무엇인가? 정점(Vertex)과 그 정점을 연결하는 간선(Edge)을 하나로 모아 놓은 자료구조. 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조 G = (V, E) ex. 지도, 지하철 노선도, 전기 회로의 소자들, 도로 등 그래프의 종류 무방향 그래프(Undirected graph) 두 정점을 연결하는 간선에 방향이 없는 그래프, 두 정점의 양 방향으로 이동 가능 방향 그래프(Directed graph) 두 정점을 연결하는 간선에 방향이 있는 그래프. 특정 방향으로만 이동 가능 가중 그래프(Weighted graph) 정점을 연결하는 간선에 가중치(Weight)가 있는 그래프. 네트워크(Network) 라고도 함 완전 그래프(Complete graph) 그래프의 모든 정.. 2023. 8. 29.
[프로그래머스 Programmers] 배달 문제 설명 N개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 도로를 지날 때 걸리는 시간은 도로별로 다릅니다. 현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다. 각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 합니다. 다음은 N = 5, K = 3인 경우의 예시입니다. 위 그림에서 1번 마을에 있는 음식점은 [1, 2, 4, 5] 번 마을까지는 3 이하의 시간에 배달할 수 있습니다. 그러나 3번 마을까지는 3시간 이내로.. 2023. 8. 29.

티스토리툴바