Doby's Lab

평범한 이분 탐색 문제이지만 이번 문제에서 중요했던 포인트가 평소에 내 취약점이라 정리를 해두고 싶었다. 난 기본적으로 범위? 같은 것에 약하다. 혹은 0으로 시작하는지 1로 시작하는지 이런 문제처럼 범위에 영향을 주는 그런 문제들에 좀 약하다. 내가 짰던 코드의 오류 이유 우선 코드를 짜서 TC는 통과할 수 있지만 제출했을 때는 시간 초과를 유발한다. 그리고, 반례도 있었다. 반례의 이유부터 먼저 말하자면 나는 코드를 짤 때, 구간이 아닌 점들로 가로등이 빛을 비추고 있는지 체크했었다. 그러다 보니 4와 5에 빛을 비춘다고 한들 4~5 사이의 구간은 비추지 못하는 것을 알 수 있다. (코드 블록에 그에 따른 반례도 적어두었다.) 시간 초과가 날 거라고는 어느 정도 예상을 했었다. 그래도 구현을 시켜보자..

이번 문제는 답을 구하고 싶었다. 무조건... (어떤 미래가 기다리고 있는지도 모른 채로...) 지금 현재 주어진 상황 (개인적인 얘기) 문제에 대해 들어가기 전에 현재 웃픈 상황에 대해 설명하고 싶다. 어제 서점을 들렸다가 읽어보고 싶은 책이 있어서 찾고 나서 서론을 봤는데(이코 테: 나동빈 님 책) 의외로 코딩 테스트에서 구현과 문자열의 비중이 상당히 높은 걸 알 수 있었다. '시간을 내서 '구현' 문제에 집중을 해봐야겠다'라는 생각을 했다. 왜냐하면 그 비중을 나타낸 그래프를 본 순간, '어쩌면 알고리즘 지식, 알고리즘 구현 능력만 가지고서 계속 문제를 풀었던 게 아닐까?', '흔히 말하는 '빡구현', 알고리즘 지식을 제외한 아이디어를 능력치로 친다면 난 아직 바닥이 아닌가?'라고 생각했기에 지금 ..

이 문제는 전제가 좀 길다. 결론적으로 다음 단어들을 입력하고, 숫자를 입력하면 이름을, 이름을 입력하면 숫자를 출력하는 문제이다. 당연히 pair형 vector배열을 선언하여 풀려고 했지만 string을 입력했을 때는 어떻게 숫자 값을 도출할지가 문제였다. 여기서 사용된 것이 C++의 STL map이다. STL map은 이라는 헤더 파일에 선언되어있다. map m; 이런 방법으로 선언하여 key값과 value에 원하는 타입형을 선언하여 사용할 수 있다. 데이터를 삽입/삭제/찾기 시간 복잡도 모두 O(log N)이다. 같은 key값에 value를 삽입할 경우 기존에 있던 value값은 삭제된다. (해시 맵과는 다른 듯하다.) 삽입하는 방식은 m.insert(make_pair(key, value)); pa..

오래간만에 DP문제를 풀었다. 이번 문제는 점화식이 꽤 어렵지 않았다. 하지만, 틀린 점화식이었다. 작성했던 코드는 이랬다. #include #include using namespace std; int cache[50001] = { 0, }; int main() { int n; cin >> n; cache[1] = 1; cache[2] = 2; cache[3] = 3; int num = 2; for (int i = 4; i n; cache[1] = 1; for (int i = 1; i

이번 문제도 분할 정복이다. 다만 이번 문제는 2차원 배열을 사용하지 못한다. 32769 x 32769 사이즈의 배열을 선언해야 했어서 이는 엄청 크기 때문에 선언하지 못한다. 그래서 배열 없이 접근했다. '0행의 0열 0부터 시작' 같은 키워드는 이번 문제에서 유독 헷갈렸었기 때문에 행과 열은 1부터 시작하고 1부터 시작하게 하여 마지막 결과 값에 -1을 해주었다. 분할 정복 함수에서 각 사분면에 해당하는 조건들을 달고, 함수의 재귀를 거치면서 입력한 행렬과 함수의 도출 행렬이 같다면 함수를 종료하고, 해당하는 결과 값에 -1을 해준 뒤에 출력하고 함수를 종료시켰다. #include #include #include using namespace std; // 배열 사이즈가 너무 커진다. >> 꼭 배열을 ..

이번 문제는 첫 공식적인(?) 분할 정복 문제다. 의외로 간단하게 풀었었다. '다만 생각을 조금만 더 해볼 걸'이라는 아쉬움이 있었다. '설마 하나하나 다 검사하겠어'라는 생각에 한 번이라도 구현했으면 시간 아꼈을 텐데 포인트 이번 분할 정복의 포인트는 문제에서 얻을 수 있었다. n이 2의 제곱수로 주어지고, 색종이들 또한 2의 제곱수 형태로 존재하기 때문에 N / 2로 분할해나가면서 리커시브 콜을 하면 됐었다. 맨 위에서 말한 '설마 하나하나 다 검사하겠어'라는 생각을 구현하면 된다. 소스 코드 #include #include using namespace std; int n; int map[129][129] = { 0, }; int white = 0; // 0 int blue = 0; // 1 void..

입력값을 넣을 때마다 즉각적으로 정렬을 시키면 되는 문제가 아닐까를 생각했지만 정렬의 시간 복잡도 O(NlogN), 연산의 최대 개수가 1,000,000이므로 이는 시간 초과를 발생시킨다. 즉, 이번 문제에서는 우선순위 큐(priority queue)의 사용을 유도한다. 큐의 특성상 pop(D)를 할 때는 앞에서 밖에 할 수 없기 때문에 두 개의 우선순위 큐를 선언해주었다. 오름차순과 내림차순. 두 개의 큐를 선언하여 풀었던 코드는 다음과 같다. #include #include #include #include #define ll long long using namespace std; int main() { int T; cin >> T; for (int i = 0; i < T; i++) { int n; c..

이번 문제는 꽤나 어려웠다. 어려웠던 포인트들을 정리해보면 1. DFS로 풀어야 할지 BFS로 풀어야 할지를 아직 헷갈린다. 2. DFS로 풀어야 할 땐 동작원리를 알고 있어도 어떠한 논리로 접근해야 하는지 모르겠다. 이번 문제는 BFS로 첫 시도를 했었다. 높이가 낮아지다가 다시 높아지는 시점을 두고 이를 경계선이라고 생각하며 구역을 나누어 각 구역을 산봉우리로 취급하려 했었다. 하지만, 이를 표현하는 데에 있어서 산 중턱에서 BFS가 돼버리면 구하려는 구역 이상의 수가 도출되기 때문에 다음 코드로는 답을 도출해낼 수 없었다. 그래서, flag 변수나 min값을 도입해 봤지만 풀리지 않았다. #include #include #include using namespace std; int n, m; int ..