개발/알고리즘

문제 접근 이전 회의 시간의 끝나는 시간보다 늦게 시작하는 회의 중, 가장 빨리 끝나는 회의만으로 구성하면 가장 많을 수 밖에 없다. 다른 회의들보다 빨리 끝난다는 건 그만큼 더 넣을 수 있다는 것이니 증명 끝! 예를 들어 1~5 보다 4~6이 효율적이려면 4 이하로 끝나는 회의가 있어야 되는데 그럼 애초에 4~6을 선택할 바에는 4 이하로 끝나는 회의를 선택하겠지? 4는 당연히 5보다 작고 ㅋㅋ 그럼 첫 줄의 가정은 성립한다는 걸 알 수 있다. 이전 회의의 끝나는 시간과 다음 회의의 시작하는 시간이 같아도 되는 걸 고려하지 않아서 한 번 틀렸었고, 정렬한 뒤 첫번째 pair 를 첫 회의로 잡았기 때문에 23행 for 문에서는 i=1 부터 시작해야되는데 0부터 시작해서 또 한 번 틀렸었다. 실수도 실력이..

문제 접근 최단 경로 찾기의 느낌이 들어서 BFS 로 풀었다. 나는 N 에서 K 로 접근하는 게 아니라 K 에서 N 으로 접근하는 방법으로 풀었다. N 에서 K 로 접근하면 텔레포트(2배) 하는 경우를 항상 고려해야돼서 큐에 들어가는 값이 많아지지만, K 에서 N 으로 접근하면 K 가 짝수일 때만 텔레포트를 고려하면 돼서 비교적 적은 양으로 처리할 수 있었다. 사소한 차이지만 효율이 좋아지니 나쁘지 않은 것 같다. 제출 했을 때 자꾸 런타임 에러나서 찾아보니 주로 아래와 같은 이유로 에러가 발생한다고 한다. 1) 배열 인덱스 범위를 벗어나는 경우 2) 잘못된 공간에 접근하는 경우 3) 0으로 나누는 경우 확인해보니 44행 ~ 51행 if 문에서 && 연산자로 조건을 확인할 때 연산 결과 인덱스가 visi..

문제 접근 요즘 구체수학이라는 책을 읽고 있어서 점화식에 꽂혔다. 보니까 점화식으로 풀 수 있을거 같아서 n 에 값을 넣어 경우의 수를 따져봤는데 ans[n] = ans[n-3]+ans[n-2]+ans[n-1] 이라는 게 보였다. ans[n+1] 에 대해서는 가장 마지막 값인 ans[n-3] 을 빼고 ans[n] 을 더하면 되니 ans[n+1] = (ans[n-3]+ans[n-2]+ans[n-1])+ ans[n] - ans[n-3] = 2*ans[n] - ans[n-3] 으로 간략하게 만들었다. n=10 일 때까지 계산에서 ans 배열에 넣어놓은 다음에 n 을 입력받으면 바로 출력되게 구현했다. 점화식을 증명해보자. n=4 인 경우는 아래와 같다. 1 1 1 1 1 1 2 1 2 1 2 1 1 2 2 1..

문제 접근 나는 바보다 ㅎ헤헿. 문제 똑바로 이해 안 하고 구현하다가 잘 안 돼서 다시 읽어보니 잘 못 풀고 있었다. 문제 제대로 이해하자마자 바로 풀었다. 허무하다. 원리는 간단하다. 입력받고 배추가 있는 곳은 true로 설정했다. find 함수에서 주변에 true 가 있으면, 재귀로 들어가서 지운다. 끝! 처음에는 while 문으로 한번에 처리하려고 했는데 시간 초과가 나왔다. 그래서 false로 바꾸는 방식을 한 번에 하는 게 아니라 find 함수로 하나하나 조건 확인해보며 재귀로 분할해서 처리하니 제 시간 안에 풀렸다. 오늘의 교훈> 1. 문제를 똑바로 이해하고 풀자. 2. 문제는 분할할 수 있다면 분할해서 처리하자. (재귀 좋아영) 문제 코드 #include using namespace std;..

문제 접근 vector 으로 접근했다가 우선 순위가 있다는 걸 알고 tuple 로 접근했다. tuple 은 여러개의 타입을 하나로 접근할 수 있도록 한 것이다. 문제를 풀고 나서 다른 풀이를 보니 algorithm 헤더에 stable_sort 라는 함수가 있었다. 찾아보니 하나의 요소로 정렬을 한 뒤 다른 요소들의 정렬 순서가 정렬 전과 같이 유지되도록 하는 함수였다. 한마디로 나이에 대해 정렬한 뒤 먼저 들어온 순서대로 정렬된다는 것이다. 오늘도 지식이 늘었다. 문제 풀이 #include #include #include #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL)..

설명 덱(Dequeue) 은 Double Ended Queue 의 준말로 들어가는 pointer, 나오는 point 가 따로 있었던 큐와는 달리 양쪽에서 들어가고, 나올 수 있어 자유도가 높다. Double Ended Queue 라고 해서 꼭 Queue 의 특성만 가지고 있기보다는 스택의 특성도 가지고 있다. 덱은 복잡한 스케쥴링이나 우선 순위를 조절할 때 사용되는데, 양방향으로 접근이 가능해 스택과 큐보다 자유로워 복잡한 스케쥴링에서 스택과 큐보다 효율이 좋고 우선 순위를 조절하기 용이하다. 코드 #include #include using namespace std; template class deque; template class Node { friend class deque; private: T da..

설명 큐는 FIFO(First In, First Out)이다. 보통 프린트 큐, 게임 큐 등 대기열에 많이 쓰인다. 함수에 대한 설명은 백준 10845번 : 큐를 참조하자. 코드 #include #include using namespace std; template class queue; template class Node { friend class queue; private: T data; Node* prev; Node* next; public: Node(T data, Node* prev=NULL, Node* next=NULL) { this->data = data; this->prev = prev; this->next = next; } }; template class queue { private: Nod..

설명 스택은 LIFO (Last In, First Out) 이다. '설명 끝!' 이라고 할 수 있다. 가장 늦게 들어온 데이터가 가장 빨리 나간다. 우리가 코딩한 프로그램이 함수를 호출할 때도 스택 프레임(Stack Frame) 이라는 메모리 블록을 할당하는데 여기에는 함수가 호출될 때 이와 관계되는 변수가 저장된다. 우리가 흔히 사용하는 재귀에서도 스택 구조로 변수가 할당된다. 함수에 대한 설명은 백준 10828번 : 스택 을 참조하자. 코드 #include #include using namespace std; template class stack; template class Node { friend class stack; private: T data; Node* prev; Node* next; pub..