기술 블로그

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://softeer.ai/practice/info.do?idx=1&eid=1204&sw_prbl_sbms_sn=181695 파라메트릭 서치(매개변수 탐색) + 이분 탐색 1. 처음 제출했을 때, 시간 초과 발생했는데, ps() 함수 안에서 continue가 아니라 break를 했어야 했다. continue는 의미 없다. 2. 다시 시간 초과가 발생하길래 확인했더니, ++left, --right가 아니라 left = mid + 1, right = mid - 1을 했어야 했다. 실수 금지 시간 초과 코드 ↓ // 시간 초과 코드 #include using namespace std; vector v; int N; long B; // m : 각 경우 마다, 최초 v에서 가장 낮은 성능이 올릴 수 있는 ..

https://softeer.ai/practice/info.do?idx=1&eid=1309 1. 정렬(sort) 및 이진탐색(upper_bound) 활용 2. 이진탐색한 인덱스를 문제에 제시된 순위(등수)에 맞게 다시 계산 3. 힌트 : 각 사람마다 “나보다 점수가 큰 사람”의 수를 세어 1을 더한 것이 자신의 등수가 된다. 4. 정렬한 벡터(또는 배열)과 입력한 순서를 기억할 벡터(또는 배열) 모두 활용 #include using namespace std; int N; vector v, p; int t[100001], tt[100001]; int main(int argc, char** argv) { scanf("%d", &N); for (int i = 0; i < 3; i++) { v.clear(); ..

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/..