RUBY

출처:: https://www.acmicpc.net/problem/3190 분류:: 시뮬레이션 1. 문제 이해 및 해결과정 - 뱀을 처리하는 법 -> 뱀을 처리하는 리스트나 큐를 따로 만들어 먼저 입력된 것이 꼬리 최근 입력된 것이 머리 - next_dir을 이용해서 방향전환배열의 인덱스를 조정할 수 있음 2. 풀이방법 1. 시뮬레이션 #뱀 #https://www.acmicpc.net/problem/3190 import sys from collections import deque sys.stdin = open("input.txt","r") n=int(input()) #보드의 크기 k=int(input()) #사과의 개수 board=[[0]*(n+1) for _ in range(n+1)] dir=[] #방..

출처:: 카카오2020 신입 공채 https://programmers.co.kr/learn/courses/30/lessons/60059 분류:: 완전탐색 1. 문제 이해 및 해결과정 - 파이썬 코딩테스트 채점 환경에서 1초에 2000만에서 1억정도의 연산을 처리할 수 있음 - 자물쇠 리스트의 크기를 3배 이상으로 변경 2. 풀이방법 1. 완전탐색 #열쇠 회전시키기 def rotate(arr): n=len(arr) rotated=[[0]*n for _ in range(n)] for i in range(n): for j in range(n): rotated[j][n-i-1] =arr[i][j] return rotated def check(biglock): leng=len(biglock)//3 for i in..

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

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