백준(22)
-
[알고리즘/파이썬] 백준 2609번 - 최대공약수와 최소공배수
2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 최대공약수를 구하는 여러방법이 있는데 가장 유명한것은 유클리드 호제법. 단번에 이해되는 예시도 있으니 아래의 백과사전을 참고하자. 유클리드 호제법 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 � ko.wikipedia.org 최대공약수를 먼저 구하면 최소공배수는 쉽게 구할 수 있다. 이유는 최대공약수와 최소공배수는 아래와 같은 관계..
2020.09.06 -
[알고리즘/파이썬] 백준 2607번 - 비슷한 단어
2607번: 비슷한 단어 첫째 줄에는 단어의 개수가 주어지고 둘째 줄부터는 한 줄에 하나씩 단어가 주어진다. 모든 단어는 영문 알파벳 대문자로 이루어져 있다. 단어의 개수는 100개 이하이며, 각 단어의 길이는 10 이�� www.acmicpc.net 문제 이해하는데 한참 걸렸다. 책좀 더 읽어야겠다. 아래 코드처럼 모든경우의 수를 다 확인하는 방법으로 풀었다. 입력은 대문자만 된다고 했으니 대문자 32개를 입력받을수 있도록 했다. ( length가 32인 list에 0으로 초기화 ) 대문자는 아스키코드 65부터 시작하니까 입력받은 문자를 65로 나눈 나머지가 0이면 A, 나머지가 1이면 B 이런식으로 처리했다. 그후 구성이 같은지, 문자를 하나 뺐을때 같은지, 문자를 하나 더했을때 같은지, 기존 문자 ..
2020.09.01 -
[알고리즘/파이썬] 백준 11053번 - 가장 긴 증가하는 부분 수열
11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net { 1, 2, 1, 4, 3, 2 }라는 순열이 있을때 구할수 있는 증가 부분 수열이 몇가지 존재한다. 예를들면 [1 2] , [1 4], [1 2 3] , [1 2 4] 같은것들이다. 좌측부터 수를 뽑되(순열) 반드시 증가해야하며(증가) 주어진 순열내에 있는 숫자(주어진 순열의 부분)로 이뤄져있다. 위의 예시같은 경우는 3이 가장긴 부분 수열이다. ( [1 2 3] 또는 [ 1 2 4..
2020.07.27 -
[알고리즘/파이썬] 백준 11047번 - 동전0
11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 백준에서 그리디 알고리즘으로 분류된 문제. 매순간 최적의 답들을 구하다 보면 결국 결과도 최적의 값이 될거라는 접근법이다. 주어진 금액K를 최소한의 동전을 이용해서 구해야한다. 동전의 가치가 가장 높은것을 먼저 사용(최적의 값)해서 K를 줄여나가면된다. nk = list(map(int,input().split())) k = nk[1] coin = [] for _ in range(nk[0]): c = ..
2020.07.16 -
[알고리즘/파이썬] 백준 1157 - 단어공부
1157번: 단어 공부 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. www.acmicpc.net 64%에서 틀렸다면 단어 2개짜리 넣어서 다시 테스트해보자. # 모두 대문자로 word = input().upper() # 알파벳 한개만 입력된경우. if len(word) == 1 : print(word) quit() h_word = {} # 알파벳별 dict for i in set(word): h_word[i] = 0 # 알파벳별 사용횟수 for i in word: h_word[i] += 1 # value별로 dict 정렬 h_word = sorted(h_word.items(),reverse..
2020.07.15 -
[알고리즘/파이썬] 백준 2606 - 바이러스
https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어�� www.acmicpc.net 간단한 BFS문제. computers = int(input()) edge_num = int(input()) edges = [] for _ in range(edge_num): s,e = list( map(int,input().split())) edges.append([s,e]) que = [] visit = [] # 출발지 que.append(1) # BFS while True: # 큐가 비면 종료 ..
2020.07.14