![]()
분류: 큐 / 문제 문제 링크 Given a string s, find the length of the longest substring without repeating characters. Example 1: Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. Example 2: Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1. Example 3: Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. No..
![]()
분류: 스택 / 문제 문제 링크 문제 설명 오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다. 이 역사적인 순간을 맞이하기 위해 줄에 서서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해졌다. 두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다. 줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람들이 서 있는 순서대로 입력이 주어진다. 출력 서로 볼 수 있는 쌍..
![]()
분류: 스택 / 문제 문제 링크 문제 설명 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다. i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다. 그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다. 예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우 = = = = - = = = = -> 관리인이 보는 방향 = - = = = = = = = = = 10 3 7 4 12 2 -> 빌딩의 높이 [1][2][3][4][5][6] -> 빌딩의 번호..
![]()
분류: 스택 / 문제 문제 링크 문제 설명 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다. 예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ...
![]()
분류: 스택(monotonic stack) / 문제 문제 링크 문제 설명 히스토그램에 대해서 알고 있는가? 히스토그램은 아래와 같은 막대그래프를 말한다. 각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다. 이러한 히스토그램의 내부에 가장 넓이가 큰 직사각형을 그리려고 한다. 아래 그림의 빗금 친 부분이 그 예이다. 이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야 한다. 주어진 히스토그램에 대해, 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하시오. 입력 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각..
![]()
분류: 스택(decreasing nomotonic stack) / 문제 문제 링크 문제 설명 KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑..
![]()
개요 따릉이는 서울시에서 운영하는 공유자전거 서비스입니다. 따릉이의 이용자 수는 매년 빠르게 증가하고 있고 2021년 기준 가입자 330만명, 이용건수 3천 300만건입니다. 이는 서울시 인구 1/3이에 해당하며 이러한 증가 추세에 맞춰 서울시는 따릉이 사업을 확대하고 있습니다. 또한 따릉이는 친환경 이동수단으로 대중교통과의 환승을 도입하는 등 사용이 장려되고있는 사업입니다. 하지만 이러한 정책적 지원과 별개로 따릉이 사용의 편의를 위한 서비스는 부족하다고 생각됩니다. 프로따릉러는 따릉이 전용 경로 추천 시스템입니다. 따릉이 대여소 정보를 제공하며 경로 탐색 시 출발지와 목적지 주변 대여소를 기반으로 경로를 추천해줍니다. 서비스는 이곳에서 이용할 수 있습니다. 문제 현재 사용자가 따릉이를 이용할 때 경로..
![]()
분류: 스택 / 문제 문제 링크 문제 설명 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다. 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라. 입력 첫 줄에 n ..
![]()
분류: 스택 배열 구현 ,STL stack / 문제 문제 링크 문제 설명 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 다섯 가지이다. push X: 정수 X를 스택에 넣는 연산이다. pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 스택에 들어있는 정수의 개수를 출력한다. empty: 스택이 비어있으면 1, 아니면 0을 출력한다. top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. 입력 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하..
![]()
분류: linked list, queue, cpp 배열 연결리스트 / 문제 문제 링크 문제 설명 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) 출력 예제와 같이..
![]()
분류: 배열 이용 시간복잡도 줄이기 스킬 / 문제 문제 링크 문제 설명 총 N개의 정수가 주어졌을 때, 정수 v가 몇 개인지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정수의 개수 N(1 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 정수가 공백으로 구분되어져있다. 셋째 줄에는 찾으려고 하는 정수 v가 주어진다. 입력으로 주어지는 정수와 v는 -100보다 크거나 같으며, 100보다 작거나 같다. 출력 첫째 줄에 입력으로 주어진 N개의 정수 중에 v가 몇 개인지 출력한다. 풀이 #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int N, v; int freq[201]={}; cin >> N;..
![]()
KaTeX Playground 블로그를 글에 수식을 적는 일이 많아 KaTeX를 자주 사용합니다. 매번 미리 보기로 확인하는 것이 번거로워 바로 수식을 확인할 수 있는 `KaTeX playground`를 제작했었습니다.(관련 글) 사용하면서 예전에 썼던 문법을 찾는 일이 잦았고 수식을 저장하는 기능을 추가 해야겠다는 생각이 들었습니다. 수식을 저장, 삭제, 복사하는 기능을 추가했고 저장한 수식을 URI를 통해 공유하는 기능도 추가했습니다. URI로 공유하기 때문에 다른 사람에게 보내기도 쉽고 URI만 클라우드에 적어두면 KaTeX Playground도 클라우드를 이용하는 것처럼 사용할 수 있습니다. 예시로 제가 작성한 수식을 공유하는 링크를 올려봅니다. 사이드바에서 저장되어 있는 수식을 확인해 보세요. ..
