본문 바로가기

알고리즘37

[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.
[Technical Organize] 기술면접_자료구조&알고리즘 문제. 시간복잡도란알고리즘을 구성하는 명령어들이 몇번이나 실행됬는지 센 결과(frequency count) +각 명령어의 실행시간(execution time) 을 곱한 합계를 의미함그러나 각 명령어의 실행시간은 특정 하드웨어 혹은 프로그래밍 언어에 따라서 그 값이 달라질 수 있기 때문에알고리즘의 일반적인 시간 복잡도는 명령어의 실제 실행시간을 제외한 명령어의 실행 횟수만을 고려하게 된다.시간의 복잡도는 크게 세가지로 나눌 수 있다.최상의 경우, 최악의 경우, 평균 => 이래서 표기법도 3개가 존재하는것이다.시간과 공간은 반비례 하는 경향이 있다.요즘은 공간보다는 시간이 우선이다!정의 : 프로그램을 실행시켜 완료하는데 걸리는 시간을 의미한다. 어떤 프로그램의 실행 시간을 추정하기 위해서는 모든 기본 명령문.. 2022. 12. 28.

티스토리툴바