재민의 IT 공부기록

https://www.acmicpc.net/problem/4504 목록안의 값이 초기값의 배수인지 아닌지를 판단하는 문제이다. #백준 4504: 배수 찾기n = int(input())while True: num = int(input()) if num == 0: break if num % n == 0: print(f"{num} is a multiple of {n}.") else: print(f"{num} is NOT a multiple of {n}.") 풀이법: While문을 이용하여 간단히 처리 할 수 있었다. 입력한 값에서 Mod연산을 한 결과 0으로 떨어진다면 배수이고, 아닐 시에는 예외처리를 함으로써 문제를 해결할 수 있었다.

https://www.acmicpc.net/problem/1005 위상정렬, 그리고 dp를 이용하여 푸는 문제이다. 위상정렬 개념에 대해 잘 몰라서 학습해보았다."위상 정렬(Topological Sort)은 방향 그래프의 모든 노드를 방향성을 지키며 순서대로 나열하는 알고리즘" 으로 정리할 수 있을 것 같다. 관련 개념에 대해 조금 더 공부해보면 좋을 것 같다. #백준 1005 : ACM Craft#필요 라이브러리 importimport sysfrom collections import dequeinput = sys.stdin.readlinet = int(input())for _ in range(t): n,k = map(int,input().split()) time = [0] + list(map(int,..

https://www.acmicpc.net/problem/6887 단순 계산 문제이다. 1부터 대입하면 된다고 생각했고, f-string을 이용하여 출력했다.#백준 6887: squaresn = int(input())a = 1while a ** 2 n: a += 1 print(f"The largest square has side length {a-1}.")

https://www.acmicpc.net/problem/1922 노드와 간선을 활용하여 비용의 합을 구하고, 출력하는 문제이다. "최소 스패닝 트리" 라는 문제라고 한다. 해당 문제를 풀기 위한 알고리즘은  "크루스칼 알고리즘" 이라고 함. 간선을 비용 순서로 정렬하여, 비용이 작은 간선부터 사이클이 생기지 않도록 연결하고, 사이클을 감지하는 식으로 진행한다. #백준 1922: 네트워크 연결import sysinput = sys.stdin.readlinedef find_parent(parent, x): if parent[x] != x: #if parent[x] != x: parent[x] = find_parent(parent, parent[x]) #parent[x] = find_parent(parent..

https://www.acmicpc.net/problem/2805  이분탐색 문제이다. " 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다. " 라는 부분에서   #백준 2805: 나무 자르기#import dictionary import sys#binary searchdef binary_search(start, end, target): while start end: mid = (start + end) // 2 sum = 0 for i in range(n): if tree[i] > mid: #if height of tree is bigger than mid sum += tree..

https://www.acmicpc.net/problem/12865 dp 문제이다.  #백준 12865: 평범한 배낭n,k = map(int,input().split())dp = [[0]*(k+1) for _ in range(n+1)]for i in range(1,n+1): w,v = map(int,input().split()) for j in range(1,k+1): #무게 1->k까지 if j w: #j가 w보다 작으면 dp[i][j] = dp[i-1][j] #이전값을 그대로 else: #j가 w보다 크거나 같으면 dp[i][j] = max(dp[i-1][j],dp[i-1][j-w]+v) #이전값 or 이전값에서 w를 뺀값+현재값 중 큰값으로 업데이트 print(dp[n][k]) 핵심 아이디어: ..

https://www.acmicpc.net/problem/1904  dp문제이다. #백준 1904 : 01타일import sysn = int(sys.stdin.readline())dp = [0] * 1000001dp[1] = 1dp[2] = 2for i in range(3, n+1): dp[i] = (dp[i-1] + dp[i-2]) % 15746print(dp[n])  풀이법: 다이나믹 프로그래밍 아이디어: 초기 타일값을 1,2로 준 다음, 3부터 n까지의 값은 dp값끼리 더하여 나눈 나머지 값들을 출력하도록 설정하였다.

https://www.acmicpc.net/problem/1011  단순한 계산 문제이다.  #백준 1011: Fly me to the Alpha Centaurit = int(input()) #테스트 케이스의 개수for _ in range(t): x, y = map(int, input().split()) distance = y - x count = 0 move = 1 #이동 횟수 move_sum = 0 #이동한 거리 while move_sum distance: #이동한 거리가 총 거리보다 작다면 count += 1 #이동 횟수 증가 move_sum += move #이동한 거리 증가 if count % 2 == 0: #이동 횟수가 2의 배수일 때 move += 1 #이동 거리 증가 print(count)..

다익스트라 알고리즘은 최단 경로 알고리즘 중 가장 많이 사용되는 알고리즘으로, 무방향 그래프와 방향 그래프 모두에서 사용 가능한 알고리즘이다.모든 간선은 음이 아닌 비용을 가진다는 가정을 바탕으로, 시작 정점으로부터 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값을 출력하여 값을 확인하였다.