HeeJ's

컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이기 때문에 연산 속도와 메모리 공간을 최대한 활용하는 효율적인 알고리즘이 필요하다. => 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있다. == 다이나믹 프로그래밍 (Dynamic Programming) 기법 다이나믹 프로그래밍으로 활용할 수 있는 대표적인 예시: 피보나치 수열 프로그래밍에서는 이러한 수열을 배열 혹은 리스트로 표현. '연속된 많은 데이터'를 처리하기 때문 파이썬: 리스트 자료형 / C, 자바: 배열 피보나치 함수 코드로 표현 # 피보나치 함수를 재귀 함수로 구현 def fibo(x): if x == 1 or x == 2: return 1 return fibo(x-1) + f..

리스트 내에 데이터를 매우 빠르게 탐색할 수 있음 순차 탐색(Sequential Search) : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 리스트의 데이터에 하나씩 방문하며 특정한 문자열과 같은지 검사하므로 구현도 간단함 리스트에 특정 값의 원소가 있는지 체크할 때도 순차 탐색으로 원소를 확인하고, 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용할 때도 내부에선 순차 탐색 진행 순차 탐색 소스코드 def seq_search(n, target, array): # 각 원소를 하나씩 확인 for i in range(n): # 현재의 원소가 찾고자 하는 원소와 동일한 경우 if array[i] == target: retu..

정렬(Sorting) 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색(Binary Search)이 가능해진다. 1. 선택 정렬 (Selection Sort) 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복 가장 작은 것을 선택해서 앞으로 보내는 과정을 반복하면 전체 데이터의 정렬이 이루어짐. [ 7, 5, 9, 0, 3, 1, 6, 2, 4, 8 ] 에서 가장 작은 데이터인 0을 1번째 인덱스인 7과 자리를 바꾼다. [ 0, 5, 9, 7, 3, 1, 6, 2, 4, 8 ] 두 번째로 가장 작은 데이터인 1과 2번째 인덱스인 5와 자리를 바꾼다. [ 0, 1, 9, 7,..

탐색(search) 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 대표적인 탐색 알고리즘 : DFS/BFS 제대로 이해하기 위해 기본적인 자료구조인 스택, 큐에 대한 이해 필요 자료구조(Data Structure) 데이터를 표현하고 관리하고 처리하기 위한 구조 기초 개념 : 스택, 큐 핵심 함수 삽입(push) : 데이터를 삽입한다. 삭제(pop) : 데이터를 삭제한다. * 오버플로우(Overflow) : 특정 자료구조가 수용할 수 있는 데이터의 크기가 가득 찬 상태에서 삽입 연산 수행 시 발생 언더플로우(Underflow) : 특정 자료구조에 데이터가 들어있지 않은 상태에서 삭제 연산 수행 시 발생 스택(stack) 후입선출(Last In First Out) 구조 초기단계 [ , , , , ] p..

구현 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 원하는 풀이과정을 원하는 프로그래밍 언어로 정확히 구현해낼 수 있어야 함. 모든 알고리즘 문제를 '구현'해야하기 때문에, 주로 구현 문제로 정의되는 것은 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제들을 의미한다. 구현하기 어려운 문제 예시 1. 알고리즘은 간단한데 코드가 길어지는 문제 2. 특정 소수점 자리까지 출력해야하는 문제 3. 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야하는(파싱 하는) 문제 등 => 프로그래밍 문법을 정확하게 숙지하거나, 라이브러리 사용 경험이 충분해야한다. + 완전 탐색(모든 경우의 수를 주저 없이 다 계산하는 해결 방법), 시뮬레이션(문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접..

그리디 알고리즘이란 글로벌 최적을 찾기 위해 각 단계에서 로컬 최적의 선택을 하는 문제 해결 알고리즘이다. 즉, 바로 눈 앞의 이익만을 좇는 알고리즘이다. 대부분의 경우에는 뛰어난 결과를 도출하지 못하지만, 드물게 최적해를 보장하는 경우도 있다. 어떠한 문제가 있을 때, 단순 무식하게 지금 당장 좋은 것을 고리는 방법이다. 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. * 탐욕 선택 속성 : 앞의 선택이 이후 선택에 영향을 주지 않는 것 그리디 알고리즘의 대표 문제들 1. 거스름돈 문제 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름 돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다. 손님에게 거슬러줘야 할..