본문 바로가기

🔑 알고리즘65

[이코다] 기출문제 - 그리디 p.311 모험가 길드 내 풀이 n = int(input()) guild = list(map(int,input().split())) guild.sort() cnt=0 while guild: num = guild.pop(0) guild = guild[num:] cnt+=1 모험가 길드를 오름차순 정렬하고 quild가 없어질때까지 첫번째 모험가를 빼고 그 모험가의 공포도만큼의 명수를 제거하면 된다고 생각했다. 오류 : 2,3,3 이면 그냥 2,3이 빠지게 될텐데 3은 3명 이상이어야지 그룹이 결성될 수 있으므로 로직 자체가 틀렸다. 정답 풀이 n = int(input()) guild = list(map(int,input().split())) guild.sort() cnt=0 ans=0 for i in gui.. 2021. 8. 25.

[이코다] 다이나믹 프로그래밍 p.217 - 1로만들기 처음 풀이(오답) def solution(num): cnt=0 def calculate(x): if x%5==0: return x//5 elif x%3==0: return x//3 elif x%2==0: return x//2 elif x>1: return x-1 while num!=1: num = calculate(num) cnt+=1 solution(26) #5 그리디처럼 푼 처음 풀이 첫 단계에 위와같은 순서로 해야지 가장 작은 연산의 횟수가 나온다고 생각했다. 하지만 위와 같이 하면 2로 먼저 나누게 되고 그러면 답안과 다르게 5라는 답이 나온다. 이 무제는 다이나믹 프로그래밍이고 그 근거는 1) 부분적인 연산의 합이 답이 된다. 2) 작은 문제로 나눠진다. 다이나믹 프로그.. 2021. 8. 23.

[이코다] 정렬 & 이진탐색 실전문제 p.181 정렬 실전문제 def solution(): n = int(input()) student = [] for i in range(n): name,grade = input().split() student.append([name,int(grade)]) student =sorted(student,key = lambda x : x[1] ) for i in student: print(i[0],end=' ') solution() 정말정말 간다한 문젠데 단순한 실수를 해서 기록한다. 배운점 1. 입력 받은 값이 정수인지 문자인지 구분하기 2. sorted를 하고 난 결과는 다시 받기 (sort와 다르다! 정렬한 값을 재할당 해줘야 한다) p.182 두 배열의 원소 교체 시간 복잡도 생각 안하고 푼 풀이 def .. 2021. 7. 28.

[이코다] 그리다 & 구현 실전문제 시간제한1 초 데이터 :100만개 => O ( n log n) p.96 숫자카드게임 내풀이 풀이시간 시간복잡도 20m O(N log N) def solution (): n,m = map(int,input().split()) for i in range(n): matrix.append(min(list(map(int, input().split())))) print(max(matrix)) result= 0 solution() 배운점 답의 후보들을 배열에 넣지 말고 그냥 두가지 값을 바로 max로 비교하는 것이 더 좋다 result = 0 for i in arr: result = max(i,result) p.100 숫자카드 풀이시간 시간복잡도 20m O(N log N) 내 코드 def solution(): n,k.. 2021. 7. 23.

[알고리즘] 이분탐색 (Binaray Search) 알고리즘을 풀다 보면 시간복잡도의 늪에 빠질 때가 있다. 특히 수의 범위가 크면 배열 내 특정한 값을 찾을 때 아래와 같은 방식은 모든 배열을 탐색하기 때문에 엄청난 시간이 걸리게 된다., i in arr 이럴때 사용할 수 있는 이분탐색! 이분탐색은 배열에서 특정한 값을 찾을 때 순차 탐색처럼 매번 모든 데이터를 체크하여 값을 찾는게 아니라, 탐색범위를 절반씩 줄여가며 찾아가는 search 방법이다. 그림을 엉성하게 그렸지만 이분탐색을 아주 직관적이게 표현해보았다. 😎 그렇다면 코드 구현 시에 어떻게 표현될까? 지극히 개인적이지만 알고리즘 문제를 만났을 때 적용할만한 유형을 크게 3가지로 분리했는데, 1) 배열내 특정한 값의 idx를 찾을 때 2) 배열내에서 특정한 값이 추가될 때의 그 idx 3) 1).. 2021. 7. 11.

[codility] Lesson 4) FrogRiverOne MaxCounter 📌 4-1) - FrogRiverOne 주어진 1부터 주어진 X값이 나온 가장 빠른 idx를 구하는 문제 첫 풀이 (54%) def solution(X, A): idArr = [0]*X for i in range(len(A)): idArr[A[i]-1]=1 if sum(idArr)==X: return i return -1 1) idArr 생성 2) A를 돌며 해당 값을 idx로 넣어줌 3) idArr가 다 찼을 때 return 역시나 시간복잡도로 인하여 점수르 반이나 깎였다. 제한 시간복잡도는 O(N ** 2) 이미 for + if의 조합으로 N^2이 되어있엇고 그안에서 sum연산까지 하기 때문에 모자라고 sum을 없애야 한다!! 다른 풀이 (100%) def solution(X, A): idArr = .. 2021. 7. 10.

[codility] Lv2- OddOccurrencesInArray,Lv3-TapeEquilibrium ,TapeEquilibrium 프로그래머스 문제에만 의존하던터라, coldility 라는 새로운 코드풀이 플랫폼을 알게 되었고, 문제를 열심히 풀어보기로 결심했다. 문제를 풀이하면서 처음으로 놀란 것은 코드의 효율성을 신경써야 하는 것 그동안은 그렇게 효율성에 대해서 깊게 생각해보지 못했지만, 효율성이 좋지않거나 지나친 반복문이 계속되는 코드는.... score에서 깎이게 된다... 문제를 풀며 배운 점 1. 예외처리를 해야한다. 2. 입력값의 범위 크기를 알아야 한다. 3. 시작복잡도에 대한 고민을 하자 (https://rrecoder.tistory.com/63) 📌 2- OddOccurrencesInArray 배열에서 자신과 중복한 값의 개수가 홀수인 값을 return 하는 문제 첫 풀이 def solution(A): cntDic.. 2021. 6. 21.

[백준] 파이썬/ 그리디 11047_동전0 , 1541_잃어버린 괄호 📌11047 동전0 https://www.acmicpc.net/problem/11047 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 내 풀이 import sys input= sys.stdin.readline coins=[] coinCnt=0 n,k = map(int,input().split()) for i in range(n): coins.append(int(input())) left=0 for j in range(len(coins),0,-1).. 2021. 6. 8.

[백준] 파이썬 / 그리디 2839_설탕배달 📌2839 설탕 배달 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 처음 딱 든 생각은 3인경우 / 5인경우 / 3과 5 둘 다를 쓰는 경우 를 다 세서 가장 작은 경우의 수를 빼야 한다고 생각했다. 내 풀이 (오답) n=int(input) def three(num): if num%3 ==0: return num//3 else: return -1 def five(num): if num%5 ==0: return num//5 else: return -1 d.. 2021. 6. 1.

이전 1 2 3 4 5 6 7 8 다음

티스토리툴바