YANGORITHM

그래프그래프는 사물을 연결하는 기본 개념에서 탄생했으며 노드 사이의 연결을 보여준다컴퓨터는 대부분 다른 컴퓨터와 연결되어 있다컴퓨터 네트워킹이란 실제로 여러 컴퓨터를 연결하는 것이다그래프는 컴퓨터(객체) 사이의 관계를 시각적으로 확인할 수 있는 주요 수단이다수학에서 파생된 그래프 이론은 컴퓨터 과학의 많은 응용 분야에 적용되고 있다그래프 vs 트리구조화된 트리와 달리 그래프는 현실 세계에 존재하는 연결 관계를 더 잘 표현한다현실 세계는 서로 다양하게 상호 작용을 하며, 그래프는 이러한 관계를 보다 정확하게 표현하고 모형화할 수 있다트리는 일종의 최소화된 그래프다그래프에서 동작하는 대부분의 알고리즘이 트리에서도 동작한다트리는 순환이나 순환적인 상호 작용이 없는 그래프와 같다다음은 트리 데이터 구조다다음은 ..

해시와 해시 함수해시는 어떤 길이의 임의 데이터를 고정 길이의 데이터로 매핑하는 것이다해시 함수는 이 해시를 실행하려고 하나의 값을 다른 값으로 변환하는 함수다해시 함수의 동작해시 함수는 데이터를 입력하면 해시값을 출력한다해시 함수의 특징은 입력되는 데이터가 문자든 문자열이든 기호든 출력되는 해시값의 길이가 항상 고정된다해시 함수는 서로 다른 입력 2개가 같은 해시값을 생성할 가능성도 있다이때 해시 충돌이 발생한다해시 함수가 잘 정의되었으면 내부 연산이 빠르고 충돌 발생이 적다해시 테이블해시 테이블은 해싱(해시 테이블을 이용하는 탐색)할 때 사용한다해시 테이블은 키와 값으로 구성된 검색 시스템이다해시 테이블에는 모든 키에 대응하는 값이 있다이러한 데이터 구성은 검색 수행 속도를 크게 증가시킨다보통 문자열..

트리트리 데이터 구조는 데이터를 계층으로 정렬한다컴퓨터 과학 분야에서 트리는 뒤집혀서 맨 위에 뿌리가 있는 나무처럼 보인다맨 위에 해당하는 노드를 루트 노드라고 한다트리의 나머지 요소는 루트 노드를 기준으로 구성한다루트 노드에서 멀어지는 방향으로 다른 노드가 연결되면, 그 노드를 하위 노드 또는 자식 노드라고 한다루트 노드를 향하는 방향으로 다른 노드가 연결 되면, 그 노드를 상위 노드 또는 부모 노드라고 한다리프 노드는 더 이상 자식 노드를 갖지 않는 트리의 마지막 노드다트리에서 노드를 연결하는 선을 에지라고 한다노드 하나와 그 자식 노드들로 구성된 트리를 서브트리라고 한다노드에는 데이터를 저장하며, 저장된 데이터를 식별하는 데 사용되는 키와 저장된 데이터인 값을 포함할 수 있다이진 트리(Binary ..

선형 데이터 구조선형 데이터 구조는 구성하는 요소들이 서로 인접해 순차적인 방식으로 정렬되어 있음을 뜻한다이런 데이터 구조는 이해하기 쉽고 개발할 때 사용하기 쉽다가장 일반적인 선형 데이터 구조는 배열과 리스트가 있다배열과 리스트는 범용적인 데이터 구조다거의 모든 데이터 구조가 배열이나 리스트에서 파생됐거나 어떤 방식으로든 이들을 사용한다배열배열은 데이터를 저장하고 구성하는 데 사용하는 가장 기본적인 데이터 구조 중 하나다배열은 자료형이 같은 요소들을 저장한다배열에 저장된 각각의 자료를 요소라고 하며, 0부터 번호가 매겨진다요소에 매겨진 숫자를 배열의 인덱스라고 한다배열의 구조배열의 구조는 다음과 같다배열 특징배열 내의 요소들은 순차적 또는 연속적으로 정렬되어 있다이 특징으로 배열 요소들을 임의의 순서로..

해당 게시물은 인프런 - "영리한 프로그래밍을 위한 알고리즘 강좌" 강의를 참고하여 작성한 글 입니다강의 링크문제그림에서 특정 좌표의 blob의 크기를 구하는 문제다Binary 이미지다각 픽셀은 image pixel 또는 background pixel이다서로 연결된 image pixel들을 blob이라고 부른다상하좌우 및 대각 방향으로도 연결된 것으로 간주한다위 그림에서는 총 4개의 blob이 있다문제를 정의하면 다음과 같다입력:N x N 크기의 2차원 그리드하나의 좌표 (x, y)출력:픽셀 (x, y)가 포함된 blob의 크기(x, y)가 어떤 blob에도 속하지 않는 경우에는 0Recursive Thinking이 문제를 Recursion을 이용해 해결해 본다수도 코드는 다음과 같다현재 픽셀이 imag..

해당 게시물은 인프런 - "영리한 프로그래밍을 위한 알고리즘 강좌" 강의를 참고하여 작성한 글 입니다강의 링크Maze 미로찾기2차원 배열 입구(0,0)에서 출구(n-1,n-1)까지 찾아가는 문제흰색 칸은 이동할 수 있는 통로, 파란색 칸은 이동할 수 없는 벽이다Recursive Thinking순환적으로 생각해 문제를 해결한다현재 위치에서 출구까지 가는 경로가 있으려면 1) 현재 위치가 출구이거나 혹은 2) 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나Decision Problem답이 yes or no인 문제로 recursion을 생각해본다다음은 위 해결법의 수도코드다boolean findPath(x, y) if (x, y) is the exit // 현..

해당 게시물은 인프런 - "영리한 프로그래밍을 위한 알고리즘 강좌" 강의를 참고하여 작성한 글 입니다강의 링크RecursionRecursion은 자기 자신을 호출하는 함수다void func(...) { ... func(...); ...}다음 Recursion 코드를 실행하면 무한루프에 빠진다public class Code01 { public static void main(String[] args) { func(); } public static void func() { System.out.println("Hello..."); func(); }}무한루프에 빠지지 않으려면?recursion을 무한 루프에 빠지지 않으려면 적절한 구조를 ..

파이썬에서는 우선순위 큐를 사용할 때 heapq 라이브러리를 이용한다heapq 자체는 최소 힙을 기반으로 구현돼 있다따라서 -5 같은 음수 값으로 힙을 구성하면 최대 힙처럼 만들 수도 있다 다음과 같은 함수가 제공된다 heapq.heappush(heap, item)힙 불변성을 유지하면서, item 값을 heap으로 푸시한다 heapq.heappop(heap)힙 불변성을 유지하면서, heap에서 가장 작은 항목을 팝하고 반환한다힙이 비어 있으면, IndexError가 발생한다팝 하지 않고 가장 작은 항목에 액세스하려면, heap[0]을 사용한다 heapq.heapify(x)리스트 x를 선형 시간으로 힙으로 변환한다 1234567891011121314import heapq  heap = [] heapq.he..