유한한 단계를 통해 문제를 해결하기 위한 절차나 방법 어떠한 문제를 해결하기 위한 절차 컴퓨터 분야에서 알고리즘을 표현 하는 방법의사코드와 순서도 좋은 알고리즘정확성작업량메모리 사용량단순성최적성주어진 문제를 해결하기 위해 여러 개의 다양한 알고리즘이 가능 알고리즘의 성
2차원 배열의 선언 1차원 리스트를 묶어놓은 리스트2차원 이상의 다차원 리스트는 차원에 따라 인덱스를 선언2차원 리스트의 선언 : 행의 개수, 열의 개수를 필요로함 파이썬에서는 데이터 초기화를 통해 변수 선언과 초기화가 가능함 arr = \[\[1,2,3,4],\[
비트연산으로 부분집합 구하기
컴퓨터에서의 문자표현 영어가 대소문자 합쳐서 52개 이므로 6비트(64가지)면 모두 표현할 수 있다. 이를 코드 체계라고 함 000000 -> 'a', 000001 -> 'b'ASCII : 문자 인코딩 표준 유니코드 : 다국어 처리를 위한 표준문자열 압축
스택의 특성 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조스택에 저장된 자료는 선형 구조를 가짐선형구조 : 자료 간의 관계가 1대1비선형구조 : 자료 간의 관계가 1대 N스택에 자료를 삽입하거나 스택에서 자료를 꺼낼 수 있음마지막에 삽입한 자료를 가장 먼저 꺼
비선형 구조인 그래프 구조는 표현된 모든 자료를 빠짐없이 탐색하는 것이 중요1\. DFS2\. BFS"내가 다시 돌아올 곳을 저장"가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 계속 반복 탐색하여, 모든 정점을 탐색한다.스택의 후입선
우리가 하는 산수방식(중위 표기법)은 컴퓨터가 이해하는 방식이 아님 중위 표현식일반적으로 알고있는 산술 방식후위 표현식왜? 컴퓨터가 이해하는 산술 방식으로 변경해주기 위해 계산 속도가 올라감연산자가 피연산자 뒤에 온다.스택 내부와 외부의 연산자 우선순위중위 표현식으로
기본 과정DFS 진행방문 지점의 유망성(Promising) 확인유망함(Promising) ??방문 중인 노드의 하위 노드에 해답이 존재할 가능성이 있는 상태반대 개념 유망하지 않음 ( non-promising)유망하지 않다면, 부모 노드(vertax)로 복귀스택의 활용
큐의 특성스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조큐의 뒤에서는 삽입만 하고, 큐의 앞에서는 삭제만 이루어지는구조 선입선출 (First in First Out)큐에 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입된 원소는 가장먼저 삭제된다 큐의 기본연
순서가 있는 list, 각각의 끝에서 자료의 삽입과 삭제가 일어나는 자료구조선입선출 FIFOrear : 데이터의 삽입이 일어나는 곳 front : 데이터의 삭제가 일어나는 곳 addQ / Enqueue : 삽입 연산 deleteQ / Dequeue : 삭제 연산 sta
비선형 구조 1:n 관계를 가지는 자료구조원소들 간에 계층관계를 가지는 계층형 자료구조상위 원소에서 하위원소로 내려가면서 확장되는 나무 구조한 개 이상의 노드로 이루어진 유한 집합 노드 중 최상위 노드를 루트(root)라 함 n개의 분리 집합(부트리)으로 분리 될 수
이진트리 구성하기 < 정렬된 트리가 있다 라고 가정하고, 탐색하는 방법 BST 도 결국 트리의 한 종류 왼쪽에 있는 노드는 반드시 부모 노드보다 값이 작아야한다 오른쪽에 있는 노드는 반드시 부모 노드보다 값이 커야한다 중위순회 하면, 오름차순으로 된 것을 확인
1 << n2^n의 값을 갖는다.원소가 n개일 경우의 모든 부분집합의 수를 의미한다.Power set(모든 부분 집합)공집합과 자기 자신을 포함한 모든 부분집합각 원소가 포함되거나 포함되지 않는 2가지 경우의 수를 계산하면 모든 부분집합의 수가 계산된다i&(
해결할 문제를 고려해서 반복이나 재귀의 방법을 선택 일반적으로, 재귀적 알고리즘은 반복 알고리즘보다 더 많은 메모리와 연산을 필요로 함입력 값 n이 커질수록 재귀 알고리즘은 반복에 비해 비효율적일 수 있다많은 종류의 문제들이 특정 조건을 만족하는 경우나 요소를 찾는 것
집합에 포함된 원소들을 선택하는 것다수의 중요 알고리즘들이 원소들의 그룹에서 최적의 부분 집합을 찾는 거임N개의 원소를 포함한 집합의 부분 집합 (공집합 포함) == 2^N개 부분집합을 생성하기 위한 가장 자연스러운 방법사전적 순서로 생성하기 위한 가장 간단한 방법 원
서로 다른 n개의 원소 중 r개를 순서없이 골라낸 것이 조합(combination)
한번 선택된 것 번복안함, 이런 특성 때문에 대부분의 탐욕 알고리즘들은 단순 and 제한적인 문제들에만 적용 가능 최적화 문제가능한 해들 중 가장 좋은(최대 혹은 최소) 해를 찾는 문제해 선택 : 현재의 부분문제의 최적 해 구한 뒤, 이를 부분해집합에 추가실행 가능성
자료 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법반복할 때마다 검색 범위가 반으로 줄어들면서\-> 검색속도 빠름자료가 정렬된 상태여야 함자료 중앙에 있는 원소 고름 중앙 원소와 찾고자 하는 목표 비교중앙 원소가 목표보다
2진수, 8진수, 10진수, 16진수10진수 -> 타진수 변환원하는 타진법의 수로 나눈 뒤 나머지를 거꾸로 읽는 방법이 있음149(10진법) = 10010101(2진법)1의 보수 : 부호와 절대값으로 표현된 값을 부호 비트를 제외한 나머지 비트들을 0은 1로, 1은 0
그래프는 아이템들과 이들 사이의 연결관계를 표현함 그래프는 정점들의 집합과 이들을 연결하는 간선들의 집합으로 구성된 자료 구조 선형 자료구조나 트리 자료구조로 표현하기 어려운 N : N관계를 가지는 원소들을 표현하기에 용이함인접(Adjacency)두 개의 정점에 간선이
가장 짧은 경로를 찾는 알고리즘 한 지점 ~ 다른 특정 지점 모든 지점 ~ 다른 모든 지점 보통 그래프를 이용해 표현 각 지점은 그래프에서 '노드'로 표현지점 간 연결된 도로는 그래프에서 '간선'으로 표현 그리디 알고리즘 및 다이나믹 프로그래밍 알고리즘의 한 유형으로
서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들이다. 다시 말해 교집합이 없다. 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분한다. 이를 representative라 한다.집합을 표현 하는 방법 연결 리스트 트리 상호배타 집합 연산make-
그래프에서 최소 비용 문제 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리 두 정점 사이의 최소 비용의 경로 찾기신장트리n개의 정점으로 이루어진 무방향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 최소 신장 트리 (Minimum Spanni