전체 글
백준 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으로 ..