https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 1. 서론 아주 유명한 문제. 떠올리는 것에서 1차 고비, 구현하는 것에서 2차 고비가 온 문제다. 근데 막 엄청나게 어렵지는 않다!! 2. 문제 풀이 아주 전형적인 그래프 문제이다. 그래프가 주어지고 그걸 두 개의 구역으로 나누어서 그 그래프가 가지고 있는 값의 차가 가장 작은 값을 구하는 문제이다. 만약 나누는 것이 불가하다면 -1을 출력해야 한다. 입력에서 두 그래프가 연결되어 있다는 것을 0,1로 표시하는 것이..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 1. 서론 어렵지 않은 문제를 어렵고 풀고 n번의 경량화를 거쳐 남들과 비슷하게 풀었다^^ 이러면서 배우는 거겠지 ㅎㅎ 시뮬 + dfs(bfs) 문제이다. 2. 문제 풀이 맵에 각 좌표에 인구수가 주어진다. 한 좌표를 기준으로 동서남북의 좌표를 봤을 때 현재 위치 좌표와 이웃한 좌표의 차가 L~R 사이이면 이동할 수 있고, 아니면 이동할 수 없다. 이동할 수 있는 것을 기준으로 연합..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXQsLWKd5cDFAUo SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 서론 그래프 문제다. dfs로 풀었는데... 플로이드 워샬로 풀 수 있는 문제란다. (나중에 풀어봐야지. 안 풀어보겠지만.) 2. 문제 풀이 학생들의 키가 어쩌고 하지만 문제의 본질을 따져보면 아주 간단한 문제다. 결론은 각 학생마다 연결된 학생들을 구하고 그 학생들이 자신을 제외한 나머지 학생들의 목록과 같으면, 즉 모든 학생의 정보가 있다면 키가 몇 번째인지 알게 되는 것이다. 그래서 주어..

https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 1. 서론 골드2 치고는 그렇게 어렵지 않으나,, 난 답을 보는 순간까지도 문제를 제대로 이해하지 못했던 문제... ㅎ 2. 문제 풀이 가장 왼쪽 열에서 출발해서 가장 오른쪽 열에 도착할 때까지 파이프를 연결한다. 파이프는 현 위치에서 오른쪽, 오른쪽 대각선 위와 아래 세 군데만 설치 가능한다. 그러나 탐색 중 건물이 있는 경우에는 파이프를 연결할 수 없다. 가장 왼쪽 열에서 파이프를 연결해서 가장 오른쪽 열에 ..

https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 1. 서론 Level 3 답게 진짜 독한 문제다....(독한 건 이걸 못 푸는 나일지도^^) 처음에는 BFS네... 근데 어차피(?) 모든 곳을 방문해야 하니까 굳이 복잡하게 안 풀고 직관적으로 풀어야지 => 시간초과 걸림(오래 걸려서가 아니라 방향을 못 찾아서 무한 돌아서) 그리고 반례 찾아보다가 한 번만 다음 도착지가 있는지..

https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 1. 서론 dfs 문제라고 해서 풀었는데... 뭔가 풀이 방법을 못 찾겠어서 인터넷을 뒤져보니 dfs 백트래킹 문제란다. 쉽지 않다... 백트래킹이 정확하게 뭔지 알려준 문제. 내가 고민하던 부분을 시원하게 긁어줌! 그러고 level 3문제다. 2. 문제 풀이 words라는 단어의 배열이 주어진다. 그리고 begin과 ..