PS/Algorithm-JS

탐욕 알고리즘 (Greedy)탐욕 알고리즘(Greedy) 이란?탐욕 알고리즘은 말 그대로 "현재 상황에서 당장 가장 좋아 보이는 것만을 선택" 하는 알고리즘이다.미래를 깊게 고민하지 않고, 지금 이 순간의 이익만을 좇는다고 하여 '탐욕(Greedy)'이라는 이름이 붙었다.현실 세계에서는 최적의 해를 구하기 어려울 때, 근사해를 빠르게 구하기 위한 방법으로 주로 사용된다.코딩테스트에서의 탐욕 알고리즘코딩 테스트에서 탐욕 알고리즘 문제가 출제된다는 것은 탐욕적 선택이 항상 최적해로 이어지는 특수한 구조의 문제라는 의미이다.따라서 다음 두 조건을 확인하는 것이 중요하다.탐욕 알고리즘이 성립하는 조건탐욕적 선택 속성 (Greedy Choice Property)현재 단계에서 최선의 선택을 하는 것이 전체 최적해로..

정렬(Sorting) 알고리즘1. 선택 정렬 (Selection Sort)선택 정렬이란?선택 정렬은 이름 그대로 "매 단계에서 가장 작은(혹은 가장 큰) 원소를 선택해서 올바른 위치로 보내는" 정렬 방식이다.전체 데이터 중에서 가장 작은 값을 찾아 맨 앞에 놓고, 그다음 작은 값을 찾아 두 번째에 놓고 ... 이 과정을 끝까지 반복한다.특징: 정렬이 완료된 '앞쪽' 부분은, 그 이후의 어떤 과정에서도 위치가 다시 변경되지 않는다. (자리가 확정)선택 정렬 동작 방식선택 정렬(오름차순)은 다음과 같은 두 가지 단계를 반복하며 진행된다.아직 정렬되지 않은 부분(unsorted part)에서 가장 작은 값과 그 인덱스를 찾는다.찾은 가장 작은 값을 아직 정렬되지 않은 부분의 맨 앞 원소와 교체(swap)한다...

핵심 자료구조 알아보기1. 자료구조(Data Structure) 개요자료구조란?자료구조는 '데이터를 효율적으로 담고 관리하기 위한 구조'이다.데이터 수가 많아질수록 '어떻게' 저장하고 구성하느냐에 따라 프로그램의 성능이 크게 좌우되기 때문에 효율적인 자료구조가 필요하다.자료구조의 필요성100만 명의 사용자 정보가 있고, 이 중에서 특정 id를 가진 사용자를 찾는 작업이 하루에 1억 번 발생한다고 가정해보자.만약 이 데이터를 단순한 배열(Array)에 [user1, user2, ...]처럼 아무 순서 없이 저장했다면 어떨까?원하는 사용자를 찾기 위해 배열을 처음부터 끝까지 훑어야 하므로, 최악의 경우 100만 번의 비교가 필요하다. ($O(N)$)하지만 id를 key로 사용하는 Map 객체나 트리(Tree..

코딩 테스트 개요 및 JavaScript 문법0. 개요지금까지 파이썬(Python)으로 알고리즘을 공부하고 코딩 테스트를 치러왔다. 파이썬은 처음 배운 프로그래밍 언어였고, 그만큼 가장 익숙했기 때문이다.하지만 프론트엔드 개발자를 준비하는 지금, 자연스럽게 실무와 프로젝트에서 JavaScript와 TypeScript의 비중이 높아졌고, 파이썬은 상대적으로 멀어지게 되었다.또한 많은 기업이 개발 직무에 사용하는 언어(Stack)로 코딩 테스트 언어를 제한하기 시작했다. 특히 프론트엔드 직무는 JavaScript 로 지정된 경우가 많다.이에 대비하고자 JavaScript로 알고리즘을 공부하고 코딩 테스트를 준비하려 한다.1. 코딩테스트 알아보기알고리즘 공부를 시작하기 전에, 효율적인 준비를 위한 몇 가지 전..