TIL_Algorithm

오전에 첫 번째 Algorithm 특강을 들었다.

 

알고리즘이란, 컴퓨터가 따라 할 수 있도록 문제를 해결하는 절차나 방법이다(구글 검색 결과). 

 

Computational thinking이 프로그래밍이나 알고리즘 문제를 풀 때 뿐만이 아니라 다른 분야 혹은 일상 생활 속에서 컴퓨팅 사고를 하는 것은 많은 도움이 된다. 

 

좋은 알고리즘의 기준으로 공간 복잡도와 시간 복잡도가 있다.

 

공간 복잡도

프로그램을 실행 및 완료하는데 필요한 저장 공간의 양, 컴퓨터 저장공간의 기술 발달로 그렇게 중요하지는 않음.

 

시간 복잡도

특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간.

- 빅오메가(Big-Ω): 최선의 경우

- 빅세타(Big-Θ): 평균(중간)

- 빅오(Big-O): 최약의 경우 배열의 길이만큼 순회를 해야 함(시간 복잡도는 주로 빅오 표기법을 사용)

 

Big-O 종류

- O(1)(상수 복잡도): 데이터 양과 상관없이 항상 일정한 연산량을 갖는 알고리즘

- O(n)(선형 복잡도): 데이터 양(n)과 비례해 연산량도 증가하는 알고리즘

- O(n²)(2차 복잡도): 데이터 양이 증가할수록 데이터 양의 제곱만큼 연산량이 증가하는 알고리즘

 

알고리즘을 잘 하기 위해서는 자료구조를 잘 이해하고 있어야 한다. 자료구조에 따라 풀이 방법이 달라지기 때문이다.

 

자료구조의 종류

- array: 같은 타입의 변수들로 이루어진 집합, 메모리의 연속 공간에 값이 채워져 있는 형태

- linked list: 선언 때 크기를 지정하지 않고 주소로 계속 연결하여 연속된 공간이 필요하지 않아 빈 공간 활용 가능

정리: 배열 데이터 수가 자주 바뀌지 않고 참조가 자주 일어난다면 Array 사용, 데이터 삽입과 삭제가 자주 일어난다면 Linked list

 

오늘 알고리즘에 대한 뜻과 자료구조의 종류, 좋은 알고리즘이란 어떤 것인지 등에 대해 배웠다. 강의 후 Programmers 사이트를 통해 몇 개의 알고리즘 문제들을 풀어보았다. 내가 생각한 것을 컴퓨터가 알 수 있게 풀어서 프로그래밍 언어로 적어보는 것이 좀 어려웠다. 프로그래밍 언어로 작성하는 것은 경험이 있지만 이렇게 알고리즘 문제를 푸는 것이 처음이어서 그런지 한 문제 푸는 데 시간이 좀 걸렸다. 시간은 좀 걸릴지라도 문제를 정의하고 목표를 향해 풀어나가는 과정이 좀 재밌었다. 마치 퍼즐을 풀어가는 것 같았다. 앞으로 알고리즘 문제를 꾸준히 풀어서 감수성 풍부한 F인 나 이지만 computational thinking의 능력치를 마음껏 키워보겠다. 

 

오늘 실시간 강의가 이해하기 쉬워 좋았다. 알고리즘을 알아야 하는 이유에 대해 설명해 주신 부분이 가장 좋았다. 자세한 문제풀이나 방법 등은 혼자서 꾸준한 연습을 통해 채워나가는 것이 중요할 것 같다. 튜터님께 좋은 강의를 제공해 주신 점에 대해 매우 감사드린다.