끄적끄적 끄적끄적

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++ 라이브러리의 모..