Doby's Lab

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 이 문제를 처음 보자마자 BFS를 떠올릴 수 있었지만 '제일 포인트가 되는 부분이 벽은 어떻게 세우지'가 고민거리였다. 하나하나 다 따지기엔 경우의 수가 너무 많아서 괜찮을까 싶었지만 주어진 평면의 크기는 8x8이라서 8^6(582144)로 큰 시간을 따지지는 않겠다는 생각이 들었다. (벽이 한 좌표에 몰빵 되는 경우도 계산한 것 >> 중복을 따지기엔 시간 계산에 너무 많은 시간을 쏟고 싶지 않았음.) 재귀 ..

이 문제는 크게 고민할 필요 없이 백트래킹으로 쌍 구하고, 최대공약수를 구해 더해나가면 되는 문제였다. 하지만 이를 구현했을 때, 시간 초과가 발생한다. 코드 (시간 초과) 백트래킹에서 발생하는 것인지, 최대공약수를 구하는 함수에서 발생하는 것인지 알 수 없었다. 하지만, 1,000,000을 넘지 않는 수라면 그에 근접하는 엄청 큰 수들이 100개까지 있다고 생각해보면 몇 쌍들이 생길지 모를뿐더러 거기다가 곱하기 1,000,000을 해준다면 엄청 큰 값이 나와서 시간 초과를 유발하는 것을 알 수 있었다. >> 최대공약수를 구하는 함수가 문제다. #include #include #include using namespace std; bool visited[101] = { 0, }; vector two; //..

이번 문제 논리는 굉장히 어려울 줄 알았다. 어떻게든 솔루션을 발견하려고 각 값의 연관성을 찾으려 했다. 그 결과 TC에서 논리를 찾을 수 있었다. Input 10 12 3 9 Output 33 10과 12 즉, M과 N의 차이는 +2다. x와 y의 차는 +6이다. 이를 보고, +6은 +2의 3배니까 3바퀴 정도 돌면 차이가 3배만큼 벌어질 거 같다는 생각에 10을 기준으로 3바퀴를 돌려보니 30과 30 각각의 M과 N으로 나눈 나머지는 0과 6이 나온다. (정확히 말하면 10은 3바퀴, 12는 2바퀴 돌고 6번의 해가 지난 것이다.) 여기서 3번의 해가 더 지나면 3 9가 x, y값과 일치하면서 맞아떨어진다. (10을 기준으로 3바퀴 돌렸으므로) 10 * 3 + (3번의 해가 지났으므로) 3 = 33 ..

백준 15094번 문자열 관련 문제를 풀다가 VS 컴파일러에서는 오류가 없지만 백준에서는 Segfault Error가 나서 문제점을 찾았었다. 전에도 이런 비슷한 문제를 풀다가 똑같은 오류가 났었는데 두 문제의 공통점이 있었다. 문자열 문제 스택을 이용하여 풀려했다 문자열은 문제가 없는 거 같아서 스택을 살펴보았다. 아래 코드는 VS 컴파일러에서는 문제가 없지만 백준에서 에러가 발생한다. #include #include #include using namespace std; int main() { char idx[1001]; cin.getline(idx, 1001, '\n'); stack s; for (int i = 0; i < 1001; i++) { if (idx[i] == 'U') { if (s.emp..

평범한 이분 탐색 문제이지만 이번 문제에서 중요했던 포인트가 평소에 내 취약점이라 정리를 해두고 싶었다. 난 기본적으로 범위? 같은 것에 약하다. 혹은 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