본문 바로가기

알고리즘36

[Algorithm] 선택 정렬 (Selection Sort) 선택 정렬 (Selection Sort) Selection Sort는 Bubble Sort과 유사한 알고리즘으로, 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다. Selection Sort와 Insertion Sort를 헷갈려하는 사람들이 종종 있는데, Selection Sort는 배열에서 해당 자리를 선택하고 그 자리에 오는 값을 찾는 것이라고 생각하면 편하다. 프로세스 주어진 배열 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다. (pass) 1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞에 오게 되므로 그 다음 회전에서는 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다. 하나의 원소만 남을 때까지 위의 1~3 과정을 반복한다.. 2023. 2. 27.
[Algorithm] 거품 정렬 (Bubble Sort) 거품 정렬 (Bubble Sort) Bubble Sort는 Selection Sort와 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 이다. 이름의 유래로는 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어졌다고 한다. 프로세스 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, … 이런 식으로 (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환한다. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬.. 2023. 2. 27.
[Algorithm] 기본 수학 이론 - 점화식 점화식 (= 재귀식) 점화식(재귀식) 이란 수열에서 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식 대표적인 점화식 *a : 고정된 상수 등차 수열 : F(n) = F(n - 1) + a 등비 수열 : F(n) = F(n - 1) * a 팩토리얼 : F(n) = F(n - 1) * n 피보나치 수열 : F(n) = F(n - 1) + F(n - 2) ex) 등차 수열_재귀 let result; function recursive(s, t, number) { if (number == 1) return s; return recursive(s, t, number - 1) + t; } result = recursive(3, 2, 5); console.log(result); // output : 11 ex.. 2023. 2. 13.
[Algorithm] 기본 수학 이론 - 경우의 수 [순열, 조합] 경우의 수 어떤 사건 혹은 일이 일어날 수 있는 경우의 거짓수를 수로 표현 일상 생활에서의 경우의 수 주사위 : 던지는 결과, 1 ~ 6 사이의 숫자이므로 경우의 수는 6 윷 : 던지는 겨과, 도, 개, 걸, 윷, 모 이므로 경우의 수는 5 가위바위보 : 게임 결과, 가위, 바위, 보 중에 하나를 낼 수 있으므로 경우의 수는 3 동전 : 던지는 결과, 앞면 혹은 뒷면이므로 경우의 수는 2 완전 탐색으로 경우의 수를 푸는 알고리즘 순열 : 서로 다른 n개의 원소 중에서 r을 중복 없이 골라 순서에 상관 있게 나열하는 경우의 수 (nPr) 조합 : 서로 다른 n개의 원소 중에서 r을 중복 없이 골라 순서에 상관 없이 나열하는 경우의 수 (nCr) 중복 순열 : 서로 다른 n개의 원소 중에서 r개를 중복 있게.. 2023. 2. 13.
[Algorithm] 기본 수학 이론 - 알고리즘 복잡도 코딩테스트 할 때는 가장 중요시 여겨야 할 것 메모리 사용량, 효율성(시간 복잡도, 공간 복잡도) 이다. 시간 복잡도 입력 크기의 값에 대해 단위 연산을 몇 번 수행하는지 계산하여, 알고리즘의 수행시간을 평가하는 방법 3가지 점근적 표현법 O(빅오) : 최악의 상황을 고려하여 성능 측정 결과 표현 Θ(세타) : 평균적인 경우에서의 성능 측정 결과 표현 Ω(오메가) : 최선의 상황일 때의 성능 측정 결과 표현 아무래도 컴퓨터 프로그래밍쪽에서는 빅오 표기법이 널리 사용된다. 왜냐하면, 알고리즘의 평균적인 시간은 의미가 없는 경우가 많기 때문이다. 함수가 평균적으로 "대충 이정도 시간이 걸릴꺼야!" 보다 "절대로 이 시간 이상은 넘지 않을거야!" 라고 말하는 것이 신뢰도가 높고, 최악의 상황을 제일 고려해야 .. 2023. 2. 13.
[Programmers] (탐욕법[Greedy]) Lv 2. 구명보트 https://school.programmers.co.kr/learn/courses/30/lessons/42885 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr function solution(people, limit) { var answer = 0; people.sort((a, b) => b - a); for (let i = 0, j = people.length - 1; i = people[i] + people[j]) { ++answer; --j; } else ++answer; } return answer; } GitHub : https://github.. 2023. 1. 17.

티스토리툴바