기술 블로그

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

https://www.acmicpc.net/problem/17471 공부겸 오랜만에 풀어본 문제다. #include using namespace std; /* 1. 두 선거구로 나누기 - 백트래킹 2. 각 선거구 내 구역들이 인접한지 check - bfs 3. 모두 인접해있다면, 두 선거구의 총인구합 구하기 - 구현 */ int N, person[11]; // person[i] : i번째 구역 인구 수 int ans = 2e9; vector v[11]; bool used[11], num[11]; bool chk(vector a, vector b) { memset(used, false, sizeof(used)); queue q; used[a[0]] = true; q.push(a[0]); // a선거구 내에..

https://www.acmicpc.net/problem/9935 stack을 활용한다. 1. 입력받은 문자열을 활용하여, for문을 수행한다. 입력받은 문자열의 문자를 stack에 push한다. 2. 현재 for문의 문자가 폭발 문자열의 마지막 문자와 같은지 비교한다. 3. 같으면, 위의 1번 stack에 담긴 문자를 하나씩 비교한다. #include using namespace std; int len; string s, t; stack st; int main() { cin.tie(0); cin >> s >> t; len = t.length(); for (auto c : s) { st.push(c); // 입력받은 문자열을 for문 돌려준다 // 현재 문자와 폭발문자열의 마지막 문자가 같으면 if (c..

https://www.acmicpc.net/problem/15683 오랜만에 풀어본 대표적인 구현 및 시뮬레이션 문제이다. #include using namespace std; #define MAX 10 int Map[MAX][MAX]; int R, C, m[MAX][MAX], ans = INT32_MAX; int loop[6] = { 0, 4, 2, 4, 4, 1 }; int dy[4] = { 0, 1, 0, -1 }; int dx[4] = { 1, 0, -1, 0 }; vector v; bool chk(int Y, int X) { return (0

https://www.acmicpc.net/problem/2660 INF를 처음에 2e9로 했는데 계속 fw[i][j]의 값이 쓰레기 값으로 출력됐다. 1000으로 수정하니 해결됨. #include using namespace std; #define MAX 55 #define INF 1000 int fw[MAX][MAX]; int score[MAX]; int n, a, b; vector v; int main() { cin.tie(0); for (int i = 1; i < MAX; i++) { for (int j = 1; j < MAX; j++) { fw[i][j] = i == j ? 0 : INF; } } scanf("%d", &n); while (true) { scanf("%d %d", &a, &b);..

※ 아래 문제도 풀어보자.(회의실 개수 최댓값 구하기) https://www.acmicpc.net/problem/1931 https://www.acmicpc.net/problem/11000 강의실 개수 최솟값을 구하는 문제이다. 시작시간 기준으로 오름차순 정렬한다. 우선순위 큐를 활용하여, 종료시간을 넣어주면서 시작시간을 활용한다. #include using namespace std; int N; vector v; int main() { //freopen("C:\\Users\\park7\\Desktop\\lazy_bronze\\2.in", "r", stdin); cin.tie(0); scanf("%d", &N); int S, T; for (int i = 0; i < N; i++) { scanf("%d %..

※ 이 문제는 1차원 배열에 대한 문제이고, 2차원 배열로 확장시킨 문제가 2021년 9월 11일 토요일 2022 카카오 블라인드 코딩테스트 6번에 출제됐다. ※ 이 글은 안즈님의 카카오 6번 문제 해설(누적합을 이용한 연산)을 참고하여 작성하였고, 제가 다시 편히 보기 위해 정리하였습니다. https://www.acmicpc.net/problem/19951 배열이 주어지고, 배열의 구간에 수를 더하고 빼는 쿼리가 있다. 세그먼트 트리를 이용해도 되지만, 우리는 연산 중간에 배열의 값을 알 필요가 없고, 모든 쿼리(연산) 이후에 마지막 단 한 번만 구하면 되기 때문에, 누적합을 이용할 수 있다. 문제에 대한 정답 코드는 맨 아래에 있다. 이 문제를 풀기 위한 누적합 연산 개념 설명(아래 사진)을 추가한다..