처음에 타임머신 & 웜홀 문제 컨셉을 이해하는데 응? 시간이 거꾸로 가 ? 무슨말이지;; 이랬는데 이말인 즉슨, 가중치가 음수일 수 있다라는 의미이다 즉, 우리는 최단거리를 구해야 하는데, 다익스트라 방법에서는 음수인 value가 주어지지 않았었다. 음수인 가중치가 주어지면 ?? 바로바로 우리가 알고리즘 시간에 배웠지만 망각했을 가능성이 큰 Bellman-Ford 방법을 떠올려야 한다 !! 다익스트라와 방법은 유사하나, 다른점은 노드를 하나씩 돌면서, 최단거리를 갱신해주는 작업을 v-1 번만 수행해야 한다는 점이다 v-1 번 이상일때도 값이 바뀐다는 뜻은 바로 cycle을 돌고 있다는 뜻이다 .. # 11657 타임 머신 n, m = map(int, input().split()) INF = int(1e9..
Algorithm (PS)
https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 풀면서 삼성기출이어서 무슨 함정이 있는거아니야?!?!!?! 이렇게 쉬울리가 없어 !!!!! 라고 생각하며 풀었는데 쉽게 풀수 있는 수학 문제이다 총감독관은 무조건 ! 한명을 배치해야하니까 이왕 이렇게 된거 처음에 한번씩 빼고 시작한다 그 후 c 값으로 나누어서, 나머지가 있는경우 없는 경우로 나누어서 필요한 부감독관의 수를 계산해주면 된다...
10870 의 피보나치 문제는 메모이제이션을 활용한 DP 풀이로 시간 제한 & 메모리 제한을 넘길 수 있었다 n = int(input()) dp = [0]*21 dp[0] = 0 dp[1] = 1 def fibo(n): for i in range(2, n+1): dp[i] = dp[i-1] + dp[i-2] return dp[n] print(fibo(n))
Selection Sort : 현재 배열중에 가장 작은 원소를 고른다. 3 5 1 8 2 9 가장 작은 원소와 현재 인덱스의 원소의 자리를 바꾼다. 1 5 3 8 2 9 가장 작은 원소는 이미 정렬된 것이므로, 그 다음원소부터 n-1번까지 확인하여 가장 작은 원소를 고른다. 1 5 3 8 2 9 --------- 1을 제외하면 2가 가장 작은 원소이다. 1 2 3 8 5 9 --------- 1, 2 까지는 정렬된 것이다. 1 2 3 8 5 9 --------- 1, 2, 3 까지는 정렬되었다. 이 경우 3은 자리를 바꾸지 않아도 된다. 1 2 3 5 8 9 --------- 5 8 9 중에 가장 작은 수는 5이므로 8과 5의 위치를 바꿨다. 1 2 3 5 8 9 ---------- 9 를 제외한 나머지..
https://programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 오랜만에 해시 유형을 풀어보았다 !! 오랜만이라서 딕셔너리 쓰는 방법을 까먹었다,,, i ) key 로 value 가져오기 : get() Python 에서 key를 이용하여 딕셔너리의 value를 가져오려면 get() 함수를 사용하면 된다. 그런데 아주 편리한 점은, get(key값, default값) 현재 key 가 딕셔너리에 없으면 def..
https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 1. 우선 graph의 원소들을 초기화 한다 ! 2. 나는 n ==3 이면 가장 기본 모양의 삼각형이므로, n==3 이면 별 모양을 넣어주는 걸로 풀었다 n==3일때의 삼각형 모양이 반복되어 만들어지기 때문이다 !! 3. n==3 일때 별을 찍고, 이 모양이 반복되므로, x좌표와 y좌표값을 찾아서 반복해 주면 되는데, 그것이 star 함수를 재귀 호출 한 부분이다 왼쪽 아래 부분, 오른쪽 아래 부분, 그리고 현재 x,y 부분을 나눠서 별을 찍는다고 ..
data = list(map(int, input())) data.sort(reverse=True) print("".join(map(str, data))) 그냥 쉬어가는 차원에서 풀어봄
https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 짜잔 이렇게 dp 테이블을 그려서 dp[i][j] = dp[i-1][j] + dp[i][j-1] 라는 점화식을 도출해내면 끝이다 단 i -1 > 0, j -1> 0 이어야 하므로 i, j 는 각각 2이상이어야 한다 !! 그러기 위해서는 dp[?][1] 은 n (자기자신) 값으로 초기화 해주어야 하고 dp[1][?] 는 1로 초기화해주어야 한다 # 2225 합분해 n, k = map(int, input().split()) dp = [[0] * 201 for _ in range(201)] for i in range(1, 201..
