RUBY

출처:: 아마존 Amazon 인터뷰 분류:: 이진 탐색 1. 문제 이해 및 해결과정 2. 풀이방법 1. 이진 탐색 #고정점 찾기 # import sys sys.stdin = open("input.txt","r") n =map(int,input().split()) li=list(map(int,input().split())) def binary_search(a,l,r): l=0 r=len(a)-1 while l

다이나믹 프로그래밍(=동적계획법) - 배경) 컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적 - 메모리 공간을 약간 더 사용하면 연산속도를 증가시킬 수 있는 방법 - 큰 문제를 작게 나누고, 같은 문제라면 한번 씩만 풀어 문제를 효율적으로 해결하는 알고리즘 - 다이나믹 프로그래밍과 분할 정복의 차이점은 다이나믹 프로그래밍은 문제들이 서로 영향을 미치는 점 - 만족해야하는 조건 1. 큰 문제를 작은 문제로 나눌 수 있다 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다 - 구현 방식 1) TOP-DOWN(탑다운)방식 = 하향식 = 메모이제이션 : 큰 문제를 해결하기 위해 작은 문제를 호출 - 재귀함수를 이용하여 다이나믹 프로그래밍 소스코드를 작..

출처:: https://www.acmicpc.net/problem/1715 분류:: 정렬 1. 문제 이해 및 해결과정 - 정렬 시 heap 자료구조를 이용하면 된다 - 작은 것 두개 빼서 합쳐서 집어넣고 2. 풀이방법 1.정렬 #카드 정렬하기 #https://www.acmicpc.net/problem/1715 import heapq import sys sys.stdin = open("input.txt","r") n=int(input()) heap=[] for i in range(n): tmp=int(input()) heapq.heappush(heap,tmp) total=0 #힙에 원소 한 개 남을 때까지 while len(heap) !=1: print(heap) #가장 작은 2개의 묶음 꺼내기 one=h..

출처:: 2019 카카오 신입 공채 1차 https://programmers.co.kr/learn/courses/30/lessons/42889 분류:: 정렬 1. 문제 이해 및 해결과정 2. 풀이방법 1. 정렬 def solution(N, stages): answer = [] stages.sort() arr=[0]*(N+1) total=len(stages) fail=[] for i in range(1,N+1): for x in stages: if i==x: arr[i]+=1 if arr[i]==0: fail.append((0,i)) else: fail.append((arr[i]/total,i)) total-=arr[i] fail.sort(key=lambda x:(-x[0],x[1])) print(fail..

출처:: https://www.acmicpc.net/problem/10825 분류:: 정렬 1. 문제 이해 및 해결과정 2. 풀이방법 1. 정렬 #국영수 #https://www.acmicpc.net/problem/10825 import sys sys.stdin = open("input.txt","r") n=int(input()) arr=[] for i in range(n): arr.append(input().split()) arr=sorted(arr,key= lambda x: (-int(x[1]),int(x[2]),-int(x[3]),x[0])) for student in arr: print(student[0]) 3. 오답원인 4. 알게된 점 정렬 시 key 값 설정하기 - 리스트 원소 정렬할 때는 so..

출처:: 삼성전자 SW역량테스트 분류:: DFS 1. 문제 이해 및 해결과정 2. 풀이방법 1.DFS #연산자 끼워넣기 #https://www.acmicpc.net/problem/14888 import sys sys.stdin = open("input.txt","r") n=int(input()) num=list(map(int,input().split())) op=list(map(int,input().split())) maxv=int(-1e9) minv=int(1e9) def DFS(d,value): global maxv,minv if d==(n-1): maxv=max(maxv,value) minv=min(minv,value) return else: for i in range(4): if op[i]>0: ..

출처:: 2020카카오 신입 공채 https://programmers.co.kr/learn/courses/30/lessons/60057?language=python3 분류:: 구현 1. 문제 이해 및 해결과정 2. 풀이방법 1. 구현 def solution(s): leng=len(s) answer=leng result=str() for i in range(1,leng//2+1): #i는 자르는 개수 cur=s[0:i] sum=1 for j in range(i,len(s),i): next=s[j:j+i] if cur==next: sum+=1 else: if sum>=2: result+=str(sum)+cur else: result+=cur cur=next sum=1 if sum>=2: result+=str..

출처:: 분류:: 위상정렬 알고리즘 1. 문제 이해 및 해결과정 - 각 노드에 대하여 인접한 노드를 확인 할 때 , 인접한 노드에 대하여 현재보다 강의시간이 더 긴 경우를 찾는다면, 더 오랜 시간이 걸리는 경우의 시간 값을 저장하는 방식으로 결과 테이블을 갱신하여 답을 구할 수 있다. - 위상 정렬을 수행하면서, 매번 간선 정보를 확인하여 결과 테이블을 갱신한다. 2. 풀이방법 1. 위상정렬 #커리큘럼 # import sys from collections import deque import copy sys.stdin = open("input.txt","r") ''' 5 10 -1 10 1 -1 4 1 -1 4 3 1 -1 3 3 -1 #출력 10 20 14 18 17 ''' n=int(input()) #..