뭥미

백준 1325번: 효율적인 해킹

문제링크: https://www.acmicpc.net/problem/1325 1325번: 효율적인 해킹 첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다. www.acmicpc.net 전형적인 DFS문제 어렵지 않다. 사실 정답률 보고, 얼마나 오래 걸릴까 걱정했는데 1시간? 30분? 이렇게 푼 것 같다. 그러나 문제를 착각할 수가 있다. A가 B를 신뢰한다 == 서로가 서로를 신뢰하다고 보면 안된다. 그래서 벡터에 넣어놓고 보면 방향성이 있는 그래프로 확인할 수 있다..

백준 1963번: 소수 경로

문제 링크: https://www.acmicpc.net/problem/1963 1963번: 소수 경로 문제 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야" “그럼 8179로 해” “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. www.acmicpc.net 아이디어 : 1. 에라토스테네스의 체를 통해 10000이하 소수를 구한다. 2. 한 자리 씩 바꿔가며, 소수가 가능한 경우의..

백준 1389번: 케빈 베이컨의 6단계 법칙

문제 링크: https://www.acmicpc.net/problem/1389 불러오는 중입니다... 아이디어 : 플로이드 와샬 알고리즘 의견 : 처음에는 DFS에 분류되어 있어, DFS로 풀려했는데, 도저히 안돼서 플로이드 와샬로 품. #define MAX_INF 100000 #include #include #include using namespace std; int nGraph[101][101]; int N, M; void FloydWarshall() { for (int k = 1; k > M; int nFriend1, nFriend2; for (int i = 1; i > nFriend1 >> nFriend2; nGraph[nFriend2][nFriend1] = 1; nGraph[nFriend1][n..

플로이드 와샬(Floyd Warshall) 알고리즘

다익스트라 알고리즘처럼 최단 경로 구하는 알고리즘이다. 차이점은, 모든 정점에서 모든 정점으로의 최단 경로를 구한다는 것. --> 다익스트라 알고리즘은 따로 게시글을 포스트할 예정입니다. 플로이드 와샬 알고리즘은 기본적으로 '거쳐가는 정점'을 기준으로 알고리즘을 수행한다는 점. 그리고 플로이드 와샬 알고리즘은 기본적으로 다이나믹 프로그래밍 기술에 기반을 두고 있습니다. 코드를 보면, 초기 경로에 대한 값을 넣어 초기화해줍니다. INF는 무한 값을 대체한 값입니다. 3중 for문으로 구현해, 최단 경로에 대한 비용을 갱신합니다. #include int number = 4; int INF = 10000000; int a[4][4] = { {0, 5, INF, 8}, {7, 0, 9, INF}, {2, INF..

에라토스테네스의 체

에라토스테네스의 체는 대표적인 소수(prime) 판별 알고리즘이다. --> 지금까지 for문 돌려서 약수 있으면 break 하는식으로 했다. --> 더군다나 이 알고리즘은 중학교 수학에서 배울 수 있다고한다.. 먼저 언급했던 for문을 돌려 1과 본인을 제외한 약수가 있다면, break 하는 방법은 시간 복잡도 O(N)을 가지고 있다. 에라토스테네스의 체를 사용하면, O(N^(1/2))의 시간복잡도를 가진다고 한다. 에라토스테네스의 체의 중점은 특정한 숫자의 제곱근까지의 약수의 여부를 검증하는 방식이다. 에라토스테네스의 체를 구현하는 방법은, 1. 이차원 배열을 생성하여 값을 초기화. 2. 2부터 시작해서 특정 숫자의 배수에 해당하는 숫자들을 모두 지움. --> 지운다는 의미는 해당 배열의 값을 0으로 ..

백준 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) 먼저..