PS
BOJ 16234 - 인구 이동
www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 이문제를 처음 풀때는 BFS 를 수행하면서 두 국가의 인구수 차이가 L 이상 R 이하인 (즉, 국경선을 열수있는) 국가들에게 동일한 번호의 라벨을 부여하여 BFS 가 끝나면, 각 라벨 번호에 맞는 인구수 총합 / 국가의 갯수로 배열을 갱신해주었다. 그러나 80% 정도에서 시간초과가 나서 통과하지 못했다. (아래의 코드가 통과 못한 코드) - c++ #include #include #include ..
BOJ 2580 - 스도쿠
www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 처음에는 아래 코드 처럼 푼게 아니라 이차원 배열을 이중포문으로 순회하면서 0 인 지점이 나타나면 백트래킹 함수로 진입하여 백트래킹 함수 내에서 가로줄에 쓰인 숫자, 세로줄에 쓰인 숫자, 현재 좌표가 소속된 3 * 3 크기의 정사각형에 쓰인 숫자를 찾아내서 가능한 숫자들을 추려낸뒤에, 가능한 숫자들을 가지고 현재좌표에 백트래킹을 시도하는 방식으로 하려고 했다. (마치 아래 블로그 분과 유사한 느낌으로 접근하려 ..
BOJ 1987 - 알파벳
www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net DFS 와 Backtracking 을 혼합해서 풀어야 하는 문제였다. DFS 로 (y, x) 지점을 방문하면서 이동할 수 있는 지역이 있으면 이동할 수 있는 새 지역 (ny, nx) 에 대해서 DFS 를 수행해준다 그리고 DFS 가 끝나는 때에 다시 초기 상태로 돌려놓는 백트래킹을 수행한다. 최대한으로 이동할 수 있는 칸의 수를 찾아내야 하므로 DFS 를 돌릴 때, y, x 좌표 뿐 아니라, cnt 라는..
BOJ 5430 - AC
www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 덱을 사용해서 풀었던 문제다. 역으로 뒤집을때, algorithm 헤더의 reverse 함수를 쓰면 시간초과가 발생한다 reverse 의 시간복잡도가 O(N) 이기 때문이다. 뒤집는것 대신에, bool 변수를 이용해서 뒤집혔는지 여부를 파악하고 뒤집히지 않았으면 앞에꺼를 빼는 pop_front() 를 하고 뒤집혔으면 뒤에꺼를 빼는 pop_back() 을 한다. 그리고 비어있는 덱에서 빼려고 할때, 에러임을 나타내는 bool 변수를 하나 만들어서 체크한다 명령어를 다 ..
BOJ 11403 - 경로 찾기
www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 플로이드 와샬 알고리즘 그대로 쓰되, i 번째에서 j 번째 노드로 이동 가능하면 1로 그렇지 않으면 0으로 출력해주면 된다. 최단거리를 출력하는게 아니라 그냥 이동 가능한지 아닌지만 보는 문제. - c++ #include #include #define MAX 100 #define INF 1e9 using namespace std; int n; int dist[MAX][MAX]; int main() { cin.tie(0); ios_base::sync_wi..
BOJ 11404 - 플로이드
www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드 와샬 알고리즘은 그래프 상에서 모든 정점 쌍 사이에 최단거리를 갱신하는 알고리즘으로, O(V^3) 의 시간 복잡도를 갖는 알고리즘이다 (V 는 노드의 갯수) 플로이드 와샬 알고리즘의 핵심은 정점 A 에서 B 로 가는 최단거리를 구하되, 중간에 거쳐가는 다른 정점 C 를 거쳐가면 A 에서 B 로 가는 최단거리가 더 줄어 들 수 있느냐 이다. 플로이드 와샬 알고리즘의 특징은 음의 가중치를 갖는 그래프에서도..
BOJ 15685 - 드래곤 커브
www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 방향 회전에 대한 부분을 도통 어떻게 처리해야 될지 감을 못잡다가 다른 블로거 분들의 해설을 보고 이해하게 되었다. k번째 세대의 드래곤 커브는 k - 1 번째 세대의 드래곤 커브의 방향 값을 역순으로 +1 하면서 나열하여 이어 붙이는 식으로 찾아낸다. 문제에서 방향에 대한 값을 다음과 같이 정의했다 0 : 오른쪽 방향, 1 : 위쪽 방향, 2 : 왼쪽 방향, 3 : 아랫쪽 방향 문제..
BOJ 11286 - 절댓값 힙
www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 우선순위 큐에 less, greater 대신에 별도의 비교 연산을 위한 구조체를 정의해서 넣으면 된다. - c++ #include #include #include using namespace std; int n; struct compare { bool operator()(const int& num1, const int& num2) { if (abs(num1) != abs(num2)) ret..