728x90 반응형 전체 글267 [BOJ 6549] 히스토그램에서 가장 큰 직사각형 알고리즘 분류: 자료구조, 분할정복, 세그먼트트리, 스택 비슷한 문제: BOJ 1725, 히스토그램 이중 스택을 이용한 풀이가 잘 알려져 있고, 이 때의 시간복잡도는 O(2N)=O(N)이다. 핵심 아이디어 (1) 히스토그램의 높이가 증가할 때 까지 스택에 인덱스를 push 한다 (2) 히스토그램의 높이가 감소한다면 (2.1) 현대 인덱스는 i, 직전의 히스토그램의 인덱스는 stack.top 일 것 이다 (2.2) 스택이 비워질 때 까지 인덱스를 pop하면서 현재 넓이를 구한다 (2.3) 이때 width = (i - top - 1), height = H[stack.top] 이 된다 (3) 스택이 비어있지 않다면, 히스토그램의 마지막 부분이 증가하다가 끝난 경우이다 (3.1) (2)의 과정을 한 번 .. 2022. 11. 23. 기라성, 기라성 같은 OO 뉴스를 보다보면 '기라성 같은 ~'이란 표현을 가끔 만난다. 처음 이 단어를 보았을 땐 거물같은 느낌이라고 생각했는데 그 뜻을 찾아봤다 일본어 '키라키라'에서 음차한 단어라고 추정하는 것 같다 국립국어원 표준국어대사전 기라-성(綺羅星) 한자: 비단 기, 그물 라, 별 성 밤하늘에 반짝이는 무수한 별이라는 뜻으로, 신분이 높거나 권력이나 명예 따위를 가지고 있는 사람이 모여 있는 것을 비유적으로 이르는 말. 기라성 같은 선배. 이 학교 졸업생 가운데 국가 대표 선수가 기라성같이 많다. 각 분야의 전문가가 기라성처럼 한자리에 모였다. 국립국어원에서는, '기라성'이 일본어 투 단어이기 때문에 '빛나는 별'이라는 순화어를 사용하라고 한다. 왜 항상 순화어는 느낌이 좀 안살까... 신분, 권력, 명예와 관련되어있.. 2022. 11. 21. 테루아르, Terroir 이 글이 시작은... 요즘 만화카페에 가서 '신의 물방울'을 읽고있다. 역시 만화카페에서는 웹툰보다는 만화지 와인 용어가 프랑스어가 많다보니 만화를 보다가 멈춰서 뜻을 찾아보게된다 이 중 하나이 '테루아르'에 대해 포스팅한다 Terroir, 테루아르, 떼루아 독특한 환경, 농업 방식, 작물 서식지를 포함하여 작물의 형질에 영향을 주는 환경적 요인이다. 영어로는 land, soil이고, 우리말로는 풍토가 적절한 뜻일 것이다. 그러나 정확한 1:1 대응이 아니기에 영어권에서도 terroir(terˈwär) 라고 발음하여 프랑스어 그대로 사용하는 듯 하다. 실제 뜻은 와인의 장소감(a wine's sense of place)을 의미하는 단어이다. 기후는 포도가 자라는데에 직접적 요인이므로, 와인 역시 기후의 .. 2022. 11. 10. BOJ 10835 카드게임 https://www.acmicpc.net/problem/10835 10835번: 카드게임 첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오 www.acmicpc.net 그리디 알고리즘인가? - 항상 오른쪽 카드만 버릴수 있으면 정답인가? NO 플레이 가능한 동작은 3가지이다 (1) 왼쪽 카드만 버리기 (2) 왼쪽 카드와 오른쪽 카드 모두 버리기 (3) 오른쪽 카드만 버리기 (단, 오른쪽 카드의 숫자가 작아야 하고, 이때 득점이 가능하다) 만약 카드가 1장씩 남아있다면? 위의 (1) ~ (3) 연산을 if를 통해 점수를 얻을 수 있다. .. 2022. 11. 9. [C++] vector를 이용하여 그래프를 인접리스트로 구현하기 vector adj[10]; vector *adj = new vector[MAX_V]; // 개인적으로 좋아하는 표현 vector adjList(N, vector()); https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 이 문제로 그래프를 표현하면 int N, M; cin >> N >> M; vector* adj = new vector[N + 1]; for (int i = 0; i <.. 2022. 10. 1. BOJ 19238 스타트 택시 DFS/BFS 알고리즘과 시뮬레이션이 합쳐진 구현 문제이다. 세부조건이 까다로워서 처음부터 간결한 코드를 작성하는 것이 요구된다고 생각한다. 그래서 구조체 대신에 클래스를 이용하여 복잡한 변수를 초기화하고, 클래스의 연산자 오버로딩으로 정렬 우선순위를 재정의할 수 있었다. "알고리즘 경력이 많은 백준은 특정 위치로 이동할 때 항상 최단경로로만 이동한다." → BFS 알고리즘 이용 "백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다." → 우선순위를 정하면 1. 아직 도착지로 가지 못한 승객 2. 택시와의 최단거리가 가장 짧은 승객 3. 행 번호가 .. 2022. 9. 7. 이전 1 ··· 40 41 42 43 44 45 다음 728x90 반응형
