본문 바로가기

Computer Science

 (28)
알고리즘 | 선택 정렬 ✔ 학습목표 선택 정렬의 원리와 실행 시간을 설명하고 구현할 수 있다. 선택 정렬 선태 정렬(selection sort)은 버블 정렬과 마찬가지로 정렬을 위한 알고리즘 중 하나이다. 선택 정렬에서는 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환한다. 넣을 위치는 이미 정해져있고, 어떤 수를 넣을지 선택한다는 게 특징이다. 선택 정렬은 아래와 같은 의사 코드로 나타낼 수 있다. For i from 0 to n–1 Find smallest item between i'th item and last item Swap smallest item with i'th item 이해를 위해 간단한 GIF를 보자. 선택 정렬은 버블 정렬과 달리 교환 횟수가 ..
알고리즘 | 버블 정렬 ✔ 학습목표 버블 정렬의 원리와 실행 시간을 설명하고 구현할 수 있다. 정렬 어떤 배열이 주어졌을 때, 그 배열이 미리 정렬되어 있다면 훨씬 빠른 속도로 검색이 가능하다. 정렬하기 위한 방법은 여러 가지가 있으며 각각의 효율성도 다르다. 이번 글에서는 그중 하나인 버블 정렬에 대해 공부한다. 버블 정렬 버블 정렬(bubble sort)은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법을 말한다. 마치 거품이 터지면서(서료 비교 및 교환하면서) 위로 올라가는(옆으로 이동하는) 것처럼 말이다. 이는 접근법이 간단하다는 장점이 있지만, 자칫하면 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수도 있다. 버블 정렬은 아래와 같은 의사 코드로 나타낼 수 있다. Repe..
알고리즘 | 선형 검색 ✔ 학습목표 주어진 배열 또는 구조체에서 선형 검색(linear research)을 할 수 있다. 1) 선형 검색 자료를 검색하는 데는 다양한 알고리즘이 사용될 수 있다. 우리는 그 예시로 선형 검색과 이진 검색을 배웠다. 선형 검색은 원하는 원소가 발견될 때까지 순서대로 보는 방법이다. 본 글에서는 주어진 배열에서 선형 검색으로 값을 찾는 방법을 배운다. 효율성 선형 검색은 정확하지만 효율적이지 못한 방법이다(알고리즘 표기법에서 배운 대로 시간의 상한선이 O(n)이다). 이는 자료가 정렬되지 않거나 그 어떤 정보도 없어 하나씩 찾아야 하는 경우에만 유용하다. * 참고로 검색에 앞서 정렬이 필요한 이유가 이것이다. 정렬은 시간이 오래 걸리고 공간을 많이 차지하지만 매우 큰 데이터를 다룰 경우 시간을 단축..
알고리즘 | 알고리즘 표기법 ✔ 학습목표 알고리즘 실행 시간의 상한과 하한을 표기할 수 있다. 알고리즘의 효율성 프로그램을 작성한 후에 실행하면 작업이 완료될 때까지 어느 정도 시간이 걸린다. 처리하는 데이터가 많아지고, 작업이 복잡해질수록 이 시간은 매우 중요하다. 그래서 알고리즘의 시간 효율성과 공간 효율성(메모리)을 나태 내기 위해 표기법을 사용한다. 두 가지 효율, 즉 시간 복잡도와 공간 복잡도를 나타내는 방법으로는 빅오(Big O), 빅오메가(big Ω),빅세타(big Θ) 표기법이 있다. 강의에서는 빅오와 빅오메가를 다룬다. Big O Big O는 알고리즘 실행 시간의 상한, 쉽게 말하자면 최악의 복잡도를 나타낸다. 복잡도를 비교하자면 다음과 같다. 앞서 배운 검색 알고리즘을 생각해보면 선형검색은 O(n), 이진 검색은 ..
알고리즘 | 검색 알고리즘 ✔ 학습목표 주어진 배열 속에서 특정 값을 찾는 방법을 설명할 수 있다. 배열 본 글에서부터는 이제껏 배운 내용(메모리의 구조, 자료형, 배열 등)을 바탕으로 검색이나 정렬과 같은 문제풀이 알고리즘을 학습할 것이다. 이에 앞서 배열 속에서 특정 값을 찾는 방법을 이해해야 한다. 배열은 한 자료형의 여러 값들이 메모리상에 모여있는 구조다. 컴퓨터는 배열을 볼 때 인덱스 하나하나에 접근하게 된다. 이때 어떤 값이 배열에 들어 있는지 확인하는 데는 정렬 여부에 따라 두 가지 방법이 있다. 선형 검색 선형 검색은 순서대로 하나씩 보는 것이다. 배열의 인덱스를 처음부터 끝까지 하나씩 증가시키며 원하는 값이 들어있는지 확인한다. 50이라는 숫자를 찾는 의사 코드로 예를 들어보자. For i from 0 to n-1..
컴퓨팅 사고 | 코드의 디자인 ✔ 학습목표 CS50 IDE에서 코드의 정확성과 디자인을 관리하는 방법을 설명할 수 있다. 규모가 큰 프로그램을 작성할 때에는 보통 여럿이 작업을 진행한다. 이때는 코드의 내용뿐만 아니라 형식도 신경 써야 한다. 같은 내용이라 하더라도 어떻게 표현하느냐에 따라 코드를 이해하고 수정하는 속도가 달라진다. CS50 IDE에서는 check50과 style50이라는 프로그램을 사용할 수 있다. check50 check50은 코드의 정확도를 확인하는 자동 검사 프로그램이다. hello.c라는 프로그램을 검사하고 싶다면 명령창에 'check50 cs50/preblems/hello'를 입력하면 된다. 간단한 깃허브 계정 인증과정을 거치면 검사 결과(피드백)가 나온다. style50 style50은 코드가 심미적으로 ..
컴퓨팅 사고 | 디버깅 ✔ 학습목표 디버깅하는 여러 방법을 설명할 수 있다. 버그와 디버깅 버그(bug)는 코드에 들어있는 오류를 말한다. 코드에 있는 버그를 식별하고 고치는 과정이 디버깅(debugging)이다. 프로그래머는 디버거라 불리는 프로그램을 사용해서 디버깅을 한다. 디버깅의 기본 프로그램은 일반적으로 인간보다 훨씬 빠르게 연산을 수행하기 때문에, 프로그램을 실행시켜보는 것만으로는 무엇이 잘못됐는지 찾기 어렵다. 그래서 디버거를 사용한다. 디버거는 프로그램을 특정 행에서 멈출 수 있게 해 주기 때문에 버그를 찾는데 도움이 된다(이때 프로그램이 멈추는 특정 지점을 중지점이라고 한다). 디버거를 사용해 프로그래머는 프로그램을 한 번에 한 행씩 실행할 수 있고, 프로그램이 내리는 모든 결정을 단계별로 따라갈 수 있다. 방..
컴퓨팅 사고 | 컴파일링 ✔ 학습목표 컴파일링의 네 단계를 설명할 수 있다. 컴파일링 지금까지는 아무것도 모른 채 코드를 컴파일했다면, 이제부터는 연습과 응용을 통해 동작 원리를 이해할 수 있을 것이다. C 코드로 작성된 쉬운 예시(hello.c)를 보자. #include int main(void) { printf("hello, world\n"); } "hello, world"를 출력하는 프로그램이다. 우선 main 이라는 함수가 있다. 이는 프로그램의 시작점으로 실행 버튼을 클릭하는 것과 같다. main 함수 안의 printf는 출력을 담당하는 함수이다. 이 함수를 사용하기 위해 stdio.h 가 필요하다. stdio.h는 C언어로 작성된 헤더 파일로, printf 함수의 프로토 타입을 담고 있다. C언어 강의에서 우리는 cl..

티스토리툴바