Stack (스택) 선형 자료구조로 삽입, 삭제 연산이 한 방향에서 수행 LIFO(Last In First Out) : 나중에 들어간 원소가 먼저 나오는 구조 Stack 용어와 주요 연산 용어 Top : 스택에 데이터가 삽입될 위치 연산 push : 스택의 top에 원소 삽입 pop : 스택의 top에 있는 원소 삭제 및 반환 peek : 스택의 top에 있는 원소 반환 Stack 시간 복잡도 데이터 삽입/삭제 : O(1) top 데이터 조회 : O(1) 특정 데이터 조회 : O(n) Stack 활용 시스템 스택(System Stack)과 실행시간 스택(Runtime stack) 프로그램의 함수 호출과 복귀에 따른 실행 순서 관리 웹 브라우저 방문 기록 관리 (뒤로가기) 실행 취소 (undo) 수식의 후..
Array index로 element에 접근이 가능한 자료구조 일반적으로 논리적 저장 장소와 물리적 저장 장소가 같다. 찾고자하는 원소의 index를 알고 있으면 O(1)을 갖는다. 배열의 삭제 작업이 발생하면, 원소 접근 O(1)을 수행하고 빈 공간을 만든 다음 삭제한 원소보다 인덱스가 큰 원소들이 이동하는 비용이 발생하게 되어 O(n)을 수행하게 된다. ( worst case도 O(n) 수행 ) 배열의 추가 작업도 모든 원소들의 인덱스를 이동하는 비용이 발생하여 O(n)을 수행한다. 일반적인 의미의 배열은 메모리 영역을 연속적으로 사용한다. 이러한 배열은 밀집 배열(dense array)이라고 한다. 하지만, 자바스크립트의 배열은 배열 요소를 위한 각각의 메모리 공간이 동일한 크기를 갖지 않아도 되며..
동빈나쌤 강의 참고: https://youtu.be/2zjoKjt97vQ ✔️ 구현문제 풀어보기 2 위의 문제에서 고려해야할 사항은 다음과 같다고 생각했다. 1) 분과 초의 첫 번째 자리는 0부터 5까지이다. 2) 분과 초의 두 번째 자리는 0부터 9까지이다. 3) 시는 0부터 23까지 가능하다. 위의 예시를 수학적으로 풀었을 때는 3이 고정되었을 때, 올 수 있는 경우의 수가 5x9x5x9와 5x5x5x9 두가지가 된다고 생각했고 각각 시를 고정했을 때의 4가지 경우의 수와 5가 올 수 있는 3가지의 경우의 수를 조합하여 2025x4 + 1125x3 = 11475라는 수를 도출해낼 수 있었다. 하지만, 코드로 옮기기 위해서는 어떻게 해야할 지 제대로 된 감이 잡히지 않았다. 경우의 수가 적기 때문에 모..
동빈나쌤 강의 참고: https://youtu.be/2zjoKjt97vQ ✔️ 구현이란? 구현은 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 알고리즘 대회에서 구현 유형의 문제는 풀이를 떠올리는 것은 쉽지만, 소스코드로 옮기기 어려운 문제를 이야기한다고 한다. 일반적으로 알고리즘 문제에서의 2차원 공간은 행렬(Matrix)의 의미로 사용된다. 또한, 시물레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 사용된다. ✔️ 구현문제 풀어보기 N x N 만큼의 2차원 배열이 주어지고, 이동할 계획서에 따라 이동한 최종 도착 지점의 좌표를 찍는 문제이다. 해당 문제에서 고려할 사항은 다음과 같다. 1) U가 진행될 때 좌표 X가 1보다 작을 경우 U는 무시한다. 2) L이 진행될 때 좌..
동빈나쌤 강의 참고: https://youtu.be/2zjoKjt97vQ ✔️ 문제 풀어보기 - 모험가 길드 이번에는 모험가 길드라는 문제이다. 지난 시간에 이어서 해당 영상에서 풀지 않았던 마지막 문제를 이번 글에서 풀어보려고 한다. 우선 문제 해결을 위해서 X는 1차원 배열의 형태로 받는데, sort()를 이용하여 정렬이 필요하다는 생각을 했다. 예를 들어서 [2 2 3 2 1 4 5] 라는 형태의 입력을 받은 리스트가 [1 2 2 2 3 4 5] 와 같은 형태로 정렬된다면 가장 작은 수부터 그룹을 묶어 나가면서 성립되지 않은 그룹은 마을에 냅두면 될 것이다. N = int(input()) X = list(map(int, input().split())) result = 0 X.sort() 근데, 막상..
동빈나쌤 강의 참고: https://youtu.be/2zjoKjt97vQ ✔️ 그리디 알고리즘(탐욕법) 그리디 알고리즘이란 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미하며, 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 예로 N이 1260원일때, 500원 2개, 100원 2개, 50원 1개, 10원 1개로 최적의 해를 나타낼 수 있게 되는 것이 바로 그리디 알고리즘이다. 최적의 해를 나타낼 수 있는 이유는 가장 큰 화폐의 단위인 500원이 100원, 50원, 10원 즉, 작은 단위 화폐들의 배수이기 때문이다. 예로 500원, 400원, 100원이라는 잔돈을 800원의 N으로 나누어주게 되면 500원 1개, 100원 3개라는 값이 나오지만 400원 2개라는 최적의 해도 존재하기 때문에 이..
