RUBY

출처:: https://www.acmicpc.net/problem/2636 분류:: BFS 1. 문제 이해 및 해결과정 1) 공기면 bfs하면서 큐에 넣기 2) 공기가 아니라면 공기에 닿은 것 더해주기 board[i][j]+=1 3) board[i][j]>=2 , 치즈가 공기에 1개이상 닿았다는 의미 이므로 녹임 2. 풀이방법 1. python #치즈 #https://www.acmicpc.net/problem/2636 import sys from collections import deque sys.stdin = open("input.txt","r") n,m=map(int,input().split()) board=[list(map(int,input().split())) for _ in range(n)] d..

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

출처:: 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까지의 탑승구 중 하나에 도킹할 수 있다. ..