재민

다익스트라 알고리즘은 최단 경로 알고리즘 중 가장 많이 사용되는 알고리즘으로, 무방향 그래프와 방향 그래프 모두에서 사용 가능한 알고리즘이다.모든 간선은 음이 아닌 비용을 가진다는 가정을 바탕으로, 시작 정점으로부터 G의 모든 다른 정점까지의 최단 경로를 구하는 것을 목표로 한다. 다익스트라 알고리즘의 개념은 다음과 같다. 시작 정점 v에서 정점 u까지의 최단 경로 dist[u]를 구해 정점 u가 집합 S에 추가되면 새로 추가된 정점 u에 대해 단축되는 경로가 있는 지를 확인한다. 현재 알고 있는 dist[w]를 새로 추가된 정점 u를 거쳐서 가는 dist[u] + cost[u][w]를 계산한 경로를 비교해 경로가 단축되면 dist[w]를 단축된 경로값으로 수정함으로써 최단 경로를 찾는다. [python..

퓨리에 변환과 역 퓨리에 변환을 구현하는 예제이다. 함수를 구현하기 위해 numpy library를 import하고, DFT와 IDFT를 정의해주었다. DFT함수에서 N은 입력신호의 길이, n은 배열, k는 열벡터, M은 지수 행렬이다. 행렬은 M과 X를 내적한 값으로 이루어진다. IDFT함수에서도 마찬가지로 N,n,k는 동일하고, M도 DFT에서의 식과 유사하지만 N으로 나눈다는 점이 다르다. 행렬은 M과 X를 내적한 값으로 이루어진다. 저장된 DFT, IDFT값을 출력하여 값을 확인하였다.

https://www.acmicpc.net/problem/2822 2822번: 점수 계산 8개 줄에 걸쳐서 각 문제에 대한 참가자의 점수가 주어진다. 점수는 0보다 크거나 같고, 150보다 작거나 같다. 모든 문제에 대한 점수는 서로 다르다. 입력으로 주어지는 순서대로 1번 문제, 2번 문 www.acmicpc.net 백준 2822번 문제인 점수계산 문제이다. 8개의 입력값을 받아, 최대값 5개의 합을 출력하고 그들의 인덱스를 찾아 인덱스 번호를 공백없이 출력해야 한다. #백준 2822 점수 계산 scores = [] for i in range(8): score = int(input()) scores.append((score,i)) scores.sort(reverse=True, key=lambda x: ..

행렬의 성분을 부분적으로 출력하는 것과, 행렬의 일부 값을 변경하여 출력하는 예제이다. numpy를 import 한 후, np.array에 행렬을 삽입한다. 1행 3열의 성분을 출력하기 위해 E[0,2] 를 1행 3열의 값으로 지정한다. (**행렬의 저장공간은 0번부터 시작!) 마찬가지로 2행 1열의 성분은 E[1,0] 이 된다. 그리고 부분행렬을 출력한다. 2행 1열 성분을 변경하는 것은 E[1,0] = -1로 재 설정하면 된다. 그리고 행렬을 출력하면 정상적으로 변경된 값으로 출력됨을 볼 수 있다.

행렬에서의 기본 연산에 관한 예제이다. 파이썬으로 행렬의 덧셈, 행렬의 뺄셈, 행렬의 곱셈을 구현해보려고 한다. 행렬의 정의를 함수를 통해 구현해보았다. n * m 행렬을 구현하기 위해 이중 for문을 이용하여 공백란과 가로, 세로열을 규정하였다. 그리고 lone을 출력한 후 각 행렬에 값들을 삽입하였다. 행렬이 모두 삽입된 상태에서 행렬의 출력은 각 행렬을 정의해줌으로서 이루어질 수 있다. 같은 행렬의 덧셈과 곱셈은 상수 덧셈과 곱셈과 같은 방식으로 이루어질 수 있지만, 다른 행렬이 곱해질 경우에는 np.dot(행렬1, 행렬2)의 방식으로 행렬의 곱을 계산하게 된다. 한 행렬의 제곱 행렬은, np.linalg.matrix_power(행렬, 원하는 차수) 를 이용하여 이루어진다. 위의 행렬식을 실행해본 ..

https://www.acmicpc.net/problem/5597 5597번: 과제 안 내신 분..? X대학 M교수님은 프로그래밍 수업을 맡고 있다. 교실엔 학생이 30명이 있는데, 학생 명부엔 각 학생별로 1번부터 30번까지 출석번호가 붙어 있다. 교수님이 내준 특별과제를 28명이 제출했는데, www.acmicpc.net 백준 5597번 문제이다. 1번부터 30번까지 번호 가운데 출력되지 않은 2개의 번호만 찾아내어 출력시키는 문제이다. # 백준 5597 a = list(range(1,31)) for i in range(28): a.remove(int(input())) for i in a: print(i) 이를 위해 전체 수를 list값으로 받는다(1~30) 그리고 전체 리스트에서 입력값을 뺀다음, 빼..

https://www.acmicpc.net/problem/10807 10807번: 개수 세기 첫째 줄에 정수의 개수 N(1 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 정수가 공백으로 구분되어져있다. 셋째 줄에는 찾으려고 하는 정수 v가 주어진다. 입력으로 주어지는 정수와 v는 -100보다 크거 www.acmicpc.net BOJ의 기본 리스트 문제이다. # 백준 10807 N = int(input()) N_list = list(map(int,input().split())) v = int(input()) print(N_list.count(v)) 문제의 조건에 따라 N의 개수를 입력받는다. 그리고 N_list를 map 형식으로 들어올 수 있게 설정한다. 다음으로 v값을 입력받는다. (v값은 특정 정수값) ..

https://www.acmicpc.net/problem/10988 10988번: 팰린드롬인지 확인하기 첫째 줄에 단어가 주어진다. 단어의 길이는 1보다 크거나 같고, 100보다 작거나 같으며, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net 백준의 10988번 문제이다. 팰린드롬이란 앞으로 읽을 때와 뒤로 읽을 때가 같은 단어이다. 앞부터 읽는다는 표시는 [::1]로 표현하며, 뒤에서부터 읽는다는 표기는 [::-1]로 진행한다. #백준 10988 N = input() if N[::1] == N[::-1]: print(1) else: print(0) [::1] 값이 [::-1]과 같다면 1을, 그렇지 않다면 0을 출력하게 설정하여 출력하였다.

https://www.acmicpc.net/problem/10214 백준의 10214번 야구 문제이다. 문제의 요점은, 회차별 득점 금액을 입력받아, 저장하고, 9회가 마무리 되었을 시점에 총 득점을 비교하여 승자를 출력하는 것이다. #정답 코드 #백준 10214 T = int(input()) for _ in range(T): yonsei_total_score = 0 korea_total_score = 0 for _ in range(9): yonsei_score, korea_score = map(int,input().split()) yonsei_total_score += yonsei_score korea_total_score += korea_score if yonsei_total_score > korea..

첫째 줄에 n이 주어지면 n번째 수를 구하는 예제이다. n = int(input()) a,b = 0, 1 for i in range(n): a,b = b, a+b print(a) n값을 인풋으로 받는다. 그리고 초기값 a,b를 0,1로 둔 뒤 반복문을 사용하여 b, a+b가 차례대로 쌓이게 한다. 그리고 a를 출력해주면 정상적으로 출력됨을 볼 수 있다.