전체 글

백준 11724번: 연결 요소의 개수

문제 링크: https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. www.acmicpc.net 아이디어 : DFS 이것은 정점 기준으로 방문체크해주면서, Main 문에서 실행 한 DFS 카운트 횟수를 계산하는 것이 포인트. 의견 : BFS를 풀고 싶어서 찾은건데, DFS로 푸는 것이 맞다 생각했다. 그리고 DFS 기본 구현을 하면 풀 것 같다. #include #include using namespace st..

백준 11403번: 경로 찾기

문제 링크 : https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 아이디어 : BFS 한 줄을 탐색하면서, 값이 1인 것인 정점을 기준으로 탐색함. 그래서 답으로 사용할 배열의 값을 1로 변경. #include #include #include #include using namespace std; int N; int nMap[101][101]; int nAns[101][101]; int nChecked[101][101]; queue q; void BFS(int y) { q.push(y); w..

백준 7562번: 나이트의 이동

문제 링크 : https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 입력 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ... www.acmicpc.net 아이디어 : BFS 현재 위치에서 나이트가 갈 수 있는 곳을 Queue에 넣고 돌린다. 항상 문제는 BFS 돌리더라도..

다이나믹 프로그래밍(Dynamic Programming)

다이나믹 프로그래밍이란 하나의 문제를 단 한 번만 풀도록 하는 알고리즘? 다이나믹 프로그래밍은 다음의 가정 하에 사용할 수 있습니다. 1번. 큰 문제를 작은 문제로 나눌 수 있습니다. 2번. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일합니다. 그것을 먼저 잘게 나누어서 해결한 뒤에 처리하여 나중에 전체의 답을 구한다. --> 분할 정복과 애매하게 다른 느낌이다? 이 과정에서 메모이제이션이 사용된다는 점에서 다르다고 합니다. --> 이미 계산한 결과는 배열에 저장함으로써 나중에 동일한 계산을 해야 할 때는 저장된 값을 단순히 반환하기만 하면 되는 것. 대표적으로 피보나치 수열을 문제로 다이나믹 프로그래밍으로 해결해본다. #include int d[100]; long long dp(int ..

이진 트리의 구현과 순회 방식

이 챕터는 알고리즘보다는 자료구조에 가까운 것 같아 자료구조 게시판에 게시한다. 이진 트리는 대표적인 비선형 자료구조이다. 완전 이진 트리와 이진 트리의 차이를 분명히 하고 넘어가야 한다. --> 나도 처음에 배열로 표현하면 될 것 같은데? 라고 생각했는데 여기서 할 것은 !이진 트리! 이다. 충분히 배열로 표현이 가능하나, 오른쪽에만 노드가 이어져있다 생각해보면 메모리 낭비가 심하다고 생각할 수 있다. 순회 방식은 3개 있다. 1. 전위 순회 (1) 먼저 자기 자신을 처리. (2) 왼쪽 자신을 방문 (3) 오른쪽 자식을 방문 2. 중위 순회 (1) 왼쪽 자신을 방문 (2) 먼저 자기 자신을 처리. (3) 오른쪽 자식을 방문 3. 후위 순회 (1) 왼쪽 자신을 방문 (2) 오른쪽 자식을 방문 (3) 먼저..