Computer Science/Algorithem (10) 썸네일형 리스트형 알고리즘 | 알고리즘 표기법 ✔ 학습목표 알고리즘 실행 시간의 상한과 하한을 표기할 수 있다. 알고리즘의 효율성 프로그램을 작성한 후에 실행하면 작업이 완료될 때까지 어느 정도 시간이 걸린다. 처리하는 데이터가 많아지고, 작업이 복잡해질수록 이 시간은 매우 중요하다. 그래서 알고리즘의 시간 효율성과 공간 효율성(메모리)을 나태 내기 위해 표기법을 사용한다. 두 가지 효율, 즉 시간 복잡도와 공간 복잡도를 나타내는 방법으로는 빅오(Big O), 빅오메가(big Ω),빅세타(big Θ) 표기법이 있다. 강의에서는 빅오와 빅오메가를 다룬다. Big O Big O는 알고리즘 실행 시간의 상한, 쉽게 말하자면 최악의 복잡도를 나타낸다. 복잡도를 비교하자면 다음과 같다. 앞서 배운 검색 알고리즘을 생각해보면 선형검색은 O(n), 이진 검색은 .. 알고리즘 | 검색 알고리즘 ✔ 학습목표 주어진 배열 속에서 특정 값을 찾는 방법을 설명할 수 있다. 배열 본 글에서부터는 이제껏 배운 내용(메모리의 구조, 자료형, 배열 등)을 바탕으로 검색이나 정렬과 같은 문제풀이 알고리즘을 학습할 것이다. 이에 앞서 배열 속에서 특정 값을 찾는 방법을 이해해야 한다. 배열은 한 자료형의 여러 값들이 메모리상에 모여있는 구조다. 컴퓨터는 배열을 볼 때 인덱스 하나하나에 접근하게 된다. 이때 어떤 값이 배열에 들어 있는지 확인하는 데는 정렬 여부에 따라 두 가지 방법이 있다. 선형 검색 선형 검색은 순서대로 하나씩 보는 것이다. 배열의 인덱스를 처음부터 끝까지 하나씩 증가시키며 원하는 값이 들어있는지 확인한다. 50이라는 숫자를 찾는 의사 코드로 예를 들어보자. For i from 0 to n-1.. 이전 1 2 다음
