RUBY

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

출처:: https://www.acmicpc.net/problem/16234 1. 문제 이해 및 해결과정 *처음 생각 -상하좌우 VISITED 배열 -차이 계산한 것을 둘 TMP배열 1. 차이를 계산한다. 2. 차이 값이 범위 밖이면 벽을 두어 막는다. 차이 값이 범위 이내인 것이 하나도 없다면 종료 3. 인접한 것끼리 BFS 하여 인구 계산 4. 다시 1번으로 돌아감 -어떻게 차이 값을 계산한 배열을 둘 것인가? -국경선을 어떻게 둘 것인가? => 벽을 둔다고 생각하지 말고 범위내에 있으면 같은 숫자로 visited함(방문한 위치에 연합된 것을 알기 위해 index로 체크하하는 것) -BFS의 조건이 범위차이 내에에 있는가 임 - 모든 나라의 위치에서 DFS,BFS를 수행하여 인접한 나라의 인구수를 확..

출처:: https://www.acmicpc.net/problem/14889 1. 문제 이해 및 해결과정 1. N개 숫자중 N/2개 뽑고 =>조합 2. 뽑은 숫자의 모든 경우의수 => 순열 을 구하고 3. 스타트팀의 합 / 링크 팀의 합의 차 가 최소인 것 찾기 4. 다시 1번으로 돌아가 이전에 조합하지 않은 것 조합하기 - 뽑은 것을 체크해두고 - 체크된 것은(team의 인덱스 체크) start에 더하고 체크되지 않은 것은 link에 더한다 - 조합코드 : 조합을 하면 pick에는 {1,1,0,1,0,0} 이렇게 뽑힌 것이 체크되어 있음 -> start와 link 팀 을 뽑혓으면 start에 아니면 link에 넣으면됨 void DFS(int idx,int cnt) { //n개중 n/2개 뽑기 if (c..