Doby's Lab

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 문제를 읽으면 쉽게 BFS를 떠올릴 수 있다. 하지만, 문제를 풀면서 실수도 하고, 최적화를 생각하지 못해서 많이 틀렸던 문제다. 정리를 하는 이유는 이런 실수가 있었다. 다음부터는 그러지 말자의 의미. [솔루션] 아마 사람들이 좀 많이 헷갈리지 않을까 싶은 부분은 '명령어를 어떻게 저장할 것인가? (구할 것인가?)' >> 간단하다, pair형 큐를 선언하고 한쪽에는 숫자(int), ..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제에 들어가기 앞서 (1) 이번 문제는 이때까지 겪어온 '빡구현' 문제들을 애기로 만들어버리는 수준이다. 걸어야 할 조건들이 엄청 많다. 1) 처음엔 DFS로 했을 때, DFS로는 안 되겠다. BFS로 해야지. (종료 조건이 없었음) 2) BFS로 했을 때, 이 무한 루프 어떻게 처리하지? 3) 방문 체크를 해야겠구나? 그러면.. 따질 게 많은데 싹 갈아엎어야 하나? 2번을 갈아엎었다. ..

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 저번에는 안 풀리던 문제였는데 오랜만에 시도해보니 풀렸다. 저번 코드는 잘 기억나진 않지만 이번에 한 거보다 더 복잡했던 거 같은데 기억이 안 난다. 여러 가지 경우를 계속 생각했었던 거 같다. 기억나는 건 이런 경우? 하지만, 구현한 코드에서는 상관없다! 주사위를 굴렸을 때 나오는 모든 경우(1 ~ 6)를 다 따지기 때문이다! 이번 문제는 '응용력'..

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

이번 문제에서 크게 어려웠던 점은 없었으나 각 문제에 대한 포인트를 항상 블로그에 담아두려 하기 때문에 가져왔다. 문제에서 헷갈릴 수 있는 건 visited의 리셋이었다. 비의 높이에 따라 bfs를 해주며 건물의 개수를 cnt하며 배열에 따로 담았었다. 하지만, cnt를 담은 배열을 디버깅해보니 처음을 제외하고는 전부 0이었다. 이 부분에서 visited를 초기화시키지 않았구나라는 것을 알고 reset 함수를 작성하고, 비에 높이에 따라 건물 cnt가 끝날 때마다 reset 함수를 콜 해주었다. [코드] #include #include #include #include using namespace std; int map[101][101] = { 0, }; bool visited[101][101] = { 0..

이번 문제 풀이는 못 풀어서 다른 사람의 답을 참고했음에도 성취감을 느낄 수 있었다. 주석처리가 이번 문제의 성취감 포인트였던 거 같다. 기존의 문제 풀이 방식 for문을 사용하여 1일 때, BFS를 사용하면 한 번에 모든 0인 노드를 다 순회하기 때문에 다른 접근법이 필요했다. 떠올랐던 방법이 for문을 사용하여 1일 때, BFS를 사용하지 않고, 큐에다가 그 노드를 push 한다. 그리고 난 뒤에 BFS를 실행시키면 답에 접근할 수 있었다. 하지만, 또 다른 문제가 발생한다. 현재까지의 접근법으로 작성한 코드는 이렇다. // 궁금증 1: 굳이 이번 문제에 visited가 필요했을까 // 궁금증 2: bfs의 if 조건문에서 map이 1인 경우는 따져도 되지 않을까 #include #include #i..

DP의 접근 방법이 꽤 어려웠다. 아무래도 점화식을 어떻게 세우는지 접근을 하지 못 했다. (BFS로 풀릴 거 같아서 BFS로 푼 풀이는 맨 아래에 첨부해두었다.) 그래서 다른 사람의 코드를 참고했다. (Bottom-Up 방식) #include #include #include using namespace std; int cache[100001] = { 0, }; int main() { int n; cin >> n; for (int i = 2; i > n; bfs(n); sort(answer.begin(), answer.end()); cout

주석 조건 참고 #include #include #include #include using namespace std; queue q; bool visited[100001] = { 0, }; void bfs(int n, int k) { q.push(make_pair(n, 0)); while (!q.empty()) { int value = q.front().first; int cnt = q.front().second; q.pop(); if (value == k) { cout > k; bfs(n, k); return 0; }