재민의 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/2667 dfs & 그래프 순회 문제이다.  전역 변수를 설정하였고, 그래프에 방문하지 않았다면 방문시키고 dfs를 진행한다. 단지의 개수, 현재 단지의 크기, 각 단지의 크기를 나누어 저장하고, 각각 출력하는 방식으로 시행해보았다.  #백준 2667: 단지번호붙이기#dfsdef dfs(x, y): global count #global variable if x1 or x>=n or y1 or y>=n: #out of range return False if graph[x][y] == 1: #not visited graph[x][y] = 0 count += 1 dfs(x-1, y) dfs(x+1, y) dfs(x, y-1) dfs(x, y+1) re..

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/1932 백준 1932번 정수 삼각형 문제이다. dp를 이용하여 풀 수도 있고, 이용하지 않고 메모리를 아끼면서 풀이도 가능하다.  1)다이나믹 프로그래밍(dp) 이용# 백준 1932: 정수 삼각형n = int(input())triangle = []# 삼각형 입력 받기for _ in range(n): triangle.append(list(map(int, input().split())))# dp 배열 초기화dp = [[0] * n for _ in range(n)]dp[0][0] = triangle[0][0] # 첫 번째 값 입력# dp 배열 업데이트for i in range(1, n): # 1부터 시작 (0은 위에서 이미 입력했음)!! for j i..

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/25306  xor(exclusive OR) 문제이다. 처음에 문제의 조건을 자세히 읽어보지 않고, a부터b까지의 값을 모두 대입하여 계산하면 되겠다는 생각을 하였다.#백준 25306: 연속 XORimport sysA, B = map(int, sys.stdin.readline().split())result = 0for i in range(A, B + 1): result ^= iprint(result)  모두 대입하여 푼 결과, 결과값은 잘 출력되었지만 (문제에서 주어진 예시) 시간 초과가 발생하였다. # 백준 25306: 연속 XORimport sysA, B = map(int, sys.stdin.readline().split())def xor(n)..

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값끼리 더하여 나눈 나머지 값들을 출력하도록 설정하였다.