아이테킨의 끄적끄적

오랜만에 코딩테스트 문제를 다시 풀어보았다. 곱셈의 값들이 각각 가장 작게 되도록 만드는 방법을 생각하는 것이었다. 가장 큰 값에 가장 작게 곱셈을 해줄때 최종 합이 가장 작을것이라는 아이디어로 풀어보았다. 각 리스트를 정방향, 역방향으로 정렬한 후에 excel에서 쓴 sumproduct를 구현해보았다. [x*y for (x,y) in zip(list_1,list_2)] 이 부분이 sumproduct인데 알아두면 두고두고 유용하게 써먹을 코드가 될 것 같다. # 1026 보물 n = int(input()) # 각 데이터를 공백으로 구분하여 입력값을 받는다. list_1 = list(map(int, input().split())) list_2 = list(map(int, input().split())) l..

그리디 문제에서 가장 대표적인 거스름돈 동전 문제이다. # 2720 세탁소 사장 동혁 t = int(input()) coins=[25,10,5,1] for _ in range(t): change = int(input()) change_coin = [] for coin in coins: change_coin.append(change//coin) change -= (change//coin)*coin for i in change_coin: print(i,end=' ')

일단 이 문제는 내 스스로 풀지 못했다. 오늘 임계점에 도달했는지 머리가 돌아가기를 거부한 듯 하다. 지금 안하면 영원히 안하게 될거같아서 어쩔수없이 구글찬스를 썻다..ㅎㅎ 단어수학이라는 문제인데 대문자의 영어알파벳 단어를 입력받고 각 알파벳의 자리수만큼 10의 승수만큼 곱해주어 단어들의 수를 정하고 그 합계의 최대값을 구하는 문제이다 아래의 링크에 들어가보면 문제에 대한 설명이 잘 나와있다. https://jokerldg.github.io/algorithm/2021/03/13/word-math.html 백준 1339번 단어 수학 (python 파이썬) - Tech 백준 1339번 단어 수학 (python 파이썬) March 13, 2021 jokerldg.github.io 코드 # 1339 단어 수학 ..

처음엔 문제를 이해하는것부터 난해했다. 도데체 무슨말인가?? S와 N이 한번에 머리속에서 정리되지는 않았다. 한참을 곰곰히 생각하다가 입력받은 수(S)를 만들어주기 위해서 최대로 많이 필요한 서로다른 숫자가 몇개(N)인지? 이걸 물어보는 문제였다. 그리디(greedy)문제이므로 최대한 많은 숫자를 사용하려면 자연수 중 제일 작은 수인 1부터 더해나가는 것부터 생각을 해보았다. 그리고 더할 만큼 더한뒤에 입력받은 숫자를 맞춰주는 수를 찾아서 넣어주고 그 숫자들의 개수를 카운팅하면 되겠다는 생각을 하였다. 처음 시도한 코드에서는 시간초과가 떳다. 시간복잡도가 O(n^2)가 될 것같다. sum_num 에서 반복 한번 그리고 while문에서 반복 한번이 겹쳐서 실행이 되었으니... 다른 방법을 생각해봐야 한다...

# 주유소 n = int(input()) dis = list(map(int,input().split())) oil = list(map(int,input().split())) res = 0 i = 0 j = 0 tot_dis = sum(dis) while tot_dis != 0: if oil[i] >= oil[i+1]: res += oil[i]*dis[j] tot_dis -= dis[i] i += 1 j += 1 else: res += oil[i]*dis[j] tot_dis -= dis[j] j += 1 print(res) 일단 입력조건들을 만족시킨 후 기름값을 비교하여 문제를 풀었다. 지금 도시에서의 기름값과 다음 도시에서의 기름값중 지금이 기름이 더 비싸면 다음 도시에 갈 만큼만 기름을 넣어주고 그렇지..

# 잃어버린 괄호 n = input().split('-') first = sum(list(map(int,n[0].split('+')))) for i in range(1,len(n)): first -= sum(list(map(int,n[i].split('+')))) print(first) 최소의 값을 만들기 위해서는 처음에 나오는 수 이외에는 모두 빼기로 연산될 수 있도록 괄호를 넣어줘야 한다. - 기호가 나올때마다 괄호를 시작하고 닫아주면 된다. 예를 들어 55-40+30+80이면 55-(40+30+80) 55+40-30-50-60+50 이면 55+40-(30)-(50)-(60)+50 - 기호가 처음 나올땐 괄호를 열어주고 그 다음 - 기호가 나오면 괄호를 닫아주면 모두 빼는 연산이 된다. *그리디(gr..

백준1931 파이썬 맨 처음 풀었던 내 코드 전체 시간을 집합(set)으로 만들어주고 거기에서 차집합으로 하나하나 빼가면서 검사를 했다. 시간초과가 떠서 새로운 방법을 생각해보아야 했다. 아마도 for문이 중복되는 부분이 있어서 입력값이 커질경우 연산량이 많아지기 때문일 것이다. O(n^2) # 회의실 - 시간초과 # big o 표기법에서 어떻게 되는건지 n = int(input()) conf = [] time = set() for i in range(n): start, end = map(int,input().split()) conf.append([start,end,abs(start-end)]) for j in range(start,end+1): time.add(j) conf.sort(key=lambda..