개인적으로 공부한 내용을 정리중입니다.

문제는 시작, 끝 시간으로 구성된 여러개의 시간 구간들이 주어진다. 그리고 임의의 1초 구간 동안 동시에 시간 구간이 몇개나 최대로 같이 있는지 구해보라는 것이다. 시간 구간은 2000개가 주어지니까 n^2도 문제 없다. 내가 생각한 구현은 시작 , 끝 구간 시간들 쭉 저장하고, 그것을 순회하면서 이 사이에 있는 타임라인들의 수를 구하고 그 최대를 구한다. 시간의 범위는 9월15일 00:00:00.000 ~ 23:59:59.999 인듯? 그냥 int로 변환해서 저장하면 될듯 근데 문제가 시간을 못 더하겠다.....음 .... 1.181 -> 이게 string인데 어떻게 바꾸지. 해결하려 한 부분들 1. 소수 문자열을 -> 실제 소수로 변환 -> 근데 float ,double은 밑에 부분이 잘려서 그냥 i..

이 문제를 스택으로 해결했었다. 그런데 음 스택으로도 다시 풀어보고, 분할 정복으로도 풀 수 있던데 두가지로 풀어보겠다. 이전에 스택했으니 일단 분할정복으로 하자. 보통 분할 정복은 절반씩 분할하는거 같다. 계속 분할해서 한개가 되고 두개로 합칠때 음? 어떻게 생각해야되는 걸까.... 음 분할해서 해당 영역의 가장 큰 넓이를 찾으면 된다고 생각한다. 그리고 이제 두개를 합치면 되는거 같은데, 그렇다면 합칠때 양쪽 중에 더 작은 높이 * 양쪽 갯수 랑 두개 영역을 비교해서 가장 큰 넓이를 선택하게 한다. 이때 합병하면서 저장해야 되는 값은 가장 작은 높이, 합친 넓이이다. 가장 작은 높이랑 갯수를 알면 왼쪽 오른쪽을 합칠때 합쳐질 넓이를 알 수 있다. 재귀함수를 사용할텐데 매개 변수로 시작,끝 인덱스를 넘..

전에 테스트때 풀었던 문제이다. 그런데 그때 구현이 틀렸다. 근데 틀린 원인이 내 생각에는 설계를 잘못한듯. 완전 탐색이긴 한데 , bfs도 어떻게 수행할지 조건들에 대한 내용을 결정하고 , 그것을 깔금하게 구현해야 할듯. 나는 이동할 수 있는 경우가 몇가지인지 제대로 파악 안하고 시작했다. 그리고 일단 로봇의 상태를 어떻게 표현할지 부터 정했어야 했다. 로봇의 상태를 어떻게 표현할지 정확히 생각하고, 배열의 범위 확인도 함수로 구현해서 확인 후 그 함수 내부에서 큐에 넣도록 하니까 깔금하게 금방 구현했는데, 예제만 맞고 테케는 한개만 맞는다..... 왜그러지 ㅠ #include #include #include using namespace std; enum { ver = 1, hori = 2 }; str..

프린터 1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다. 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다. 3. 그렇지 않으면 J를 인쇄합니다. 1번은 수행이 매우 단순하다. 2번 부분에서 뒤에 중요도가 높은 문서가 한 개라도 존재하는지가 문제 해결의 부분인거 같다. 내 생각에는 맨 처음에 대기 목록에서 맨 앞에 것을 제외하고 가장 높은 우선 순위를 max_priority에 저장한다. max_priority > J 이면 J를 대기 목록 맨 뒤에 넣는다. max_priority < J이면 출력하고 order를 1 증가한다 . J가 location이면 order를 출력한다. 근데 max_priority는 뒤에 가장 ..

스택은 진짜 그냥 맨날 나오는 문제 유형이다. 면접에서도 중요한 개념으로서 이용하라고 문제 냈는데 틀렸다.... 탑 사실전에 백준에서 풀어본 문제다. 그럼에도 풀이가 기억나지는 않음 스택을 쓴다는 것 정도 ㅋㅋ. 코딩테스트에서도 실제로 만났던 문제인데 그 당시에는 풀 줄 몰랐다. [6,9,5,7,4] [0,0,2,2,4] 예제를 분석해보면 6은 맨 왼쪽이라 0 , 9는 왼쪽에 자기보다 큰게 없어서 0, 5는 왼쪽에 9가 있으니 2, 7도 왼쪽에 5는 스킵되고 9가 있으니 2, 4는 7이 바로 왼쪽에 있으니 4이다. 그럼 목표는 모든 위치에서 왼쪽에 가장 먼저 자기보다 큰 기둥을 찾는 것이다. 스택에 넣다가 해당 위치에서의 답을 구하려면 스택에서 빼면서 먼저 만나는 자기 보다 큰 값을 확인하면 될거 같은데..

자물쇠와 열쇠 실제로 시험을 봤었는데 , 그때 어려워 보여서 안풀고 넘어갔다. 문제의 목적은 키가 락에 들어 맞는지 확인하는 것이다. 방법은 키를 회전, 이동시켜서 확인하면 된다. 문제에 주어짐..... 근데 문제는 회전 구현이 어려워 보인다. 회전을 어떻게 하지??-> 음 row, col의 위치를 교환하면 되는거 같다!!... -> 근데 이건 0,0이 왼쪽 위로 기준이 고정됬을때다. 그러면 회전하고 이동시킨다 치고...?이동도 어떻게 해야되지?? -> 이동 시키려면 키를 없애면 안되고 범위를 정해서 이동시켜야 한다.?무슨 말이지 ㅋㅋ -> root_r ,root_c , 배열 크기인 n을 사용해서 전체 배열을 이동시키기 보다 세 변수의 변경을 이동으로 처리하자. 홈에 맞는지 확인은 어떻게 하지?? -> ..

완주하지 못한 선수 참가한 선수보다 완주한 선수가 단 한명 적으니까, 그 단 한명을 찾으라는 말 같다. 음 그리고 크기가 10만이라서 O(N)만에 찾는 편이 좋겠다. 또는 O(NlogN) 음 근데 방법을 모르겠다. 그냥 생각나는 방법은 정렬하고 앞에서부터 두 배열이 같은지 확인하다가 다른 놈이 정답 같다. 일단 해보겠다. 음 내 방식이 성공했다. 그런데 해쉬를 사용하는게 문제인데 나는 정렬을 사용했으니 다른 코드들도 좀 분석해 보겠다. 방법2 c++ unrodered_map 사용 나는 주로 map을 사용했는데 이게 왠지 더 편해보인다. 음 사실 둘이 연산, 문법 규칙은 동일한거 같다. 성능이 다른듯. 밑에서 보니 RBT(레드 블랙 트리?) 를 사용한게 map , unordered_map은 해쉬 구조인듯 ..