RUBY

PART2 그리디 - 큰 수의 법칙 - 숫자 카드 게임 - 1이 될 때까지 구현 - 예제4-1) 상하좌우 - 예제4-2) 시각 - 왕실의 나이트 - 게임 개발 DFS/BFS - 음료수 얼려 먹기 - 미로 탈출 정렬 - 선택정렬 - 삽입정렬 - 퀵정렬 - 계수정렬 - 위에서 아래로 - 성적이 낮은 순서로 학생 출력하기 - 두 배열의 원소교체 이진탐색 - 부품찾기 - 떡볶이 떡 만들기 다이나믹프로그래밍 - 1로 만들기 - 개미전사 - 바닥 공사 - 효율적인 화폐 구성 최단 경로 - 미래 도시 - 전보 그래프 이론 - 팀 결성 - 도시분할 계획 - 커리큘럼 PART3 그리디 1. 모험가 길드 2. 곱하기 혹은 더하기 3. 문자열 뒤집기 4. 만들 수 없는 금액 5. 볼링공 고르기 6. 무지의 먹방 라이브 구현..

출처:: www.acmicpc.net/problem/10775 분류:: 서로소 집합 알고리즘 , union-find 1. 문제 이해 및 해결과정 - 도킹 = union연산 - 비행기가 순서대로 들어오면 차례대로 도킹을 수행해야하는데, 가능한 큰 번호의 탑승구로 도킹을 수행한다고 해보자 - 새롭게 비행기가 도킹 되면, 해당 집합을 바로 왼쪽 집합과 합친다. - 단, 집합의 루트가 0이면 더 이상 도킹이 불가능하다 ex) 입력2의 경우, 4는 탑승구의 개수, 6은 비행기의 수 1. 2 -> 첫번째 비행기는 1부터 2까지의 탑승구 중 하나에 도킹, 2번 노드를 확인하는데 2번 노드의 루트는 2이다. 그러므로, 1번과 union 2. 2 -> 두번째 비행기는 1부터 2까지의 탑승구 중 하나에 도킹할 수 있다. ..

출처:: University of Ulm Local Contest 분류:: 크루스칼 1. 문제 이해 및 해결과정 - 최소한의 비용으로 모든집을 연결해야한다 => 최소 신장 트리문제 - 임의의 두 집에 대하여 가로등이 켜진 도로만으로도 오갈 수 있도록 -> 최소 신장 트리 문제 의심해야한다 - 왕래할 수 있다는 것은, 그래프에서 각 노드가 서로 연결되어 있다는 의미와 같기 때문이다 - 크루스칼 알고리즘 - 구하는 것은 절약할 수 있는 최대 금액 이므로 전체 가로등 켜는 비용 - 최소 신장 트리 비용 2. 풀이방법 1. 크루스칼 #어두운 길 # import sys sys.stdin = open("input.txt","r") n,m=map(int,input().split()) parent=[0]*(n+1) f..

출처:: 분류:: 서로소 집합 알고리즘 1. 문제 이해 및 해결과정 - 서로소 집합 알고리즘을 이용하여, 그래프에서 노드 간의 연결성을 파악하여 해결해야한다. - 서로소 집합 알고리즘을 이용하는 이유: 여행계획에 해당하는 모든 노드가 같은 집합에 속하면 가능한 여행결로 - 두 노드 사이에 도로가 존재하면 -> union 연산 - 여행계획에 포함되는 모든 노드가 모두 같은 집합에 속하는지 체크하면 정답 2. 풀이방법 1. UNION-FIND 서로소 집합 알고리즘 #여행 계획 # import sys sys.stdin = open("input.txt","r") n,m=list(map(int,input().split())) parent = [0]*(n+1) #부모 테이블 초기화 #부모 테이블 상에서, 부모를 자..

출처:: 구글 인터뷰 분류:: DP 1. 문제 이해 및 해결과정 - 못생긴 수: 2,3,5만을 소인수로 가지는 수 - 1은 못생긴 수라고 가정 - 못생긴 수 = {1,2,3,4,5,6,8,9,10,12,15, ... } 2. 풀이방법 1.DP #못생긴 수 # import sys sys.stdin = open("input.txt","r") n=int(input()) ugly = [0]*n #못생긴 수를 담기 위한 테이블(1차원 dp테이블) ugly[0]=1 #첫번쨰 못생긴 수는 1 #2,3,5배를 위한 인덱스 i2=i3=i5=0 #처음에 곱셈값을 초기화 next2,next3,next5=2,3,5 #1부터 n까지의 못생긴 수 찾기 for i in range(1,n): #가능한 곱셈 결과 중에서 가장 작은 수..

출처:: Goldman Sachs 인터뷰 분류:: DP 1. 문제 이해 및 해결과정 - 2차원 DP테이블 이용 1. 두 문자가 같은 경우 dp[i][j]=dp[i-1][j-1] , 행과 열에 해당하는 문자가 서로 같으면, 왼쪽 위에 해당하는 수 삽입 2. 두 문자가 다른 경우 dp[i][j]= 1 + min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1]) , 행과 열에 해당하는 문자가 서로 다르면, 왼쪽(삽입), 위쪽(삭제), 왼쪽 위(교체) 에 해당하는 수 중 가장 작은 수에 1을 더해서 대입 a/b 0 s a t u r d a y 0 0 1 2 3 4 5 6 7 8 s 1 0 1 2 3 4 5 6 7 u 2 1 1 2 2 3 4 5 6 n 3 2 2 2 3 3 4 5 6 d 4 3 3..

출처:: Filpkart 인터뷰 분류:: dp 1. 문제 이해 및 해결과정 - 시작을 기준으로 하는 것이 아니라 들어오는 지점을 기준으로 생각을 전환해보자 - 예를 들면 (2.2)에서 갈 수 있는 곳은 (3,1) (3,2) (3,3) 이지만 (3,2)로 들어올 수 있는 것은 (2,1) (2,2) (2,3) 이 된다 2. 풀이방법 1. dp #금광 # import sys sys.stdin = open("input.txt","r") t=int(input()) for tc in range(t): n,m=map(int,input().split()) arr =list(map(int,input().split())) dp=[] index = 0 for i in range(n): dp.append(arr[index:i..

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