분류 전체보기
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..
BOJ 15684 - 사다리 조작
www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 처음에 dfs 로 처리하려고 했으나, 사다리가 끝에 도달 했을때, 끝나지 않고 다른 지점을 방문하는 오류를 계속 범하고 있어서 통과하지 못했다. dfs 는 한쪽을 쭉 다 방문한 다음 다른 쪽을 방문하여 전체를 다 방문하는 것인데 문제풀때, dfs 에 대한 개념 자체를 모호하게 이해하고 있었던것 같다. 답을 못 찾다가 다른 분들의 풀이를 보고서 이해하게 되었다. 1. 전체 놓을 수 있는 가로선의 사다리 중 최대..