본문 바로가기

Algorithm/BOJ

(36)

[BOJ] 국회의원 선거(#1417) 코드 n = int(input()) dasom = int(input()) arr = [int(input()) for _ in range(n-1)] cnt = 0 if n == 1: pass else: while dasom 처음에 나는 순서대로 모든 후보자의 득표수에서 하나씩 빼서 다솜이의 득표수에 더하는 방법을 선택하였는데, 생각해보니 문제에서 순서대로 사람을 매수하라고 적혀 있지 않았다는 것을 알게 되었다. 그러니 그냥 최다득표자의 득표수를 계속 빼서 최다 득표자가 다솜이 될 때까지 사람을 매수하면 해결되는 문제였다. 1417번: 국회의원 선거 첫째 줄에 후보의 수 N이 주어진다. 둘째 줄부터 차례대로 기호 1번을 찍으려고 하는 사람의 수, 기호 2번을 찍으려고 하는 수, 이렇게 총 N개의 줄에 걸쳐 ..

[BOJ] 한국이 그리울 땐 서버에 접속하지 코드 t = int(input()) imp = input().split('*') for _ in range(t): word = input() if len(word) >= len(imp[0]) + len(imp[1]): if word[0:len(imp[0])] == imp[0] and word[-1 * len(imp[1]):] == imp[1]: print("DA") else: print('NE') else: print('NE') 분석 > 거의 다 풀었는데, imp[0]과 imp[1]의 길이를 더했을 때 word의 길이보다 작은 경우를 놓쳐서 계속 문제를 풀지 못하였다. 예를들어, ab*bc 이고 word가 abc인 경우 이는 옳지 못하기 때문에 예외처리를 해주어야 한다. 나는 이 중복된 문자를 어떻게 처..

[BOJ] 듣보잡 코드 a,b = map(int,input().split()) arr = [input() for _ in range(a)] imp = [input() for _ in range(b)] arr = set(arr) imp = set(imp) result = sorted(list(arr&imp)) print(len(result)) for k in result: print(k) 분석 > 간단한 문제였지만 set 함수를 쓰지 않으면 시간초과가 나는 문제였다. 문제를 풀면서 set함수끼리 겹치는 원소만 추출할 때에는 sorted(list(a&b)) 같이 코드를 적으면 된다는 것을 알게 되었다. 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄..

[BOJ] 비슷한 단어 해설 코드 N = int(input()) compare = list(input()) ans = 0 for _ in range(N-1): compare_word = compare[:] check_word = list(input()) for _ in range(len(check_word)): a = check_word.pop(0) if a in compare_word: compare_word.remove(a) else: check_word.append(a) A = len(compare_word) B = len(check_word) if (A==0 and B==0) or (A==1 and B==0) or (A==0 and B==1) or (A==1 and B==1): ans += 1 print(ans) 분석 ..

[BOJ] 랜선 자르기 나의 코드 a,b = map(int,input().split()) arr = [int(input()) for _ in range(a)] k = 1 ans = [] while True: imp = [] for num in arr: t = num // k imp.append(t) k += 1 if sum(imp) == b: break while True: ans = [] k += 1 for num in arr: ans.append(num//k) if ans != imp: break print(k-1) 분석 > 시간초과 날 것을 알고 있었지만, 효율성을 제외하고 일단 문제를 풀어보기 위해서 풀어보았다. 당연히 결과는 시간초과. 해설 코드 a,b = map(int,input().split()) arr = [in..

[BOJ] 가장 긴 증가하는 부분 수열 코드 t = int(input()) num = list(map(int,input().split())) dp = [1] * t for i in range(t): for j in range(i): if num[i] > num[j]: dp[i] = max(dp[i],dp[j]+1) # 현재의 dp값과 이전 수의 dp값에 1을 더한 값을 비교 후 더 크면 갱신 print(max(dp)) 분석 > LIS(Longest Increasing Subsequence) 알고리즘으로 원리는 간단하다. 현재의 수 (num[i]) 가 비교대상이 되는 이전의 수 (num[j]) 보다 클 때만, 비교 대상이 되는 수의 dp값에 1을 더한 값을 갱신하는 것이다. 그렇게 이전의 수들을 모두 탐색하면, 최종적으로 현재 수의 dp값은 이..

[BOJ] 올림픽 코드 a,b = map(int,input().split()) world = [] for _ in range(a): num = list(map(int,input().split())) world.append(num) world.sort(key = lambda x: (x[1],x[2],x[3]),reverse=True) for i in range(len(world)): if world[i][0] == b: index = i for i in range(len(world)): if world[index][1:] == world[i][1:]: print(i+1) break 분석 > 새롭게 알게 된 개념 중 하나는, 배열을 순서대로 기준을 정해서 정렬을 할 때 (x[1],x[2],x[3]) 와 같이 람다함수를 이용해..

[BOJ] 공통 부분 문자열 문제 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다. 두 문자열 ABRACADABRA와 ECADADABRBCRDARA의 공통 부분 문자열은 CA, CADA, ADABR, 빈 문자열 등이 있다. 이 중에서 가장 긴 공통 부분 문자열은 ADABR이며, 길이는 5이다. 또, 두 문자열이 UPWJCIRUCAXIIRGL와 SBQNYBSBZDFNEV인 경우에는 가장 긴 공..

이전 1 2 3 4 5 다음

티스토리툴바