본문 바로가기
반응형

분류 전체보기629

수의 체계(數의 體系) 자연수(Natural Number) == 양수, 양의 정수(Posivie Integer) 자연수란 1, 2, 3과 같이 1부터 시작하여 1씩 커지는 수를 이야기한다. 음수, 음의 정수((Negative Integer)) 음수란 자연수와 0 보다 작은 숫자를 의미한다. 어떠한 수 앞에 '-' 음의 부호를 사용하여 표기한다. 정수(Integer) 정수란 양의 정수, 음의 정수, 0을 포함하는 숫자를 의미한다. 분수(Fraction)와 대조되는 정수는 1570년대 라틴어 integer에서 유래되었으며 "손상되지 않은, 완전한"의 뜻으로, 비유적으로는 "오염되지 않은, 정직한"을 의미하며, 문자 그대로는 "만지지 않은"을 의미한다. 유리수(Rational Number) 유리수란 정수를 포함하며, 분모가 0이 아.. 2023. 8. 31.
깊이 우선 탐색(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.

티스토리툴바