문제 문제 바로가기> BOJ 6549번: 히스토그램에서 가장 큰 직사각형 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 풀이 스택을 이용하여 O(N)만에 정답을 구할 수 있다. 낮아지는 경우와 높아지는 경우로 구분하고, 낮아지는 경우에 pop한 idx를 현재 높이와 함께 다시 스택에 넣어주는 부분이 핵심인듯 하다!! #include #include #define MAX 100005 using namespace std; struct DATA{int id..

문제 문제 바로가기> BOJ 8980번: 택배 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 풀이 도착지를 기준으로 오름차순 정렬하여, 현재 보낼 수 있는 양의 최대치를 구 방식으로 문제를 풀었다! 그리디는 진짜 ,, 생각해내기가 쉽지 않다 ,, #include #include #include #define MAX 2001 using namespace std; struct PARCEL { int s, e, c; bool operator < (const PARCEL &p) const { i..

문제 문제 바로가기> BOJ 1963번: 소수 경로 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 풀이 두 소수 사이의 변환에 필요한 최소 회수를 구하는 것이므로 bfs를 이용하여 문제를 해결해주었다. #include #include #include #define MAX 10000 using namespace std; struct DATA{int num, cnt;}; int arr[4]; bool visited[MAX]; bool notPrime[MAX]; void eratosthenes(){ for (int a=2..

문제 문제 바로가기> BOJ 9935번: 문자열 폭발 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 풀이 문자열을 폭발시킬 때는 LIFO, 남은 문자열을 합칠때는 FIFO 자료구조가 용이하기에 deque를 사용했다. 문자열 폭발시 LIFO 자료구조를 이용하여 시간을 단축시킬 수 있는데, 그 이유는 가장 최신 폭발 문자열 개수만 보고 판단할 수 있고, stack 덕분에 문자열의 순서가 유지되기 때문이다. ( + stack 같은 자료구조의 유용성을 알 수 있는 좋은 문제같아서, 한번 풀어보면 좋을..

문제 농부 존은 그의 들판에 N(1≤N≤10,000)개의 건초 더미를 놓으려 한다. 들판은 1*1 크기의 사각형으로 구성된 100*100 크기이고, 건초 더미들은 각각 1*1 크기의 사각형 한 칸을 차지한다. (한 칸에 두 개의 건초 더미가 놓이는 일은 없다) 농부 존은 건초 더미로 연결된 다양한 형태의 하나의 큰 영역이 생기는 것을 알았다. 즉, 건초 더미들 모두 인접한 (동서남북으로 한 칸) 곳에 다른 건초 더미가 있다. 한 건초 더미에서 출발해서 다른 모든 건초 더미에 도달할 수 있다. 건초 더미로 연결된 영역은 “구멍”을 포함할수있다. 구멍은 건초 더미로 완전히 둘러싸인 빈 영역이다. 농부 존이 건초 베일에 의해 형성되는 영역의 둘레를 계산하는 것을 도와주시오. “구멍”은 둘레에 영향을 주지 않는..

문제 문제 바로가기> BOJ 2666번: 벽장문의 이동 2666번: 벽장문의 이동 첫 번째 줄에 벽장의 개수를 나타내는 3보다 크고 20보다 작거나 같은 하나의 정수, 두 번째 줄에 초기에 열려있는 두 개의 벽장을 나타내는 두 개의 정수, 그리고 세 번째 줄에는 사용할 벽장들 www.acmicpc.net 풀이 처음에는 3가지 케이스 별로 나누어서 풀었는데, right 보다 작은 경우는 left 문을 이용하고, left보다 작은 경우는 right 문을 이용하도록 하면 두개의 if문으로 코드를 줄일 수 있었다..! 밑에 그림을 참고하자 :) + 추가로 left와 right를 파라미터로 가지고 다니면, 원상태로 복원시켜줄 필요가 없어서 변수관리가 편리하다! #include #define MAX 25 using..

stringstream주어진 문자열에서 필요한 자료형의 데이터를 추출할 때 유용하게 사용 공백과 '\n'을 제외하고 문자열에서 맞는 자료형의 정보를 추출stream.str(string str): 현재 stream의 값을 문자열 str로 변환// swapping ostringstream objects #include // std::string #include // std::cout #include // std::stringstream int main () { std::stringstream ss; ss > bar; std::cout

문제 문제 바로가기> 정올 1169번: 주사위 던지기1 JUNGOL history 최근 본 문제 jungol.co.kr 풀이 각각 중복순열, 중복조합, 순열을 구현하는 문제이다. 오랜만에 풀어보니 약간 헷갈.. 렸다 ㅎㅎ 순열: 서로 다른 n개 중에서 r개를 선택하여 일렬로 세우는 경우 중복순열: 서로 다른 n개 중에서 중복을 허락하고 r개를 일렬로 나열하는 수 조합: 서로 다른 n개 중에서 r개를 선택하여 그룹을 만드는 경우 (순서 상관 x) 중복조합: 서로 다른 n개 중에서 순서를 생각하지 않고 중복을 허락하여 r개를 선택하는 경우 #include #define MAX 7 using namespace std; int N, M; int seq[MAX]; bool visited[MAX]; void inp..

문제 문제 바로가기> 정올 2097번: 지하철 JUNGOL history 최근 본 문제 jungol.co.kr 풀이 다익스트라를 이용하여 최소 시간을 구해주었다. 최단 경로의 경우, (최단 경로일 때만 경로 업데이트가 일어나므로) 경로가 업데이트 될 때 이전 역을 저장하고 역추적하는 방식으로 쉽게 구할 수 있다. #include #include #include #define MAX 105 #define INF 1000000001 #define pii pair using namespace std; int N, M; int cost[MAX]; // cost[k]: 1번역에서 k 역까지 가는데 걸리는 시간 int stopover[MAX]; // 경유지 저장 vector v[MAX]; void input(){ ..

RapidJSON SAX/DOM 스타일 API를 모두 갖춘 C++용 빠른 JSON parser/generator Install 별도의 설치는 필요하지 않다. git clone을 받은 후 include 폴더 내 rapidjson 폴더를 src 폴더와 같은 경로에 위치 시켜 사용할 수 있다. $ https://github.com/Tencent/rapidjson.git RapidJSON 사용 // 입력 JSON을 JSONx 형식으로 변환하는 command line tool // rapidjson/example/simpledom/simpledom.cpp` #include "rapidjson/document.h" #include "rapidjson/writer.h" #include "rapidjson/string..

문제 문제 바로가기> BOJ 10157번: 자리배정 10157번: 자리배정 첫 줄에는 공연장의 격자 크기를 나타내는 정수 C와 R이 하나의 공백을 사이에 두고 차례대로 주어진다. 두 값의 범위는 5 ≤ C, R ≤ 1,000이다. 그 다음 줄에는 어떤 관객의 대기번호 K가 주어진다. www.acmicpc.net 풀이 달팽이 모양을 그릴 수록 R, C 칸이 한칸씩 감소하는 성질을 이용하여 문제를 해결했다! #include #include #define pii pair using namespace std; int C, R, K; int dr[] = {1, 0, -1, 0}; // 상 우 하 좌 int dc[] = {0, 1, 0, -1}; void input(){ cin >> C >> ..

json-c JSON 객체를 C로 쉽게 구성하고 JSON 포맷된 문자열로 출력하여 JSON 포맷된 문자열을 다시 JSON 객체의 C 표현으로 파싱할 수 있는 reference counting object model을 구현하는 라이브러리 Install (e.g. Ubuntu 16.04.2 LTS) $ sudo apt install libjson-c-dev libjson-c3 $ vi src/main.cpp $ g++ src/main.cpp -ljson-c $ ./a.out // main.cpp #include #include using namespace std; int main(int argc, char **argv) { json_object *myobj, *dataobj; // 메모리 할당 myobj =..

문제 문제 바로가기> BOJ 8983번: 사냥꾼 8983번: 사냥꾼 입력의 첫 줄에는 사대의 수 M (1 ≤ M ≤ 100,000), 동물의 수 N (1 ≤ N ≤ 100,000), 사정거리 L (1 ≤ L ≤ 1,000,000,000)이 빈칸을 사이에 두고 주어진다. 두 번째 줄에는 사대의 위치를 나타내는 M개의 x-좌 www.acmicpc.net 풀이 중요한 포인트는 "사대를 기준으로 동물을 보는 것"이 아니라, "동물을 기준으로 사대를 보는 것"이다. 사대를 정렬해두고, 해당 동물을 잡을 수 있는 사대가 있는지 이분탐색을 이용하여 확인하면, MlogM(사대 정렬) + NlogN(나를 잡을 수 있는 사대 찾기) → O(MlogM) 만에 문제를 해결할 수 있다. #include #include #def..

문제 문제 바로가기> 정올 1141번: 불쾌한 날 JUNGOL history 최근 본 문제 jungol.co.kr 풀이 N이 최대 80,000이므로 각 소에 대해서 이중 for문을 돌면서 확인할 경우 시간초과가 발생한다. 내가 볼 수 있는 소의 수를 세는 것이 아니라, 나를 볼 수 있는 소의 수를 센다면, O(N)으로 문제를 해결할 수 있다. 다음과 같이 스택 안에 나(H[i])를 볼 수 있는 소들만 들어 있도록 유지하면 된다. (1번 소가 3번 소를 볼 수 있고, 3번 소가 4번 소를 볼 수있으면, 1번 소는 4번 소를 볼 수있다.) #include #include #define MAX 80001 using namespace std; int N; int H[MAX]; void input(){ cin >..

문제 개구리가 연못 위에서 놀고 있다. 개구리는 N개의 연 잎 들을 이용해서 이리저리 뛰어 놀고 있다. 개구리가 뛰는 장면을 보던 철수는 개구리가 도약을 하는 경우가 얼마나 있는지 궁금해졌다. 여기서 도약은 아래 조건을 만족하는 경우를 말한다. 1. 개구리가 뛴 거리가 이전에 뛴 거리 이상 뛰지만 그 2배보다 멀리 뛰지는 않는다. 2. 개구리는 오른쪽으로만 뛴다. 3. 개구리는 두 번만 뛴다. 4. 위 세 가지 조건을 만족한다면 어느 곳에서든 시작할 수 있다. 허나, 연 잎 들이 너무 많기 때문에 가능한 횟수가 매우 많아질 것 같다고 생각한 철수는, 개구리가 오른쪽으로 도약하는 경우가 얼마나 되는지 구해달라고 했다. 철수를 위해 프로그램을 짜주자. 첫 번째 줄에는 연 잎의 수 N(3 ≤ N ≤ 1,000..