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

문제 문제 바로가기> BOJ 1079번: 쇠막대기 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 풀이 닫는 괄호 ')' 일 경우 두 가지 경우가 있다. 1. 쇠막대기의 끝인 경우: 자신(조각)을 정답에 더해준다 (+1) 2. 레이저의 끝인 경우 = 이전 문자가 '(': 이때까지 쌓인 쇠막대기 개수만큼 정답에 더해준다 (+siz) #include using namespace std; string str; void input(){ cin >> str; } void solution(){ int ans=0, siz=0; for..

Shell운영체제 상에서 사용자가 입력하는 명령을 읽고 해석하여 대신 실행해주는 프로그램운영체제의 커널과 사용자를 이어주는 역할사용자의 명령어를 해석하고 운영체제가 알아들을 수 있도록 도와주는 명령어 해석기 Shell ScriptShell에서 사용할 수 있는 명령어들의 조합을 모아서 만든 배치 파일운영체제의 Shell을 이용하여 한줄씩 순차적으로 읽으면서 명령어들을 실행시켜주는 인터프리터 방식의 프로그램Shell Script를 활용하여 묶어진 명령어 조합을 수행하거나 반복적인 명령어를 단일 명령으로 쉽게 사용할 수 있음 기본 문법파일로 작성 후, 파일을 실행파일의 가장 위 첫 라인은 #!/bin/bash로 시작파일 형식(확장자): '파일이름.sh'쉘 스크립트 파일은 코드를 작성한 후에는 실행 권한 부여 ..

문제 문제 바로가기> 정올 1985번: 분수 정렬 JUNGOL history 최근 본 문제 jungol.co.kr 풀이 1 * 1/2과 2/4처럼 값이 겹치는 경우 분모가 작은 1/2을 선택 (분모가 작으면 분자도 작다) 조합 가능한 모든 분수를 생성해주고, 분수값(오름차순) 과 분모값(오름차순)을 기준으로 정렬해준다. 만약 분수값이 이전 분수값과 같다면 continue 해주면 된다. 분모의 범위를 2부터, 분자의 범위를 1부터 한 것은 0과 1이 되는 값은 어차피 0/1과 1/1이 출력될 것이기 때문이다. 100000 을 곱해준 후 나눈 값을 저장한 것은 소수가 아닌 정수 형태로 저장하기 위함이다. 1.0을 곱해주고 double로 저장해서 계산해도 된다. #include #include #include..

문제 문제 바로가기> BOJ 9047번: 6174 9047번: 6174 입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스마다 한 줄에 네 자리 수(1000~9999)가 하나씩 주어진다. 단, www.acmicpc.net 풀이 1 타입을 문자열과 정수로 변환해가며 풀었다! 이때 정수 -> 문자열로 변환하는 과정에서 0089 같은 것이 나올 수 있으므로 자리 수를 맞춰주는 연산을 추가로 진행해주었다. 이런 과정을 거치지 않으려면, 풀이2와 같은 방법으로 풀 수도 있다. #include #include #include #include #define SIZE 4 using namespace std; in..

cherry-pick 다른 브랜치에 있는 커밋을 선택적으로 내 브랜치에 적용시킬 때 사용하는 명령어 # git cherry-pick {commit hash} $ git cherry-pick 555f8b4 # 한번에 여러개의 커밋을 반영하고 싶은 경우 $ git cherry-pick 555f8b4 8f618a0 480b6bb $ git cherry-pick 555f8b4..480b6bb # 가져오고 싶은 커밋 범위 지정 아래는 cherry-pick을 이용하여 현재 branch y에 branch x의 3개의 커밋을 반영한 모습이다. 코드에 대한 수정사항, 커밋 로그, 작성자 역시 그대로 가져온다. cherry-pick 충돌 해결 다른 브랜치의 커밋 사항을 가져오므로 수정 사항이 현재 브랜치의 코드에 맞지 않..