oz9911의 등록된 링크

 oz9911로 등록된 네이버 블로그 포스트 수는 53건입니다.

[BOJ] Two Machines baekjoon 17528 DP [내부링크]

DP Two Machines https://www.acmicpc.net/problem/17528 17528번: Two Machines 17528번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 Two Machines 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 0.5 초 (추가 시간 없음) 512 MB 1352 537 385 46.330% 문제 스케줄링 최적화 회사인 SOPT 에 완료해야 할 n 개의 작업 t 1 , t 2 , ..., t n 이 있다. SOPT 회사는 두 대의 머신 A 와 B 를 보유하고 있다. 각 작업 t i 를 완료하기 위해 SOPT 는 머신 A 와 B 둘 중에 오직 하나를 선택할 수 있다. 작업 t i 를... www.acmicpc.net 문제 : 완료해야 할 n개의 작업 t1, t2, ..., tn 이 있다. 각 작업 ti를 완료하기 위해 SOPT 는 머신 A 와 B 둘 중에 오직 하나를 선택할 수 있다. 작업 ti를 완료하기

[BOJ] 단어 섞기 baekjoon 9177 DP [내부링크]

DP 단어 섞기 https://www.acmicpc.net/problem/9177 9177번: 단어 섞기 문제 세 개의 단어가 주어졌을때, 꿍은 첫 번째 단어와 두 번째 단어를 섞어서 세 번째 단어를 만들 수 있는지 궁금해졌다. 첫 번째와 두 번째 단어는 마음대로 섞어도 되지만 원래의 순서는 섞여서는 안 된다. 다음과 같은 경우를 생각해보자. 첫 번째 단어 : cat 두 번째 단어 : tree 세 번째 단어 : tcraete 보면 알 수 있듯이, 첫 번째 단어와 두 번째 단어를 서로 섞어서 세 번째 단어를 만들 수 있다. 아래와 같이 두 번째 예를 들어보자. 첫 번째 단어 : cat 두 번째 단어 : tree 세 번째 단어 : catr... www.acmicpc.net 문제에 대한 설명은 생략하고 제 풀이와 여러 방안에 대해 정리해봅니다. 방안 1 재귀로 작성 a와 b의 인덱스중에서 목표로 찾고자 하는 x의 index에 해당하는 문자와 같다면 그 인덱스가 맞다고 가정하고 x인덱스와

[BOJ] 앱 baekjoon 7579 DP [내부링크]

DP 앱 https://www.acmicpc.net/problem/7579 7579번: 앱 문제 우리는 스마트폰을 사용하면서 여러 가지 앱(App)을 실행하게 된다. 대개의 경우 화면에 보이는 ‘실행 중’인 앱은 하나뿐이지만 보이지 않는 상태로 많은 앱이 '활성화'되어 있다. 앱들이 활성화 되어 있다는 것은 화면에 보이지 않더라도 메인 메모리에 직전의 상태가 기록되어 있는 것을 말한다. 현재 실행 중이 아니더라도 이렇게 메모리에 남겨두는 이유는 사용자가 이전에 실행하던 앱을 다시 불러올 때에 직전의 상태를 메인 메모리로부터 읽어 들여 실행 준비를 빠르게 마치기 위해서이다. 하지만 스마트폰의 메모리는 제한적이기 때문에 한번... www.acmicpc.net dp의 대표문제인 배낭 문제와 유사한 문제인 듯하다. 유사하게 조건에 맞게 변경해서 구현해보았다. <문제 조건 & 구상> <코드> #include<iostream> using namespace std; typedef struct A

[BOJ] 돌 그룹 baekjoon 12886 BFS / Brute Force [내부링크]

Brute-Force / BFS 돌 그룹 https://www.acmicpc.net/problem/12886 12886번: 돌 그룹 12886번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 검색 돌 그룹 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 512 MB 9182 2847 1853 28.377% 문제 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 한다. 강호는 돌을 단계별로 움직이며, 각 단계는 다음과 같이 이루어져 있다. 크기가 같지 않은 두 그룹을 고른다. 그 다음, 돌의... www.acmicpc.net 문제 : 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 한다. 크기가 같지 않은 두 그룹을 고른다. 그 다음, 돌의 개수가 작은 쪽을 X, 큰 쪽

[BOJ] 과외맨 baekjoon 5213 BFS [내부링크]

BFS 과외맨 https://www.acmicpc.net/problem/5213 5213번: 과외맨 문제 과외맨은 평소에 서강대학교 학생 이민혁으로 위장하고 있는 한국의 대표적인 영웅이다. 그는 슈퍼 히어로가 너무 미국에 집중되어 있는 현실을 안타까워했고, 그의 절친한 친구인 스파이더맨과 아이언맨에게 한국으로 와서 같이 영웅 활동을 하자는 제안을 했으나 거절당했다. 얼마 전, 오랜 잠에서 깨어난 고대 마야인들이 과외맨이 수업을 듣는 동안 과외 노트를 훔쳐갔다. 과외맨은 빼앗긴 노트를 찾아오기 위해 인천 공항으로 가서 과테말라로 가는 비행기를 탔다. 일단 언어가 통하지 않기 때문에, 과외맨은 자신의 특기를 살려서 일주일간 과테말라에... www.acmicpc.net 문제 : 도미노 타일은 두 조각으로 나누어져 있었고, 각 조각은 정사각형이다. 조각에는 1과 6사이의 숫자가 써져 있다. 타일은 N줄로 놓여져 있고, 홀수 줄에는 N개의 타일이, 짝수 줄에는 N-1개의 타일이 놓여져 있다.

[BOJ] LCA 2 baekjoon 11438 LCA [내부링크]

LCA LCA 2 https://www.acmicpc.net/problem/11438 11438번: LCA 2 문제 N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다. 입력 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다. 출력 M개의 줄에 차례대로 입력받은... www.acmicpc.net 문제 : N개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지

[BOJ] 다각형의 면적 baekjoon 2166 CCW [내부링크]

CCW 다각형의 면적 https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 2166번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 검색 다각형의 면적 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 23175 6735 4956 27.605% 문제 2차원 평면상에 N(3 ≤ N ≤ 10,000)개의 점으로 이루어진 다각형이 있다. 이 다각형의 면적을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. 출력 첫째 줄에 면적을... www.acmicpc.net 문제 : 2차원 평면상에 N개의 점으로 이루어진 다각형이 있다. 이 다각형의 면적을 구하는 프로그램을 작성하시오. 제한 : (3 ≤ N ≤ 10,000),좌표값은 절댓값이 100,000을 넘지 않는 정수 메모

[BOJ] LCA와 쿼리 baekjoon 15480 LCA [내부링크]

LCA LCA와 쿼리 https://www.acmicpc.net/problem/15480 15480번: LCA와 쿼리 15480번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 검색 LCA와 쿼리 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 512 MB 1873 840 598 43.713% 문제 N개의 정점으로 이루어져 있는 트리 T가 주어졌을 때, 다음 쿼리를 수행하는 프로그램을 작성하시오. r u v : T의 루트가 r이라고 했을 때, u와 v의 LCA를 출력한다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리 T의 간선 정보 u와 v가 주어지다. u... www.acmicpc.net 문제 : N개의 정점으로 이루어져 있는 트리 T가 주어졌을 때, 다음 쿼리를 수행하는 프로그램을 작성하시오. r u v: T의 루트가 r이라고 했을 때, u와 v의 LCA를 출력한다. 제한 : N(1 ≤ N

[BOJ] 집합의 표현 baekjoon 1717 Union Find [내부링크]

Union - Find 집합의 표현 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 1717번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 검색 집합의 표현 스페셜 저지 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 69103 21866 13245 28.204% 문제 초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작성하시오. 입력 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,00... www.acmicpc.net 문제 : 초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

[BOJ] 최솟값 baekjoon 10868 Segment Tree [내부링크]

Segment Tree 최솟값 https://www.acmicpc.net/problem/10868 10868번: 최솟값 10868번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 검색 최솟값 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 256 MB 15147 7186 5097 50.716% 문제 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자. 여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야... www.acmicpc.net 문제 : N개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M개 주어졌을 때는 어려운 문제가 된다. 이

[BOJ] 구간 합 구하기 2 baekjoon 12886 Lazy Propagation [내부링크]

Lazy-Propagation / Segment Tree 구간 합 구하기 2 https://www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 10999번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 검색 구간 합 구하기 2 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 256 MB 18787 4616 2456 27.868% 문제 어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째부터 4번째 수에 6을 더하면 1, 2, 9, 10, 5가 되고, 여기서 2번째부터 5번째까지 합을 구하라고 한다면 26을 출력하면 되는 것이다. 그리고... www.acmicpc.net 문제 : 어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3

[BOJ] 찾기 baekjoon 1786 KMP [내부링크]

Kmp 찾기 https://www.acmicpc.net/problem/1786 1786번: 찾기 문제 워드프로세서 등을 사용하는 도중에 찾기 기능을 이용해 본 일이 있을 것이다. 이 기능을 여러분이 실제로 구현해 보도록 하자. 두 개의 문자열 P와 T에 대해, 문자열 P가 문자열 T 중간에 몇 번, 어느 위치에서 나타나는지 알아내는 문제를 '문자열 매칭'이라고 한다. 워드프로세서의 찾기 기능은 이 문자열 매칭 문제를 풀어주는 기능이라고 할 수 있다. 이때의 P는 패턴이라고 부르고 T는 텍스트라고 부른다. 편의상 T의 길이를 n, P의 길이를 m이라고 하자. 일반적으로, n ≥ m이라고 가정해도 무리가 없다. n<m이면 어차피... www.acmicpc.net 문제 : 너무 길어서 생략하겠습니다. 한마디로 두 문장 s,x를 주고 x가 s안에 어디 어디 나오는지 출력하시오 입니다 제한 : 첫째 줄에 문자열 T가, 둘째 줄에 문자열 P가 주어진다. T와 P의 길이 n, m은 1이상 100

[BOJ] LCS 2 baekjoon 9252 LCS [내부링크]

LCS LCS 2 https://www.acmicpc.net/problem/9252 9252번: LCS 2 9252번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 검색 LCS 2 스페셜 저지 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 0.1 초 ( 하단 참고 ) 256 MB 27591 9798 7553 38.204% 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. ... www.acmicpc.net 문제 : LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAP

[BOJ] 사탕상자 baekjoon 2243 Segment Tree [내부링크]

Segment Tree 사탕상자 https://www.acmicpc.net/problem/2243 2243번: 사탕상자 2243번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 검색 사탕상자 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 10401 3926 2674 37.951% 문제 수정이는 어린 동생을 달래기 위해서 사탕을 사용한다. 수정이는 평소에 여러 개의 사탕을 사서 사탕상자에 넣어두고, 동생이 말을 잘 들을 때면 그 안에서 사탕을 꺼내서 주곤 한다. 각각의 사탕은 그 맛의 좋고 나쁨이 1부터 1,000,000까지의 정수로 구분된다. 1이 가장 맛있는 사탕을 의미하며, 1,000,000은 가장 맛없는 ... www.acmicpc.net 문제 : 수정이는 평소에 여러 개의 사탕을 사서 사탕상자에 넣어두고,그 안에서 사탕을 꺼내서 주곤 한다. 각각의 사탕은 그 맛의 좋고 나쁨이 1부터 1,000,000까지의 정수로 구분된다. 1이 가장 맛

[BOJ] 정점들의 거리 baekjoon 1761 LCA [내부링크]

LCA 정점들의 거리 https://www.acmicpc.net/problem/1761 1761번: 정점들의 거리 1761번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 검색 정점들의 거리 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 10425 4171 2666 38.299% 문제 N(2 ≤ N ≤ 40,000)개의 정점으로 이루어진 트리가 주어지고 M(1 ≤ M ≤ 10,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. 입력 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 ... www.acmicpc.net 문제 : N개의 정점으로 이루어진 트리가 주어지고 M(1 ≤ M ≤ 10,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. 제한 : (2 ≤ N ≤ 40,000) 메모리 : 128MB

[BOJ] 합성함수와 쿼리 baekjoon 12886 Sparse Table [내부링크]

Sparse Table/LCA 합성함수와 쿼리 https://www.acmicpc.net/problem/17435 17435번: 합성함수와 쿼리 17435번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 검색 합성함수와 쿼리 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 512 MB 3714 2018 1340 52.673% 문제 함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 f n : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자. f 1 (x) = f(x) f n+1 (x) = f(f n (x)) 예를 들어 f 4 (1) = f(f(f(f(1))))이다. n과 x가 주어질 때 f n... www.acmicpc.net 문제 : 함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 fn : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자.

[BOJ] Cubeditor baekjoon 1701 KMP [내부링크]

KMP Cubeditor https://www.acmicpc.net/problem/1701 1701번: Cubeditor 문제 Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 끝에 새로운 에디터를 만들게 되었고, 그 에디터의 이름은 Cubeditor이다. 텍스트 에디터는 찾기 기능을 지원한다. 대부분의 에디터는 찾으려고 하는 문자열이 단 한 번만 나와도 찾는다. Cubelover는 이 기능은 Cubelang에 부적합하다고 생각했다. Cubelang에서 필요한 기능은 어떤 문자열... www.acmicpc.net 문제 : Cubelang에서 필요한 기능은 어떤 문자열 내에서 부분 문자열이 두 번 이상 나오는 문자열을 찾는 기능이다. 이때, 두 부분 문자열은 겹쳐도 된다. 문자열의 길이는 최대 5,000이고, 문

[BOJ] LCS 3 baekjoon 1958 LCS [내부링크]

LCS LCS 3 https://www.acmicpc.net/problem/1958 1958번: LCS 3 1958번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 검색 LCS 3 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 7182 3523 2812 50.376% 문제 문자열과 놀기를 세상에서 제일 좋아하는 영식이는 오늘도 문자열 2개의 LCS(Longest Common Subsequence)를 구하고 있었다. 어느 날 영식이는 조교들이 문자열 3개의 LCS를 구하는 것을 보았다. 영식이도 도전해 보았지만 실패하고 말았다. 이제 우리가 할 일은 다음과 같다. 영식이를 도와서 문자열 3개의 LCS를 구... www.acmicpc.net 문제 : 문자열 3개의 LCS 길이를 구하여라 제한 : 각 문자열 길이는 100보다 작거나 같다 메모리 : 128MB 시간 : 2초 구상 : 기본 LCS를 3차원으로 하면 될거 같다..! 혹시 LCS에 대해 잘 모르

[BOJ] Strongly Connected Component baekjoon 2150 SCC [내부링크]

SCC Strongly Connected Component https://www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 문제 방향 그래프가 주어졌을 때, 그 그래프를 SCC들로 나누는 프로그램을 작성하시오. 방향 그래프의 SCC는 우선 정점의 최대 부분집합이며, 그 부분집합에 들어있는 서로 다른 임의의 두 정점 u, v에 대해서 u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재하는 경우를 말한다. 예를 들어 위와 같은 그림을 보자. 이 그래프에서 SCC들은 {a, b, e}, {c, d}, {f, g}, {h} 가 있다. 물론 h에서 h로 가는 간선이 없는 경우에도 {h}는 SCC를 이룬다. 입력 첫째 줄에 두 정수 V(1 ≤ V ≤ 10... www.acmicpc.net 문제 : 방향 그래프가 주어졌을 때, 그 그래프를 SCC들로 나누는 프로그램을 작성하시오. 방향 그래프의 SCC는 우선 정점의 최대

[BOJ] 가톨릭대학교에서 워터슬라이드를?? baekjoon 18133 SCC / 위상정렬 [내부링크]

SCC / 위상 정렬 가톨릭대학교에서 워터슬라이드를? https://www.acmicpc.net/problem/18133 18133번: 가톨릭대학교에 워터 슬라이드를?? 문제 치삼이는 축제를 맞아 가톨릭대학교에 건물 옥상에서 다른 건물 옥상으로 이동하는 워터 슬라이드를 짓기로 했다! 가톨릭대학교의 건물은 총 N 개로 이루어져 있으며, 편의상 1번 건물부터 N 번 건물까지 있다고 하자. 이 건물들의 옥상과 옥상 사이에 터널이 설치되어 있다면 터널을 따라 연결된 건물 옥상으로 물이 흐른다. 단 터널은 방향이 정해져 있어 주어진 방향으로만 물이 흐를 수 있으며, 이동할 수 있는 모든 건물 옥상으로 물이 흐른다. 예를 들어 1에서 2번으로 향하는 터널이 있고, 2에서 3번으로 향하는 터널이 있다면, ... www.acmicpc.net 문제 : 가톨릭대학교의 건물은 총 N 개로 이루어져 있으며, 편의상 1번 건물부터 N 번 건물까지 있다고 하자. 이 건물들의 옥상과 옥상 사이에 터널이 설치되

[BOJ] 구간 곱 구하기 baekjoon 11505 Segment Tree [내부링크]

Segment Tree 구간 곱 구하기 https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 문제 어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 곱을 구하려 한다. 만약에 1, 2, 3, 4, 5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 곱을 구하라고 한다면 240을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 곱을 구하라고 한다면 48이 될 것이다. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은... www.acmicpc.net 문제 : 첫째 줄에 수의 개수 N과 M, K 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주

[BOJ] K번째 괄호 문자열 baekjoon 17428 DP [내부링크]

DP K번째 괄호 문자열 https://www.acmicpc.net/problem/17428 17428번: K번째 괄호 문자열 문제 괄호 문자열은 다음과 같이 정의한다. 빈 문자열은 괄호 문자열이다. S가 괄호 문자열일 때, (S)도 괄호 문자열이다. S와 T가 괄호 문자열이라면, ST도 괄호 문자열이다. 모든 괄호 문자열은 위의 3개 규칙으로만 만들 수 있다. 길이가 N인 괄호 문자열 중에 사전순으로 K번째인 문자열을 출력하는 프로그램을 작성하시오. 사전순으로 가장 앞서는 괄호 문자열은 0번째이다. ‘(‘가 ‘)’보다 사전순으로 앞선다. 입력 첫째 줄에 자연수 N과 K가 주어진다. 출력 첫째 줄에 K번째 괄호 문자열을 출력한다. K번째 괄호 문자열이 없는... www.acmicpc.net 문제 : 괄호 문자열은 다음과 같이 정의한다. 빈 문자열은 괄호 문자열이다. S가 괄호 문자열일 때, (S)도 괄호 문자열이다. S와 T가 괄호 문자열이라면, ST도 괄호 문자열이다. 모든 괄호

[BOJ] 최소비용 구하기 2 baekjoon 11779 Dijkstra [내부링크]

Dijkstra 최소비용 구하기 2 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 11779번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 검색 최소비용 구하기 2 스페셜 저지 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 256 MB 20030 7346 5135 36.600% 문제 n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라.... www.acmicpc.net 문제 : n개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한

[BOJ] 선분 교차 1 baekjoon 17386 CCW [내부링크]

CCW 선분 교차 1 https://www.acmicpc.net/problem/17386 17386번: 선분 교차 1 17386번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 선분 교차 1 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 0.25 초 (추가 시간 없음) 512 MB 7654 2816 2040 35.522% 문제 2차원 좌표 평면 위의 두 선분 L 1 , L 2 가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. L 1 의 양 끝 점은 (x 1 , y 1 ), (x 2 , y 2 ), L 2 의 양 끝 점은 (x 3 , y 3 ), (x 4 , y 4 )이다. 입력 첫째 줄에 L 1 의 양 끝 점 x ... www.acmicpc.net 문제 : 2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (

[BOJ] 운동 baekjoon 1956 Floyd-Warshall [내부링크]

Floyd-Warshall 운동 https://www.acmicpc.net/problem/1956 1956번: 운동 1956번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 운동 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 192 MB 15719 6232 4611 40.712% 문제 V개의 마을와 E개의 도로로 구성되어 있는 도시가 있다. 도로는 마을과 마을 사이에 놓여 있으며, 일방 통행 도로이다. 마을에는 편의상 1번부터 V번까지 번호가 매겨져 있다고 하자. 당신은 도로를 따라 운동을 하기 위한 경로를 찾으려고 한다. 운동을 한 후에는 다시 시작점으로 돌아오는 것이 좋기 때문에, 우리는 사이클을 찾기를 원한... www.acmicpc.net 문제 : V개의 마을와 E개의 도로로 구성되어 있는 도시가 있다. 도로는 마을과 마을 사이에 놓여 있으며, 일방 통행 도로이다. 마을에는 편의상 1번부터 V번까지 번호가 매겨져 있다고 하자. 사이클을 이루는

[BOJ] 이항 계수 3 baekjoon 12886 수학(페르마의 소정리) [내부링크]

수학 (페르마의 소정리) 이항 계수 3 https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 11401번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 이항 계수 3 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 256 MB 20778 7642 5593 40.783% 문제 자연수 N \(N\) 과 정수 K \(K\) 가 주어졌을 때 이항 계수 ( N K ) \(\binom{N}{K}\) 를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N \(N\) 과 K \(K\) 가 주어진다. (1 ≤ N \(N\) ≤ 4,000,000, 0 ≤ K \(K\) ... www.acmicpc.net 문제 : 자연수 N과 정수 K가 주어졌을 때 이항 계수 (NK)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 성성하시오. 제한 : (1 ≤ N ≤ 4,000,000, 0

[BOJ] 최솟값 찾기 baekjoon 11003 Dequeue/ Priority-Queue [내부링크]

Dequeue/Priority-Queue 최솟값 찾기 https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 11003번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 검색 최솟값 찾기 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2.4 초 ( 하단 참고 ) 512 MB 20807 5980 3770 29.025% 문제 N개의 수 A 1 , A 2 , ..., A N 과 L이 주어진다. D i = A i-L+1 ~ A i 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 A i 는 무시하고 D를 구해야 한다. 입력 첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,0... www.acmicpc.net 문제 : N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이

[BOJ] 가장 긴 증가하는 부분 수열 3 baekjoon 12738 DP [내부링크]

DP 가장 긴 증가하는 부분 수열 3 https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 12738번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 가장 긴 증가하는 부분 수열 3 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 3 초 512 MB 10140 5744 4675 62.467% 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = { 10 , 20 , 10, 30 , 20, 50 } 이고, 길이는 4이다. 입력 첫째 줄에 수... www.acmicpc.net 문제 : 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에

[BOJ] 히스토그램 baekjoon 12886 Segment Tree [내부링크]

Segment Tree 히스토그램 https://www.acmicpc.net/problem/1725 1725번: 히스토그램 문제 히스토그램에 대해서 알고 있는가? 히스토그램은 아래와 같은 막대그래프를 말한다. 각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다. 이러한 히스토그램의 내부에 가장 넓이가 큰 직사각형을 그리려고 한다. 아래 그림의 빗금 친 부분이 그 예이다. 이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야 한다. 주어진 히스토그램에 대해, 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하시오. 입력 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. ... www.acmicpc.net 문제 : 히스토그램에 대해서 알고 있는가? 히스토그램은 아래와 같은 막대그래프를 말한다. 각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 2 1 4 5 1 3 3

[BOJ] 구간 합 구하기 3 baekjoon 11658 다차원 세그먼트 트리 [내부링크]

다차원 세그먼트 트리 구간 합 구하기 3 https://www.acmicpc.net/problem/11658 11658번: 구간 합 구하기 3 문제 N×N개의 수가 N×N 크기의 표에 채워져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 표의 i행 j열은 (i, j)로 나타낸다. 예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이 된다. (2, 3)을 7로 바꾸고 (2, 2)부터 (3, 4)까지 합을 구하면 3+7+5+4+5+6=30 이 된다. 표에 채워져 있는 ... www.acmicpc.net 문제 : N×N개의 수가 N×N 크기의 표, 표의 i행 j열은 (i, j)로 나타낸다. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 여기서 (2, 2)부터 (3, 4)

[BOJ] 가장 가까운 두 점 baekjoon 2261 Line Sweep / 분할 정복 [내부링크]

Line Sweep / 분할 정복 가장 가까운 두 점 https://www.acmicpc.net/problem/2261 2261번: 가장 가까운 두 점 2261번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 가장 가까운 두 점 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 256 MB 37082 6336 3253 16.064% 문제 2차원 평면상에 n개의 점이 주어졌을 때, 이 점들 중 가장 가까운 두 점을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를... www.acmicpc.net 문제 : 2차원 평면상에 n개의 점이 주어졌을 때, 이 점들 중 가장 가까운 두 점을 구하는 프로그램을 작성하시오. 제한 : n(2 ≤ n ≤ 100,000), 각 좌표

[BOJ] 북서풍 baekjoon 5419 Segment Tree [내부링크]

Segment Tree 북서풍 https://www.acmicpc.net/problem/5419 5419번: 북서풍 5419번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 북서풍 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 256 MB 5850 1958 1254 34.244% 문제 강한 북서풍이 불고 있다. 이 뜻은 동쪽과 남쪽 사이의 모든 방향으로 항해할 수 있다는 뜻이다. 북쪽이나 서쪽으로 항해하는 것은 불가능하다. 작은 섬이 여러 개 있는 바다가 있다. 섬은 좌표 평면의 한 점으로 나타낼 수 있다. y 좌표가 증가하는 방향은 북쪽, x좌표가 증가하는 방향은 동쪽이다. 북서풍을 타고 항해할 수 있는 섬의... www.acmicpc.net 문제 : 동쪽과 남쪽 사이의 모든 방향으로 항해할 수 있다는 뜻이다. 북쪽이나 서쪽으로 항해하는 것은 불가능하다. y 좌표가 증가하는 방향은 북쪽, x좌표가 증가하는 방향은 동쪽이다. 북서풍을 타고 항해할

[BOJ] 여우가 정보섬에 올라온 이유 baekjoon 17131 Segment Tree [내부링크]

Segment Tree 여우가 정보섬에 올라온 이유 https://www.acmicpc.net/problem/17131 17131번: 여우가 정보섬에 올라온 이유 문제 여우가 정보섬에 올라왔다! 오늘도 하늘에는 아름다운 별들이 빛나고 있다. 정보섬은 언덕 꼭대기에 위치해 있기 때문에 별이 잘 보이기로 유명하다. 그래서인지, 여우 한 마리가 정보섬에 올라와 밤하늘을 바라보며 별자리를 만들고 있다. 여우는 세 개의 별을 연결하여 V형 별자리를 만드는데, 그 이유는 V가 자신의 얼굴과 닮았기 때문이라나 뭐라나. 여우는 자신의 시점을 기준으로 생각하기 때문에, V가 회전한 모양(<, >, ㄴ, ㄱ, ^ 등)은 V라고 생각하지 않는다. 여우는 만들 수 있는 V형 별자리의 총 개수가 궁금해졌다. 그러나... www.acmicpc.net 문제 : 직교좌표계에서 세점으로 이루어진 V모양의 개수를 구하라 V형 별자리를 명확하게 정의하면 다음과 같다. 세 별 (s,t,u)가 s.x < t.x < u.

[BOJ] 줄 세우기 baekjoon 2465 Segment Tree [내부링크]

Segment Tree 줄 세우기 https://www.acmicpc.net/problem/2465 2465번: 줄 세우기 문제 N명의 사람들이 어떤 공연장에 입장하기 위해서 한 줄로 서 있다. 줄 서 있는 각 사람은 자기 앞에 서 있는 사람들 중에서 자기보다 키가 작거나 같은 사람들의 수를 알고 있다. 그러면, 이 수들을 표시하는 수열을 S라고 한다. N명의 키 집합과 수열 S가 주어질 때, 원래 줄 서 있는 키 순서를 정확히 찾아내는 프로그램을 작성하시오. 예를 들어서, 사람들의 키 집합이 다음과 같이 주어진다 (여기서, 같은 키의 사람들이 여러 명 존재할 수 있어서 중복이 포함된다). {120, 167, 163, 172, 145, 134, 18... www.acmicpc.net 문제 : 줄 서 있는 각 사람은 자기 앞에 서 있는 사람들 중에서 자기보다 키가 작거나 같은 사람들의 수를 알고 있다. 그러면, 이 수들을 표시하는 수열을 S라고 한다. N명의 키 집합과 수열 S가 주어

[BOJ] 공항 baekjoon 10775 Union Find [내부링크]

Union Find / Greedy 공항 https://www.acmicpc.net/problem/10775 10775번: 공항 문제 오늘은 신승원의 생일이다. 박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다. 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다. 공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 g i (1 ≤ g i ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다. 신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 ... www.acmicpc.net 문제 : 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다. 공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤

[BOJ] 굉장한 학생 baekjoon 2336 Segment Tree [내부링크]

Segment Tree 굉장한 학생 https://www.acmicpc.net/problem/2336 2336번: 굉장한 학생 2336번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 굉장한 학생 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 192 MB 3608 1599 1157 43.382% 문제 N명의 학생이 참여하여 세 번의 시험을 치렀다. N명의 학생들은 세 번의 시험에 모두 응시하였다. 조교는 각각의 시험에서 같은 등수의 학생이 한 명도 없도록 성적을 매겼다. A라는 학생이 B라는 학생보다 세 번의 시험에서 모두 성적이 좋다면, A가 B보다 '대단하다'고 한다. 또, C라는 학생보다 '대단한' 학생이 한 ... www.acmicpc.net 문제 : A라는 학생이 B라는 학생보다 세 번의 시험에서 모두 성적이 좋다면, A가 B보다 '대단하다'고 한다. 또, C라는 학생보다 '대단한' 학생이 한 명도 없으면, C를 '굉장하다'고 한다.

[BOJ] 선분 교차 2 baekjoon 17387 CCW [내부링크]

CCW 선분 교차 2 https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 문제 2차원 좌표 평면 위의 두 선분 L 1 , L 2 가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다. L 1 의 양 끝 점은 (x 1 , y 1 ), (x 2 , y 2 ), L 2 의 양 끝 점은 (x 3 , y 3 ), (x 4 , y 4 )이다. 입력 첫째 줄에 L 1 의 양 끝 점 x 1 , y 1 , x 2 , y 2 가, 둘째 줄에 L 2 의 양 끝 점 x 3 , y 3 , x 4 , y 4 가 주어진다. 출력 L 1 과 L 2 가 교차... www.acmicpc.net 문제 : 2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다. L1의 양 끝 점은

[BOJ] N수매화검법 baekjoon 25315 CCW [내부링크]

CCW N수매화검법 https://www.acmicpc.net/problem/25315 25315번: N수매화검법 25315번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 N수매화검법 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 (추가 시간 없음) 1024 MB (추가 메모리 없음) 688 277 227 45.129% 문제 화산파의 장로 우경은 새로운 무공 N수매화검법 을 창안했다. N수매화검법은 이십사수매화검법을 발전시킨 검법으로 총 N $N$ 개의 베기 (검으로 무언가를 베는 동작) 로 이루어진다. N수매화검법은 2차원 평면 상에서 펼치는 검법으로, 베기 i $i$ 는 점 s i $s_i$ 에서 시작해 e i... www.acmicpc.net 문제 : 화산파의 장로 우경은 새로운 무공 N수매화검법을 창안했다. N수매화검법은 2차원 평면 상에서 펼치는 검법으로, 베기 i는 점 si에서 시작해 ei까지를 일직선으로 벤다. 이때 검이 지나는 경로를 베기

[BOJ] 당근 밭 baekjoon 23239 기하학 [내부링크]

기하학 당근 밭 https://www.acmicpc.net/problem/23239 23239번: 당근 밭 문제 무한히 넓은 당근 밭 가운데 x $x$ , y $y$ 축으로 수평인 직사각형 마구간이 있다. 그림 B.1 의 왼쪽 그림처럼 마구간의 왼쪽 아래 모서리 기둥에 말이 묶여 있고, 마구간의 네 모서리는 모두 격자점에 있다. 상하좌우로 인접한 두 격자점 사이의 간격은 1 $1$ 이다. 말을 묶은 줄의 길이는 L $L$ 로 유한하다. 그리고 당근 밭의 모든 격자점마다 하나씩 당근이 심어져 있다. 그리고 말을 묶은 줄이 닿을 수 있는 거리 안에 심어진 당근은 말이 모두 먹을 수 있다고 가정한다. 만일 마구간의 크기가 11 × 6이고 묶은... www.acmicpc.net 문제 : 무한히 넓은 당근 밭 가운데 x, y 축으로 수평인 직사각형 마구간이 있다. 그림 B.1 의 왼쪽 그림처럼 마구간의 왼쪽 아래 모서리 기둥에 말이 묶여 있고, 마구간의 네 모서리는 모두 격자점에 있다. 상하

[BOJ] 볼록 껍질 baekjoon 1708 Convex Hull / 기하학 [내부링크]

Convex Hull / 기하학 볼록 껍질 https://www.acmicpc.net/problem/1708 1708번: 볼록 껍질 문제 다각형의 임의의 두 꼭짓점을 연결하는 선분이 항상 다각형 내부에 존재하는 다각형을 볼록 다각형이라고 한다. 아래 그림에서 (a)는 볼록 다각형이며, (b)는 볼록 다각형이 아니다. 조금만 생각해 보면 다각형의 모든 내각이 180도 이하일 때 볼록 다각형이 된다는 것을 알 수 있다. 편의상 이 문제에서는 180도 미만인 경우만을 볼록 다각형으로 한정하도록 한다. 2차원 평면에 N개의 점이 주어졌을 때, 이들 중 몇 개의 점을 골라 볼록 다각형을 만드는데, 나머지 모든 점을 내부에 포함하도록 할 수 있다. 이를 볼록 껍질 (CON... www.acmicpc.net 문제 : 다각형의 임의의 두 꼭짓점을 연결하는 선분이 항상 다각형 내부에 존재하는 다각형을 볼록 다각형이라고 한다. 아래 그림에서 (a)는 볼록 다각형이며, (b)는 볼록 다각형이 아니다.

[BOJ] 선분 교차 3 baekjoon 20149 CCW [내부링크]

Brute-Force / BFS 선분 교차 3 https://www.acmicpc.net/problem/20149 20149번: 선분 교차 3 문제 2차원 좌표 평면 위의 두 선분 L 1 , L 2 가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다. L 1 의 양 끝 점은 (x 1 , y 1 ), (x 2 , y 2 ), L 2 의 양 끝 점은 (x 3 , y 3 ), (x 4 , y 4 )이다. 입력 첫째 줄에 L 1 의 양 끝 점 x 1 , y 1 , x 2 , y 2 가, 둘째 줄에 L 2 의 양 끝 점 x 3 , y 3 , x 4 , y 4 가 주어진다. 출력 L 1 과 L 2 가 교차... www.acmicpc.net 문제 : 2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이

[BOJ] 단순 다각형 baekjoon 3679 기하학 / CCW [내부링크]

기하학 / CCW 단순 다각형 https://www.acmicpc.net/problem/3679 3679번: 단순 다각형 3679번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 단순 다각형 스페셜 저지 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 2573 620 498 24.000% 문제 평면 위의 점의 집합이 주어졌을 때, 다각형을 만드는 프로그램을 작성하시오. 집합의 모든 점은 다각형의 꼭짓점이어야 하고, 집합에 없는 점을 다각형의 꼭짓점으로 가질 수 없다. 다각형의 두 선분은 연속하는 두 선분의 교점을 제외하고는 교차할 수 없다. 예를 들어, 왼쪽 그림의 점으로 만든 다각형은 오른쪽과 같다. 항... www.acmicpc.net 문제 : 평면 위의 점의 집합이 주어졌을 때, 다각형을 만드는 프로그램을 작성하시오. 집합의 모든 점은 다각형의 꼭짓점이어야 하고, 집합에 없는 점을 다각형의 꼭짓점으로 가질 수 없다. 다각형의 두 선

[BOJ] PIZZA ALVOLOC baekjoon 12781 CCW [내부링크]

CCW PIZZA ALVOLOC https://www.acmicpc.net/problem/12781 12781번: PIZZA ALVOLOC 문제 도윤이는 친구 3명과 함께 시험이 끝난 기념으로 도윤이의 집에서 놀기로 했다. 갑자기 배가 고파진 도윤이는 근처 맛 집인 PIZZA ALVOLOC에서 피자를 시켜먹기로 했다. 이 곳의 피자는 특이하게도, 보통 피자와 다르게 피자의 모양이 항상 볼록 다각형이다. 도윤이와 친구들은 피자를 네 등분해서 나눠먹기로 했다. 어떻게 나눌지 고민을 하던 중에 도윤이는 피자를 다음과 같이 나누기로 했다. 한 명씩 피자의 가장자리의 한 점을 선택한다. (같은 점을 선택하지 않는다.) 선택한 순서대로 첫 번째 점과 두 번째 점을 이어 선분을 만... www.acmicpc.net 문제 : 도윤이와 친구들은 피자를 네 등분해서 나눠먹기로 했다. 어떻게 나눌지 고민을 하던 중에 도윤이는 피자를 다음과 같이 나누기로 했다. 한 명씩 피자의 가장자리의 한 점을 선택한

[BOJ] 선분 그룹 baekjoon 2162 CCW / Union Find [내부링크]

CCW / Union-Find 선분 그룹 https://www.acmicpc.net/problem/2162 2162번: 선분 그룹 2162번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 선분 그룹 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 11764 3295 2134 26.365% 문제 N개의 선분들이 2차원 평면상에 주어져 있다. 선분은 양 끝점의 x, y 좌표로 표현이 된다. 두 선분이 서로 만나는 경우에, 두 선분은 같은 그룹에 속한다고 정의하며, 그룹의 크기는 그 그룹에 속한 선분의 개수로 정의한다. 두 선분이 만난다는 것은 선분의 끝점을 스치듯이 만나는 경우도 포함하는 것으로 한다. N개의 선분들이 주어졌... www.acmicpc.net 문제 : N개의 선분들이 2차원 평면상에 주어져 있다. 선분은 양 끝점의 x, y 좌표로 표현이 된다. 두 선분이 서로 만나는 경우에, 두 선분은 같은 그룹에 속한다고 정의하며, 그룹의 크기는

[BOJ] 증가 수열의 개수 baekjoon 17409 DP/Segment Tree [내부링크]

DP / Segment Tree 증가 수열의 개수 https://www.acmicpc.net/problem/17409 17409번: 증가 수열의 개수 입력 첫째 줄에 N, K가 주어진다. 둘째 줄에 수열 A 1 , A 2 , ..., A N 이 주어진다. 출력 첫째 줄에 A의 증가하는 부분 수열 중에서 길이가 K인 것의 개수를 10 9 +7로 나눈 나머지를 출력한다. 제한 1 ≤ N ≤ 100,000 1 ≤ K ≤ 10 1 ≤ A i ≤ N A i 는 모두 다른 수 예제 입력 1 복사 5 1 1 2 3 5 4 예제 출력 1 복사 5 예제 입력 2 복사 5 2 1 2 3 5 4 예제 출력 2 복사 9 예제 입력 3 복사 5 3 1 2 3 5 4 예제 출력 3 복사 7 예제 입력 4 www.acmicpc.net 문제 : 크기가 N인 수열 A와 정수 K가 주어졌을 때, A의 증가하는 부분 수열 중에서 길이가 K인 것의 개수를 구해보자. 개수를 109+7로 나눈 나머지를 출력한다. 제한 :

[BOJ] 최소 스패닝 트리 baekjoon 1197 Minimum Spanning Tree [내부링크]

MST 최소 스패닝 트리 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 1197번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 최소 스패닝 트리 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 59461 25143 14136 40.413% 문제 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가... www.acmicpc.net 문제 : 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인

[BOJ] 행성 터널 baekjoon 2887 MST [내부링크]

MST 행성 터널 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 2887번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 행성 터널 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 18697 6857 4790 34.946% 문제 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. 행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(x A , y A , z A )와 B(x B , y B , z B )를 터널로... www.acmicpc.net 문제 : 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. 행성은 3차원 좌표위

[BOJ] 확장 게임 baekjoon 16920 BFS [내부링크]

BFS 확장 게임 https://www.acmicpc.net/problem/16920 16920번: 확장 게임 문제 구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위에 있다. 한 칸 위에 성이 두 개 이상인 경우는 없다. 게임은 라운드로 이루어져 있고, 각 라운드마다 플레이어는 자기 턴이 돌아올 때마다 성을 확장해야 한다. 제일 먼저 플레이어 1이 확장을 하고, 그 다음 플레이어 2가 확장을 하고, 이런 식으로 라운드가 진행된다. 각 턴이 돌아왔을 때, 플레이어는 자신이 가지고 있는 성을 비어있는 칸... www.acmicpc.net 문제 : 구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위에 있다.

[BOJ] 해킹 baekjoon 10282 Dijkstra [내부링크]

Dijkstra 해킹 https://www.acmicpc.net/problem/10282 10282번: 해킹 10282번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 해킹 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 256 MB 11229 4543 3236 39.129% 문제 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다. 최흉최악의 해커 yum... www.acmicpc.net 문제 : 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일

[BOJ] 도서관 baekjoon 1461 Greedy [내부링크]

Greedy 도서관 https://www.acmicpc.net/problem/1461 1461번: 도서관 1461번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 도서관 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 7092 3252 2630 45.843% 문제 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 계산하는 프로그램을 작성하시오. 세준이는 한 걸음에 좌표 1칸씩 가... www.acmicpc.net 문제 : 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책들의 원래 위치가

[BOJ] 맹독 방벽 baekjoon 7420 Convex Hull / 기하학 [내부링크]

Convex Hull / 기하학 맹독 방벽 https://www.acmicpc.net/problem/7420 7420번: 맹독 방벽 7420번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 맹독 방벽 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 1595 633 510 39.051% 문제 화학 제국의 왕 성준이는 계속되는 이웃나라의 침범으로부터 자유로워지기 위해 자국의 자랑 화학 방벽 을 건설하기로 마음먹었다. 이 방벽은 근처에 다가오는 생명체에게 해로운 독성을 내뿜어서 더이상 다른 나라들이 얼씬도 못하게 만들 것이다! 그러나 이 방벽은 만들기 까다롭기에 가능한 한 적게 지어야 하며, 자국민들에게도 악영향을 끼칠 ... www.acmicpc.net 문제 : 화학 제국의 왕 성준이는 계속되는 이웃나라의 침범으로부터 자유로워지기 위해 자국의 자랑 화학 방벽을 건설하기로 마음먹었다. 이 방벽은 근처에 다가오는 생명체에게 해로운 독성을 내뿜어

[BOJ] 환상의 듀엣 baekjoon 11570 DP [내부링크]

DP 환상의 듀엣 https://www.acmicpc.net/problem/11570 11570번: 환상의 듀엣 11570번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 환상의 듀엣 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 256 MB 1013 539 431 58.880% 문제 상덕이와 희원이는 소문난 환상의 듀엣으로, 노래방에 가서 노래를 자주 부르곤 한다. 어느 날 상덕이는 백준이에게 선물 받은 악보를 가져왔다. 악보에는 그 노래를 표현하는데 필요한 음의 높이가 순서대로 N개 적혀져 있었다. 둘은 악보에 적혀 있는 모든 음들을 노래해야 하며, 각 음은 둘 중 한 사람에 의해서만 불러져야 한다. 예를 들어... www.acmicpc.net 문제 : 상덕이와 희원이는 소문난 환상의 듀엣으로, 노래방에 가서 노래를 자주 부르곤 한다. 어느 날 상덕이는 백준이에게 선물 받은 악보를 가져왔다. 악보에는 그 노래를 표현하는데 필요한 음의 높이가 순서대로

[BOJ] 나무 위의 입자 baekjoon 15669 DP [내부링크]

DP 나무 위의 입자 https://www.acmicpc.net/problem/15669 15669번: 나무 위의 입자 문제 트리란, 사이클이 없는 연결 그래프를 의미한다. 위 그림은 트리 모양의 입자가속기와 그 위의 어떤 정점에 놓인 특별한 입자 하나를 표시하고 있다. RB 입자라고 불리는 이 특이한 입자는 안정한 상태에서는 빨간색이지만, 불안정해질 경우 1초마다 색이 변하게 된다. 만일 빨간색이었다면 검은색이 되며, 검은색이었다면 빨간색으로 변하게 된다. 택희는 이 입자에 대한 간단한 실험을 해보려 한다. 우선 가속기 내에서 입자의 시작 정점과 끝 정점을 정해, 안정한 입자를 하나 꺼낸 뒤 불안정한 상태로 만들어 시작 지점에 놓는다. 이 과정에 ... www.acmicpc.net 문제 : <문제요약> 한칸 이동할때마다 색이 바뀐다. 빨 -> 검 -> 빨... 트리를 먼저 주어준다. M번의 쿼리동안 시작점에서 도착점까지 가는데 반드시 지나는 점 U,V를 준다. U->V로 가는 U,