문제 문제 바로가기> BOJ 1005번: ACM Craft 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 풀이 건물을 지을 때, 건설 순서 규칙이 존재하므로, 위상정렬을 이용해 문제를 풀었다. 내가 지어지기 이전에 지어져야 하는 건물들 중 가장 오랜 시간이 걸리는 건물 + 내가 지어지는 데 걸리는 시간이 정답이다. #include #include #include #define MAX 1005 using namespace std; int N; // 건물의 개수 int K; // 건물간의 건설순서 규칙의 ..

make SW 개발을 위해 유닉스 계열 운영체제에서 사용되는 프로그램 빌드 도구 어떤 파일들을 컴파일 하고, 어떤 방식으로 컴파일 할 지 직접 컴파일러에게 알려줘야 함 프로젝트의 크기가 커지고 파일들이 많아진다면 매번 명령어를 치기는 힘들어짐 이 문제를 해결하기 위해 리눅스에서는 make 라는 프로그램을 제공 make 프로그램은 Makefile을 읽어서 주어진 방식대로 명령어를 처리함 즉, make 명령어를 통해 make 프로그램은 Makefile을 읽고, 많은 수의 파일들을 명령어 한번으로 컴파일 할 수 있음 또한, Increment Build를 수행한다는 장점이 있음 (단순 shell script 작성과의 차이점) 💡 빌드(build) 컴파일 언어를 실행파일로 변환하는 과정 (컴파일 + 링크) > 컴..

문제 문제 바로가기> BOJ 1477번: 휴게소 세우기 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다. N = 0인 경우 둘째 줄은 빈 줄 www.acmicpc.net 풀이 M개의 휴게소를 가능한 빈 공간에 모두 세워보는 조합 방식으로는 너무 많은 경우의 수가 있다. 따라서 입력 받은 위치를 정렬하고, "각 휴게소 간 거리 중 최대값"으로 이분 탐색하여 문제를 해결하였다. ( + 거리이기 때문에 low 값을 0이 아닌 1로 설정하였다.) 문제를 풀기 전에 "예제 입력 1"을 손으로 그려보고 문제를 푸니, 문제를 금방 풀 수 있었던 거 같다. 문제를 이해하고, ..

문제 문제 바로가기> BOJ 2933번: 미네랄 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 풀이 옛날에 풀다가 때려쳤었는데,, 오랜만에 싹 지우고 다시 풀어봤다! 중력을 작용시키는 클러스터를 찾는 부분, 중력을 처리하는 부분만 주의해주면 된다! 클러스터가 지면에 닿아있지 않다면, 중력이 작용하는 클러스터이다! #include #include #include #define MAX 101 using namespace std; struct POS{int y, x;}; vector cluster; int R, C, N; ch..

문제 문제 바로가기> BOJ 2812번: 크게 만들기 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 큰 수를 만났을 때, 현재 수보다 작은 수가 앞에 있다면 해당 수를 지우기 위해 스택을 이용하였다! #include #include using namespace std; int N, K; string str; deque s; void input(){ cin >> N >> K; cin >> str; } void solve(){ // 숫자 K개를 지워서 얻을 수 있는 가장 큰 수 for(char c : str){ while(!s.empty() && s.back()

문제 문제 바로가기> 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..