끄적끄적 끄적끄적

n일동안 상담 일정을 적절히 잡아 최대 이익을 구하는 문제이다. 처음 문제를 보자마자 생각난 알고리즘은 DP였지만... 효율적인 공식이 생각나지 않아 결국 DFS로 방향을 틀었다. 일하는 날짜(start), 현재까지의 이익(cur_profit)을 인자로 받고, start부터 n일까지 dfs를 돌면서 일할 수 있는 모든 경우를 탐색하면 된다. 딱히 어려운 점은 없었지만, 처음에 start가 n보다 크면 dfs를 종료하도록 코드를 짰다가 마지막 날(n일)에 일하게 되는 경우가 제외되어 최대 이익이 제대로 계산되지 않았다. 그래서 start > n + 1로 수정해주었고 결국 맞았다. if (visited[start] || start > n + 1) return; // 14501_퇴사.cpp #define _C..

입력으로 날 수와 각 날의 주가가 주어졌을 때 최대 이익을 구하는 문제이다. 처음 이 문제를 봤을 때 제일 먼저 생각난 방법은 DP였다. 하지만 DP로 하기에는 주어진 숫자가 너무 크기도 했고... 단순히 감소하는 시점에 팔아버리는 것으로 구현하면 뒤에 더 고점이 나왔을 때 반례가 존재하기 때문에 이 방식은 포기했다. 내림차순으로 sorting한 후에 이익을 계산해볼까도 했지만, 이 경우 sorting시 순서도 같이 기억해야했기 때문에 포기.. 결국 내가 선택한 방법은 뒤에서부터 반복문을 돌아서, 이전까지의 최대 주가보다 현재 주가가 더 크면 최대 주가를 갱신하고, 반대로 현재 주가가 더 작으면 차익만큼을 플러스하는 식으로 구현했다. 예를 들어 주가가 cost[8] = 4 1 2 4 5 6 2 2 이렇게..

테트로미노가 놓인 칸 수의 최대값을 구하는 문제이다. 처음에 DFS를 쓸까 하다가... 복잡할 것 같아서 그냥 Brute Force를 썼다. 아래 5가지 모양에 대한 모든 경우의 수를 지정해줘야 한다. 먼저 제일 쉬운 긴 직사각형 모양과 정사각형 모양의 좌표를 지정해준다. // 직사각형 {{0, 0}, {0, 1}, {0, 2}, {0, 3}}, {{0, 0}, {1, 0}, {2, 0}, {3, 0}} // 정사각형 {{0, 0}, {1, 0}, {0, 1}, {1, 1}} 그 다음 ㄹ형 모양과 ㅗ형 모양의 좌표를 지정해준다. 문제에서 회전뿐만 아니라 대칭까지도 허용한다고 했으므로, 각 모양의 경우의 수는 총 4가지이다. // ㄹ형 {{0, 0}, {1, 0}, {1, 1}, {2, 1}}, {{0, ..

[문제] : 각 빌딩의 관리인들이 확인할 수 있는 옥상정원 수의 총합 구하기 입력 예시 출력 예시 6 //빌딩의 개수 N (1 ≤ N ≤ 80,000) 10 //각 빌딩의 높이 (1 ≤ hi ≤ 1,000,000,000) 3 7 4 12 2 5 (= 3+0+1+0+1+0) [풀이] 문제에 제시된 예시를 보면, 1번 관리인은 2, 3, 4번 옥상을 확인할 수 있고, 2번은 다른 빌딩의 옥상을 확인할 수 없으며, 3번은 4번 옥상을 확인할 수 있다. 이를 반대로 생각해보면, 1번은 아무도 볼 수 없고, 2번은 1번에서만 볼 수 있다. 또한 3번은 1번에서만 볼 수 있고, 4번은 1, 3번에서만 볼 수 있다. 마찬가지로 5번은 아무도 볼 수 없고, 6번은 5번만 볼 수 있다. 이 발상을 이용하여 스택을 구현하..

pair는 두 개의 자료형을 하나로 묶어서 사용할 수 있게 해준다. 첫 번째 변수를 first, 두 번째 변수를 second라 한다. pair는 2차원 배열의 인덱스나 좌표를 사용할 때, 두 정점 사이의 최단거리를 묶어서 저장해야할 때 사용한다. 1. 사용법 1 2 3 4 5 6 7 8 9 #include pair p[10]; p[1] = make_pair(10, 'c'); cout

벡터(vector)는 가변 배열을 만들 때 사용하는 STL의 컨테이너 라이브러리이다. 자동으로 메모리가 할당되는 배열이라고 생각하면 된다. [벡터의 특징] 1. 가변적인 크기 크기가 선언 시에 고정되는 배열과는 달리, vector는 크기가 동적으로 변한다. 따라서 저장할 데이터의 개수를 미리 알 수 없다면 vector을 사용하는 것이 좋다. 2. 중간에 데이터를 삽입/삭제할 수 없다. 벡터는 배열처럼 데이터를 순차적으로 저장하기 때문에 중간에 데이터를 삭제하거나 삽입하는 것이 번거롭다. 따라서 벡터는 가장 뒤에 있는 데이터를 삭제 및 삽입하는 경우에 사용하는 것이 좋다. 3. 저장할 데이터 개수가 많은 경우 검색이 용이하지 않다. 데이터를 순차적으로 저장하기 때문에 많은 데이터를 저장할 경우 검색 속도가..

C++에서 사용하는 표준 입출력 개체인 cout과 cin을 사용하려면 iostream 헤더파일을 include하여 std 네임 스페이스를 사용해야 한다. 1 2 #include using namespace std; 1. iostream STL(Standard Template Library)에서 제공하는 클래스 중 하나로, 데이터 입출력 시에 사용하는 클래스이다. 2. namespace namespace는 모든 식별자(변수, 함수, 형식 등의 이름)가 고유하도록 보장하는 코드 영역이다. 두개 이상의 독립된 코드가 함께 사용될 때 서로 이름이 충돌하는 문제를 방지하기 위해 namespace 키워드를 통해 독립된 namespace를 선언할 수 있다. 3. std 원래 C++ 설계 시에는 C++ 라이브러리의 모..

hell_fire 문제와 비슷한 것 같지만... preg_match 함수의 필터링 목록에 sleep까지 포함되어 있어서 시간 기반 Blind SQL 인젝션을 사용할 수 없다. 일단 테이블에 뭐가 있는지 알아보기 위해 order에 1을 넣어보았다. hell_fire에서 admin의 score이 200이었던 것에 반해, 이번에는 admin의 score이 50이었다. 즉, id로 정렬하든 score로 정렬하든 똑같은 결과가 나온다. 그래서 이번에도 if문을 사용하여, 조건문이 참이면 score로 정렬하고, 거짓이면 출력이 되지 않게끔 아래와 같이 설정했다. ?order=if(id='admin' and length(email)>0,score,2000) 그런데 의도와는 달리 조건문이 거짓일 때 테이블이 아예 출력..