Algorithm/data_structure

1.  스택 (Stack)(1) 정의와 성질 스택은 기본적으로 후입선출(LIFO, Last-In-First-Out) 방식을 따르는 자료구조이다. 즉, 프링글스 통처럼 한 쪽에서만 데이터를 넣는 구조로 가장 마지막에 추가된 원소가 가장 먼저 제거된다! 이러한 특성 때문에 스택은 데이터를 일시적으로 저장하며 저장된 역순으로 접근해야할 때 유용하게 사용된다. (2) 관련 메서드 및 구현 관련 메서드 (C++ 기준) void push(const T& value);스택 최상단에 원소를 추가한다.시간복잡도 : O(1)void pop();스택 최상단 원소를 제거한다. 시간복잡도 : O(1)T& top();스택 최상단 원소를 조회한다.시간복잡도 : O(1)bool empty();스택이 비어 있는지 확인한다.시간복잡도 ..

1. 문제 설명문제 바로 가기 2. 풀이 과정문제 해결의 흐름기능 순서대로 개발함을 인지하자. progresses 배열을 순회하며 기능개발에 걸리는 시간(days)을 구하자.days가 큐에 저장된 이전 값보다 크다면 이전 작업의 개발에 현재 작업이 포함되지 않기에 끊어주어야 한다.작거나 같다면 현재 작업이 이전 작업에 포함되기에 끊어주지 않아도 된다.코드 #include #include #include using namespace std;vector solution(vector progresses, vector speeds) { vector answer; queue q; for (int i = 0; i 3. 후기   관심 있는 부분이 days가 가장 큰 q.front() 값임이 파악되면 ..

1. 문제 설명문제 바로가기2. 풀이 과정문제 해결의 흐름 처음에 문제 자체를 이해하는데 어려움이 있었다-! 자세히 살펴보니 입력된 주식가격(prices)이 언제까지 떨어지지 않는지 구해주면 되는 것이었다.이때, 주식 가격이 입력되는 간격은 1초이다. 입력된 가격 배열 prices를 순회하며 이전에 살펴봤던 값이랑 비교하였을 때 현재 값이 이전 값보다 더 작다면 이전 값의 가격이 하락한 것이기에 가격 하락 전까지의 기간을 배열에 저장해주자!4.에 해당하지 않는 값들은 Stack에 계속 쌓아준다.4.~5.의 과정이 끝난 이후 Stack에 있는 값들을 pop하며 배열에 저장한다.코드 #include #include #include using namespace std;vector solution(vector ..

1. 문제 설명문제 바로가기2. 풀이 과정문제 해결의 흐름     1. 2493 탑 문제와 굉장히 비슷하지만 이 문제는 이전에 추가된 자료가 아닌 새롭게 추가된 자료에 대해 조건을 걸어주어야할듯 하다!    2. 새롭게 추가되는 빌딩의 높이가 직전에 추가된 빌딩의 높이보다 높거나 같다면 이전에 추가된 빌딩의 관리자는 새롭게 추가된 빌딩을 보지 못한다.    3. 쉽게 생각해본다면 이전에 추가된 빌딩들보다 낮은 높이의 빌딩이 추가된다면 계속 빌딩을 볼 수 있다.    4. 반면, 이전 빌딩보다 높이가 높거나 같은 빌딩이 추가된다면 이전 빌딩의 관리자는 더 이상 추가되는 빌딩을 볼 수 없기에 삭제해주어야 한다.    5. 이 문제 역시 새롭게 추가되는 자료와 이전에 추가된 자료에 대해 관심이 깊으니 후입후출..

1. 문제 설명문제 바로가기2. 풀이 과정문제 해결의 흐름     1. 탑의 높이가 하나씩 추가되는 형태군!! 추가될 때마다 출력할지 한 번에 결과를 출력할지 생각해봐야겠다.     2. 음.. 탑의 높이가 추가될 때마다 바로 직전에 추가된 탑의 높이와 비교하는게 어떨까? 만약 추가된 탑의 높이가 더 크다면 바로 직전 탑이 수신을 절대 받지 못할 것이고, 이전에 추가된 탑의 높이가 더 크다면 수신을 받을 수 있겠군!!!     3. 이를 다음과 같이 구체화하여 조건문으로 나타내면 쉽게 풀 수 있을듯! 아래 조건문에 맞지 않는 높이는 수신을 받을 수 없기 때문에 삭제 처리해면 될듯 if (새로 추가되는 높이     4.  후입선출의 자료에 관심이 크기에 stack을 사용하여 풀어보자!! 코드 #includ..

빠르고 느림은 상대적인 표현이다. 효율성을 중요시하는 알고리즘 세계에서 빠르고 느림을 표현하는 척도는 무엇일까? 1. 빅 오 표기법이란? Big - O Nation, 즉 '빅 오 표기법'은 알고리즘의 시간 복잡도를 나타내는 표기법이다. 이 표기법을 통해 알고리즘의 빠르고 느림을 표현할 수 있고 코드가 얼마나 효율적인지 평가할 수 있다. 참고로 시간복잡도의 3가지 표현은 다음과 같은데, Big-O(빅-오) 표기법을 사용하는 이유는 최선의 경우를 고려했어도 최악의 경우가 발생할 수 있기에 최악의 시간을 기본적으로 대비하는 것이 바람직하기 때문이다. 이를 전문적으로 표현하면 빅 오표기법은 알고리즘의 효율성을 상한선을 기준으로 표기한다고 한다. (x축이 입력크기, y축이 실행시간일 때, 그래프가 위로 향할수록,..