기록장

문제https://www.acmicpc.net/problem/190400 또는 1을 총 n개 붙여서 만들 수 있는 이진수열의 개수를 구하는 문제풀이n을 1부터 5까지 늘려가며 어떤 수열이 만들어질 수 있는지 구해보면 규칙을 찾을 수 있다.n번째에 만들 수 있는 이진 수열의 개수 = (n-1번째에 만들 수 있는 이진 수열 개수) + (n-2번째에 만들 수 있는 이진 수열 개수) 이 규칙의 원리는 n-1번째에 만들어진 이진 수열의 맨 뒤에 '1'을 붙인 값들 + n-2번째에 만들어진 이진 수열의 맨 뒤에 '00'을 붙인 값들이 두 가지가 합쳐져서 n번째의 이진 수열이 만들어진다는 점을 고려하면 쉽게 찾을 수 있다. 오답노트문제에서 답을 출력할 때 숫자를 15746으로 나눈 나머지를 출력하라고 해서 최종 값에..

문제https://www.acmicpc.net/problem/11403 가중치 없는 방향그래프가 주어졌을 때, 모든 정점(i, j)에 대해 i->j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하라. 양수인 경로가 있으면 i행 j열의 숫자를 1로, 없으면 0으로 출력해야 한다. 입력:30 1 00 0 11 0 0풀이i행 j열의 값이 1이면 양수인 경로가 있다고 했으므로 입력으로 인접행렬이 주어진 것과 같다. 그런데 이 인접행렬은 정점 i에서 j로 바로 가는 경로가 있는가에 대한 정보이다.i에서 j로 바로 갈 수는 없지만 k를 거쳐서 가는 경로가 존재할 수도 있다. 이 경우를 찾아내야 한다. 노드 k는 그래프 상에서 i, j를 제외한 모든 노드가 될 수 있기 때문에 3중 for문을 돌리..

플로이드 워셜개념정점 i에서 j까지 가는 최단 경로를 구할 때 중간 정점을 거쳐서 갈 수 있으면 거쳐서 가는 게 더 빠른지 확인하면서 최단 경로를 구하는 알고리즘임의의 경로 p에 중간 정점 k가 존재하면 k를 거쳐 가는 경로와 비교하여 더 작은 값으로 갱신하고, 중간 정점이 존재하지 않으면 아무 것도 하지 않는다.여기서 알 수 있는 특징은 거쳐갈 중간 정점이 여러 개가 될 수 있는데, 중간 정점 개수가 늘어날 수록 경로가 더 다양해지고 더 짧은 경로를 발견할 수 있는 확률이 늘어난다는 것이다.그리고 중간 정점 후보가 {1, 2, 3, ..., k} 이렇게 존재한다면 중간 정점을 단계적으로 확장해나가며 점점 더 정교한 최단 경로를 계산해나간다.즉 경로를 점점 확장해가면서 가능한 모든 조합을 다 비교하고 있..