본문 바로가기

전체 글669

모노토닉 스택(monotonic stack) 개념, 작동원리 + 예제 문제들 (주식 가격, 탑, 히스토그램에서 가장 큰 직사각형 찾기) 1. 모노토닉 스택이란?모노토닉 스택 개념모노토닉 스택(Monotonic Stack)은 원소들이 단조 증가하거나 단조 감소하는 순서를 유지하는 스택이다. 즉, 스택에 삽입되는 값들이 항상 특정한 순서를 따른다. 예를 들어, 단조 증가 스택은 스택에 있는 값들이 항상 오름차순(increasing)을 유지하도록 구성되며, 단조 감소 스택은 스택의 값들이 내림차순(decreasing)을 유지한다. 이 스택의 중요한 점은 특정 규칙을 만족시키기 위해 스택에서 값을 꺼내면서 문제를 해결한다는 점이다. 모노토닉 스택의 핵심은 배열을 한 번만 순회하면서 각 요소에 대해 문제의 요구 사항을 만족시키는 연산을 할 수 있다는 것이다. 이때 요구 사항은 일반적으로 다음 큰 수, 이전 작은 수 등을 찾는 데 사용된다. 이 과.. 2024. 10. 6.
[백준] 히스토그램에서 가장 큰 직사각형 (자바 풀이) 📌 문제히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다. 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오. ⚔ 입력 및 출력 입력 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서.. 2024. 10. 5.
[프로그래머스] 표 편집 (2021 카카오 채용연계형 인텁십, 자바 풀이) https://school.programmers.co.kr/learn/courses/30/lessons/81303 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr   📌 문제업무용 소프트웨어를 개발하는 니니즈웍스의 인턴인 앙몬드는 명령어 기반으로 표의 행을 선택, 삭제, 복구하는 프로그램을 작성하는 과제를 맡았습니다. 세부 요구 사항은 다음과 같습니다  위 그림에서 파란색으로 칠해진 칸은 현재 선택된 행을 나타냅니다. 단, 한 번에 한 행만 선택할 수 있으며, 표의 범위(0행 ~ 마지막 행)를 벗어날 수 없습니다. 이때, 다음과 같은 명령어를 이용하여 표를 .. 2024. 9. 30.
[프로그래머스] 두 개 뽑아서 더하기 https://school.programmers.co.kr/learn/courses/30/lessons/68644  📌 문제정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요.⚔ 제한 사항numbers의 길이는 2 이상 100 이하입니다.numbers의 모든 수는 0 이상 100 이하입니다.  👀 문제 해석이 문제는 주어진 정수 배열 numbers 에서 서로 다른 두 개의 수를 선택해 그 합을 구한 뒤, 이를 오름차순으로 정렬하여 반환하는 문제이다. 각 수는 배열에서 다른 인덱스에 있는 수와 조합되어야 한다. 또한 중복된 합은 한 번만 포함.. 2024. 9. 15.
항해 플러스 백엔드 5기 수료 회고 - 여름 방학 경험치 이벤트가 끝나면? 이 글에 대해서 - 요약이 글은 항해 플러스 백엔드 5기 과정의 수료 회고 글입니다. 6 ~ 10주 차 과정 중심의 내용을 톺아보며, 항해 플러스가 제게 어떤 의미였는지를 다룹니다. 더불어서 지속가능한 개발자로 성장하기 위한 생각을 나눕니다. 5 ~ 6주차 과정 중간 회고 글은 아래 링크로 들어가면 볼 수 있어요! 👇🏻 https://upcurvewave.tistory.com/700 항해 플러스 백엔드 5기 1~5주차 현실 100% 회고 (1+1=N)이 글에 대해서 - 요약팀스파르타에서 운영하는 항해 플러스 백엔드 5기 과정에 합류했습니다. 문제를 정의하고, 분석하며, 최적의 방식으로 해결하는 능력을 키우는 것이 개발자로서의 성장이upcurvewave.tistory.com 항해 플러스, 수료하다! ☘.. 2024. 8. 28.

티스토리툴바