[모두의 알고리즘] '알고리즘'이란?

알고리즘

• 알고리즘이란?
• ‘어떤 문제를 풀기 위한 절차나 방법’
• 어떤 문제가 있을 때 주어진 입력 정보를 원하는 출력 정보로 만드는 일련의 과정을 구체적이고 명료하게적은 것 (컴퓨터는 주어진 명령에 따라 계산을 수행하는 기계이므로)

 

• 알고리즘 분석
• 알고리즘의 성능이나 특징을 분석하는 것
• 한 가지 문제를 여러가지 방식으로 풀 수 있는데, 이 때 알고리즘의 특징과 효율성(얼마나 빠르고, 편한지)을 알고 있다면 최적의 방법으로 문제를 해결할 수 있다.1부터 n까지의 합 구하기

알고리즘 기초

1부터 n까지의 합 구하기 / O(n^2)

• 문제: 1부터 n까지 연속한 숫자의 합 구하기
• 1. 1부터 n까지 하나씩 더해간다: 1 + 2 + 3 + … + n
• 2. 가우스가 사용했다는 방법: n(n+1) / 2
• 입력 크기와 계산횟수
• 알고리즘의 계산은 입력의 크기가 커질수록 복잡해진다.
• 계산 복잡도(O)
• 어떤 알고리즘이 문제를 풀기 위해해야 하는계산이 얼마나 복잡한지 나타낸 정도

 

연습문제

1. 1부터 n까지 연속한 숫자의 제곱의 합을 구하는 프로그램을 for 반복문으로 만들어라. 

4번째 줄에 s+= i * i로 수정...  아마 s = s+i*i를 적었다가 지운거 같다.

 

2. 공식 = n(n+1)(2n+1) / 6

 

고등학교 때 분명등차, 등비, 피보나치 등등 공식 다 외웠는데 기억이안 난다.와우.

이 공식도 분명히 내 머릿속에 있었을 건데 완전히 생각나지 않았다.. 그래서 유도해보려고도 했는데

이런 공식들은 일단 다 외워서 풀었던 터라 유도도 실패해서 결국 검색하고 알아낸 답ㅎㅎ..

 

 

최대, 최솟값 찾기

• 문제: 숫자 n개를 리스트로 입력받아최솟값을구하는 프로그램을 만들어라.

 

n개를 입력받아라고 해서 동적으로 값을 입력받는 줄 알았으나 예시 문제도 그렇고 리스트가 주어져 있다는 가정하에 알고리즘을 짜보는 거였다. 

 

 

• 변형: 최솟값의위치(인덱스)를 찾는 프로그램 

 

 

동명이인 찾기 / O(n^2)

• 문제: n명 중두 명을뽑아 짝을 짓는다고 할 때 짝을 지을 수 있는 모든 조합을 출력하는 알고리즘을 만들어라.

>>> Tom - Jerry

>>> Tom - Mike

>>> Jerry - Mike

 

결과 값을 캡처해두지 않아 직접 적어보았는데, 위에 함수는 이렇게 이중 for문을 통해 각 인덱스를 비교해 볼 수 있다.

 

 

 

 

책의 내용을 굉장히 짧고 간단하고 나만 알아볼 수 있게 정리해봤다. 쉽게 쓰인 책이라 이 책으로 알고리즘을 정복하겠다는 마음은 없다. 쉽게 알고리즘을 공부하고, 활용해보기 위해 책을 선택했고 굉장히 기초적인 수준의 알고리즘이라고 생각하기 때문에  책의 구간구간을 완벽하게 이해하고 넘어가야겠다고 생각한다.