기술 블로그

https://www.acmicpc.net/problem/1477 1. 휴게소의 위치는 1이 아니라 0부터 시작한다. "길이가 1,000"이라는 말과 "~휴게소가 없는 구간의 최댓값은 200~701구간인 501이다.~" 이라는 말 그리고 최대 길이가 1000이라는 조건이 존재할 때, 시작 위치가 0이라는 뜻이다. 2. 처음에는 chk() 함수의 return을 int로 했었다.(0, 1, 2) 0 : cnt > M 1 : cnt == M 2 : cnt < M [최초 구현 로직] 1과 2 일 때, right = mid - 1; → "1"일 때만, ret = min(ret, mid); 수행 0일 때, left = mid + 1; 하지만, cnt == M일 때만 최솟값을 갱신할 필요가 없었다. 이유는 cnt <..

https://www.acmicpc.net/problem/2887 지난 풀이 : https://hsdevelopment.tistory.com/417 일반적인 MST로는 메모리 초과가 발생한다. 처음에는 모든 행성들 간에 각각 행성의 x, y, z 및 이중 for문을 활용해, vector에 담는 방법을 생각할 수 있지만. 최대 10만개라서, 메모리 초과가 발생한다. 생각해볼 수 있는건 행성 A : xa, ya, za 행성 B : xb, yb, zb 일 때의 거리로 인정 받는 최솟값은 min(|xa-xb|, |ya-yb|, |za-zb|)라는 점이다. 즉, 행성 A와 행성 B를 이중 for문을 통해 담는 것이 아니라, x 좌표, y 좌표, z 좌표끼리 각각 vector에 담아서 구현할 수 있다. 1. x좌표..

https://www.acmicpc.net/problem/18430 지난 번 풀이 : https://hsdevelopment.tistory.com/788 현재 좌표(r, c)를 부메랑으로 사용할지 말지 2가지의 경우를 모두 고려해야한다. go bool 변수를 활용해서 현재 좌표(r, c)에서의 4가지 부메랑 중 하나를 수행했다고 해서, 현재 좌표(r, c)에서는 부메랑을 사용하지 않는 경우를 잊어버리며 안 된다. 오답인 소스코드는 현재 좌표(r, c)를 부메랑으로 사용한 후에는 go bool 변수에 true로 표시하는 바람에 그 밑의 경우(현재 좌표를 부메랑으로 사용하지 않을 때)가 수행되지 않는다. 그래서, 단순 go bool 변수를 사용하지 않고, 삼중 for문 밑에 바로 simulation(r, c..

https://www.acmicpc.net/problem/16932 오랜만에 풀어보았다. 저번 풀이 : https://hsdevelopment.tistory.com/336 저번에 푼 풀이 로직이랑 똑같다. 1. dfs를 통한 그루핑 및 그룹 번호 표기, 동일한 그룹 내 1의 개수 2. 이중for문을 통해 0인 경우에만 동서남북 방향으로 좌표에 따른 그룹번호를 활용하여 개수를 더함. (단, map을 통해서 동일한 그룹일 경우 무시) #include using namespace std; int m[1010][1010]; int R, C; int group[1000011]; int dy[4] = { 1, 0, -1, 0 }; int dx[4] = { 0, -1, 0, 1 }; bool used[1010][10..

https://www.acmicpc.net/problem/17472 오랜만에 풀어보았는데, 계속 오답이 출력됐다. 이유는 bfs의 로직때문이었는데, 수정하지 통과됐다. 잘못된 bfs 로직 // → if (k == 0) { if (c + 1 < C && !vis[r][c + 1][k] && (g[r][c + 1] == 0 || g[r][c + 1] == e)) { if (g[r][c + 1] == e && g[r][c] == e) { continue; } vis[r][c + 1][k] = true; q.push({ k, {r, c + 1} }); } } // ↓ else if (k == 1) { if (r + 1 < R && !vis[r + 1][c][k] && (g[r + 1][c] == 0 || g[r..

https://www.acmicpc.net/problem/13335 처음에는 Greedy 문제인줄 알았다. 로직 순서 호출만 조심하면 되고, 나머지는 구현이다. 1. 한 칸 씩 이동 → 트럭 제거 → 새로운 트럭 추가 순서로 호출 2. 무게 총 합에서 제거한 트럭의 무게를 뺄 때, v.erase(itr)를 나중에 해준다. 먼저하면, itr이 자동 증가하기 때문에 그 다음 원소(트럭)의 무게가 빼진다. 3. 새로운 트럭을 추가할 때, index와 현재 다리에 올라가 있는 트럭들의 무게 총합(total_weight)를 올라갈 트럭의 무게까지 고려하여 if 조건문을 잘 따진다. #include using namespace std; #define MAX 1010 // https://www.acmicpc.net/..

https://www.acmicpc.net/problem/18430 저번 풀이 : https://hsdevelopment.tistory.com/507 18430번 무기 공학 https://www.acmicpc.net/problem/18430 # 탐색 # dfs # 복습 # 구현 # 브루트포스 # 추천 # 코딩 # 코테 # 백트래킹 # back 백트래킹 문제이다. 현재 좌표에서 방문하는 경우, 방문하지 않는 경우까지 모두 고려.. hsdevelopment.tistory.com 오랜만에 다시 풀어보았는데, 5%에서 계속 틀렸다. 오답 소스코드가 틀린 이유는 크게 2가지다. 1. simulation() 함수 내에서 for(k:0~4)만 해줘도 되는데, 삼중 for문(for i:0~n, j:0~m, k:0~4)..

https://www.acmicpc.net/problem/2138 0번 스위치를 누를 때와 누르지 않을 때 2가지 경우를 나누어 구현한다. idea) i번 째 스위치를 누를지 말지 고민하는 상황일 때, 현재 i-1번 째 스위치의 현재 상태와 우리가 만들고자 하는 전구의 i-1번 째 스위치의 상태가 다르면 눌러야 한다. #include using namespace std; #define MAX 200000 int n, now[MAX], now2[MAX], goal[MAX], ans1, ans2; bool isSame() { for (int i = 0; i < n; i++) { if (now[i] != goal[i]) { return false; } } return true; } int main() { ci..