RUBY

출처:: https://www.acmicpc.net/problem/18353 분류:: LIS ,dp 1. 문제 이해 및 해결과정 2. 풀이방법 1. LIS 가장 긴 증가하는 부분수열 #병사 배치하기 #https://www.acmicpc.net/problem/18353 import sys sys.stdin = open("input.txt","r") n=int(input()) arr=list(map(int,input().split())) arr.reverse() dp=[1]*n #최소 한개의 길이는 가짐 for i in range(n): #arr[i]가 마지막항일때 for j in range(i): #i보다 작은 것들 중 if arr[j]

출처:: https://www.acmicpc.net/problem/17144 1. 문제 이해 및 해결과정 - 미세먼지가 있는 곳을 큐에 넣음, 큐에 있는 미세먼지만 처리하므로 답이 틀림 - 순서대로 확산 - 확산될때 임시배열을 만들어 두고 나중에 반영하기 - 1. 확산 2. 청정 1)미세먼지의 확장 과정 2) 공기 청정 2. 풀이방법 1. c++ #if 01 //미세먼지 안녕 //https://www.acmicpc.net/problem/17144 #include #define MAXN (50) using namespace std; int R, C, T; //세로, 가로, 시간 int map[2][MAXN + 5][MAXN + 5]; int up_h, up_w, down_h, down_w; int dh[]..

출처:: https://www.acmicpc.net/problem/14501 분류:: dp, dfs 1. 문제 이해 및 해결과정 - 뒤쪽부터 풀어 해결하는 DP - 뒤쪽부터 상담에 대해서 현재 상담 일자의 이익(p[i]) + 현재 상담을 마친 일자부터의 최대이익 dp[t[i]+i]] 을 계산하면됨 - dp[i] : i번째 날부터 마지막 날까지 낼 수 있는 최대 이익 - dp[i] = max(dp[i] + dp[t[i]+i]],maxv) - maxv: 현재까지의 최대 상담금액 2. 풀이방법 1. DP #퇴사 #https://www.acmicpc.net/problem/14501 import sys sys.stdin = open("input.txt","r") n=int(input()) t=[] #각 상담을 완..

출처:: https://www.acmicpc.net/problem/14500 분류:: 구현, 브루트 포스 1. 문제 이해 및 해결과정 - 테트로미노의 회전까지 더해서 가능한 모양은 19가지이다 - 전체 배열을 돌면서 테트로미노의 블럭이 맞는 곳 중에 최대 값을 찾는다 2. 풀이방법 #테트로미노 #https://www.acmicpc.net/problem/14500 import sys sys.stdin = open("input.txt","r") n,m=map(int,input().split()) board=[list(map(int,input().split())) for _ in range(n)] tetromino=[ #19가지 테트로미노가 나올 수 있음 [(0,0),(0,1),(1,0),(1,1)], #ㅁ ..

출처:: https://www.acmicpc.net/problem/11559 분류:: BFS 1. 문제 이해 및 해결과정 1번 풀이 (c++) 1. 입력받음 string 으로 2. 전체 탐색하면서 (bfs) 같은 것의 개수가 4개이상이면 bomb = true 2-1) 탐색하면서 4개이상인 것은 . 으로 바꿈 3. bomb가 true이면 1증가, 하고 fall떨어뜨려야해 4. bomb가 false면 끝 2번 풀이 (python) 1. 4개 이상의 블록이 인접해 있으면 . 으로 바꿈 2. 현재 보드에서 블록을 모두 처리 한 후 , fall 떨어뜨리는 것 처리함 2. 풀이방법 1. c++ #if 01 //Puyo Puyo //https://www.acmicpc.net/problem/11559 #include ..

출처:: https://www.acmicpc.net/problem/15686 분류:: BruteForce, DFS 1. 문제 이해 및 해결과정 1. 치킨 집의 총 개수를 K 라고 하면 그 중 M개를 고름 => 조합 순서없음,중복없음 2. M개에서 치킨거리를 구하고, 치킨거리 중 최소 값을 누적해서 도시의 치킨거리를 구함 [python] 1. 치킨집의 개수가 더 작으니까 치킨집을 기준으로 2. 치킨집의 위치와 집의 위치 각각 저장한다 3. 치킨집을 m개 만큼 뽑는다. 4. 뽑힌 치킨 집부터 집까지 모든 거리를 계산하여 저장한다 5. 치킨 집부터 집까지의 치킨거리가 이전 치킨거리보다 작은경우 작은 것을 저장한다. ex) dist는 (0,2) , (1,4), (2,1), (3,2) 인 집에서 치킨집까지의 최소..

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