[알고리즘] 알고리즘 공부 시작하기 (참고 사이트)

1. 알고리즘이란?
1.1 알고리즘의 조건
1.2 알고리즘 공부 순서/방법
2. 알고리즘 기초 공부 사이트
3. 알고리즘에 필요한 기본 개념
3.1 시간 복잡도
3.2 자료구조
3.3 정렬
4.웹IDE
4.1 웹IDE 사용방법
5. 알고리즘 문제은행
6. 문제풀이
7. 티어 확인

1. 알고리즘이란?

▶ 알고리즘은 어떠한 문제를 해결하기 위한 일련의 절차를 공식화한 형태로 표현한 것이다.

최단 거리 혹은 최단 시간 내에 학교에 가는 길을 찾는 것, 샌드위치를 만들기 위한 재료를 준비하고 조리 순서를 진행하는 것, 매점에서 물건을 집고 계산하는 것까지 모두 알고리즘이라 할 수 있다.

프로그래밍에서 알고리즘은 input 값을 통해 output 값을 얻기 위한 계산 과정을 의미한다. 이러한 문제를 해결할 때, 정확하고 효율적으로 결과값을 얻기 위해서 알고리즘이 필요하다.

1.1 알고리즘의 조건

좋은 알고리즘을 만들기 위해서는 다음과 같은 조건을 충족시켜야 한다.

입력 : 외부에서 제공되는 자료가 0개 이상 존재한다.
출력 : 적어도 2개 이상의 서로 다른 결과를 내어야 한다. 즉 모든 입력에 하나의 출력- 이 나오면 안 된다.
명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 한다.
유한성 : 유한 번의 명령어를 수행 후 유한 시간 내에 종료한다.
효율성 : 모든 과정은 명백하게 실행 가능(검증 가능)한 것이어야 한다

1.2 알고리즘 공부 순서/방법

기본 개념 이해
기본 알고리즘 코드 학습
쉬운 문제 풀기
…
(어려운 개념 이해 & 문제 풀기)

🗺️ 취업을 위한 코딩테스트 정복 로드맵

코딩테스트 TIP

2. 알고리즘 기초 공부 사이트

LibreWiki

visualgo : 정렬, 트리 등의 원리를 이해하기 쉽게 시각화하여 한 단계씩 나타낸 사이트이다.. 그림과 코드가 한 화면에 나오고, 재생 버튼을 누르면 순차적으로 for 반복문을 따라 알고리즘 진행 과정을 보여준다.

연관된 글 :

알고리즘 기초

코딩테스트 자주사용하는 코드 (JAVA)

3. 알고리즘에 필요한 기본 개념

3.1 시간 복잡도

문제를 해결하는데 걸리는 시간과 입력의 함수 관계 프로그램을 작성할 때에 입력의 크기에 따라서 프로그램이 계산하는 횟수가 크게 달라진다. 입력된 자료의 양과 알고리즘 실행에 걸리는 시간 사이에는 어느 정도의 관계가 있다. 이것을 알고리즘의 시간 복잡도라 한다.

시간 복잡도를 나타낼 때에는 Big O 표기법을 이용한다. 예를 들어서, 1부터 n까지의 합을 구한다고 할 때, 다음과 같은 두 가지 방법이 있다.

// 방법 1
int n, res = 0;
for (int i = 1; i <= n;, i++) {
    res += i;
}
System.out.println(res);

// 방법 2
int n, res = 0;
res = n*(n+1)/2;
System.out.println(res);

코드를 살펴보면 방법1에서는 for를 이용해 n번의 연산을 하기 때문에 O(n) 의 시간 복잡도를 가진다. 반면 방법2에서는 n의 크기와 상관 없이 1번의 연산을 하기 때문에 O(1) 의 시간 복잡도를 가진다.

시간 복잡도설명

O(1)	상수 형태. n의 값에 상관없이 일정한 양의 계산만 한다.
O(logn)	로그 형태
O(n)	선형
O(nlogn)	선형로그 형태
O(n2),O(n3),⋯	다차 형태
O(2n)	지수 형태
O(n!)	팩토리얼 형태

맨 위에서부터 시간 복잡도가 낮고 빠르고, 아래로 갈 수록 시간 복잡도가 높고 느려진다. 제한된 시간 안에 올바르게 output을 출력하려면 시간 복잡도를 낮춰야 할 것임을 알 수 있다.

3.2 자료구조

자료구조란, 데이터 사이의 관계를 반영한 저장구조 및 그 조작 방법을 뜻한다. 컴퓨터의 프로그램을 실행하면 CPU에서 메모리로 데이터를 이동해서 처리하는데, 이 때 메모리를 효율적으로 사용하기 위해 데이터에 맞는 특성의 자료구조를 사용하는 것이 중요하다.

자료구조를 모두 나열하자면 아래 표와 같이 다양한 종류가 있다.