https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 풀이 방향키로만 목표값인 n에 가는것을 초깃값으로 잡아준 뒤 0~1000000까지의 숫자 중 만들 수 있는 숫자들을 완전탐색하여 최솟값이 나올 수 있게 계속 비교해준다. 0

https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 풀이 라이브러리 itertools의 combinations(조합)을 사용하여 풀어주었다. # 6603번 로또 from itertools import combinations as comb while True: numbers = input().split() if numbers[0] == '0': break else: numbers = numbers[1:] for i in comb(numbe..

다익스트라 최단경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 다익스트라 최단경로 알고리즘은 '음의 간선'이 없을 때 정상적으로 동작한다. 다익스트라 알고리즘을 세팅할 때는 다음 단계를 거친다. 1, 주어진값으로 정확하게 그래프를 만들어준다. (양방향성인지 단방향인지, 혹은 최대값이 얼마나 나오는지) 2, 다익스트라 알고리즘을 사용해서 풀어준다. 뭐 이렇게 설명해놨냐고 따질 수 있지만 문제를 풀다보면 이게 전부라는 것을 알 수 있다. 그 다음에 시간 감축은 본인의 자료구조 활용도에 따라 달라지기에 이후는 푸는 사람한테 달려있다. 추가로 자료구조 힙을 쓰기에 힙에 대한 이해가 필요하다. INF를 대체로 int(1e..

https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 풀이 시작값과 목표값이 각 테스트케이스마다 주어진다. 시작값의 각 자리의 숫자를 바꿔가면서 소수를 유지하면서 목표값으로 바꿀 수 있는가? 1, 에라토스테네스의 체 알고리즘으로 1000 ~ 9999까지의 숫자들 중 소수만 뽑아서 리스트를 만들어준다.2, BFS를 실행해서 숫자의 각 자리를 1~9까지의 숫자로 바꿔가면서 목표값까지 이동할 수 있나 없나 확인한다.대신 첫방문이며 소수여야하고 1000이상인 숫자여..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 풀이 이분탐색 문제 # 백준 1654 # K개의 다른길이를 가진 전선들을 N개의 일정한 길이의 전선들로 만들어야한다. # 이분탐색을 위한 target, start, mid를 잡아준다. 이분탐색을 최댓값을 찾을때까지 진행된다. import sys input = sys.stdin.readline K, N = map(int, input().split()) # K개와 N개를 ..

고대 그리스 수학자인 에라토스테네스가 발견한 알고리즘이다. 그 시대에 어떻게 발견했나 싶네.. 여러개의 소수를 상대할 때 좋은 알고리즘이다. 소수는 1과 자기자신으로 밖에 나눠지지 않는 수이다. (1 제외) 숫자 N의 소수판별은 N을 N의 제곱근이하인 수로 나눴을 때 나눠지지않았을 경우 소수이다. # N 이하의 소수를 찾으려할 경우 # 소수는 1혹은 자기 자신으로 밖에 나눠지지 않는 수 이다. # 0 - N 까지를 표현해줄 리스트 생성 arr = [True for _ in range(N+1)] for i in range(2, int(N**0.5)+1): if arr[i]: for j in range(i*2, N+1, i): arr[j] = False # 0, 1은 소수가 아니기에 제외 print([i f..

https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 풀이 파이썬에는 math 라이브러리에 최대공약수와 최소공배수를 계산해주는 함수가 있다.최대공약수 = gcd(greatest common divisor)최소공배수 = lcm(least common multiple) # 2609번 최대공약수와 최소공배수 import math a, b = map(int, input().split()) print(math.gcd(a, b)) print(math.lcm(a, b)) 출력결과

골드 달성. 티어가 있는게 동기부여도 되고 좋은 것 같다. 아직 부족한 점이 많아서 더 노력해야한다.