RUBY

출처:: https://www.acmicpc.net/problem/1932 분류:: 다이나믹프로그래밍 DP 1. 문제 이해 및 해결과정 - dp[i][j] = arr[i][j] + max(dp[i-1][j-1],dp[i-1][j]) - dp배열에 저장되는 값은 현재 위치값 + max( 입력조건 기준으로는 왼쪽위 대각선 값 or 위쪽 값) - 단!!! 처리해야 할 사항은 맨 윗줄 혹은 사이드일 때 왼쪽 or 오른쪽 대각선 값이 없으므로 처리 해야함 => 맨 왼쪽 j==0일때는 왼쪽 대각선이 없음 , 맨 오른쪽 j==len(dp[i])-1 일때는 오른쪽 대각선이 없음 2. 풀이방법 1. dp #정수 삼각형 #https://www.acmicpc.net/problem/1932 import sys sys.stdi..

출처:: 아마존 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..