2933 미네랄 알고리즘(구현, 시뮬레이션) 1. 들어온 위치의 미네랄을 지움 2. 지운 위치에서 상하좌우에 인접한 칸들을 root로 BFS 시행 -> 바닥에 닿는 칸이 있으면 공중에 뜬 클러스터가 아님 3. 공중에 뜬 클러스터이면 BFS 시 넣은 칸들을 열순, 열이 같으면 행이 큰 순으로 정렬 4. 각 열별로 가장 밑에 있는 칸만 검사하여 ...

2931 가스관 알고리즘(구현) 1. M에서 시작해 갈 수 있는 방향으로 가다가 빈칸을 마주하면 스탑. 만약 빈칸이 없으면 아예 처음부터 연결이 안된 것. 이때는 Z 부터 시작해 빈칸을 찾는다. 2. 빈칸을 찾으면 빈칸 주변을 검색. 인접한 칸에 바로 연결되는 파이프가 있으면 그 칸을 true로 표시. 표시된 것에 따라 빈칸에 넣을 수 있는 가...

2887 planet tunnel 알고리즘(정렬, MST) 1. 모든 행성들의 x좌표, y좌표, z좌표를 꺼내 따로 저장하고, 오름차순으로 정렬 2. 정렬한 것에서 인접한 것끼리 비용을 계산, (인접한 점 두개 + 비용)을 구조체로 n-1개의 원소를 가지는 배열 3개를 선언하고 집어넣음 3. 그 구조체배열 3개는 비용을 기준으로 오름차순으로 정렬 ...

2568 전기줄 알고리즘(LIS) 1. LIS를 구하면 그것들이 겹치지 않고 최대로 연결가능한 전깃줄들이다. 2. 따라서 LIS를 구하고 전체 전깃줄에서 LIS를 빼면 빼야하는 전깃줄의 수와 전깃줄의 종류가 나오게 된다. 코드 #include <bits/stdc++.h> #define MAX_WIRE 100001 using nam...

2529 부등호 알고리즘(브루트포스, 백트래킹) 1. 모든 경우를 탐색하되, 앞에서부터 하나씩 채워가면서 재귀형태로 하면 백트래킹도 적용하기 쉽다. 2. 조건에 맞는 경우만 탐색하면 됨. 3. 낮은 거 먼저 탐색하도록하면 굳이 뭘 저장할 필요없이 맨처음것만 minimum에 저장하고, 제일 나중 것을 maxnimum에 저장하면 된다. 코드 #i...

2342 Dance Dance Revolution 알고리즘(DP) 1. 왼발 위치, 오른발 위치, 명령 번호를 기준으로 dp 자료를 만듬 dp[5][5][MAX_COMMAND] 2. 명령과 같은 칸에 있을 경우 그대로, 다른 위치에 있을 경우 가능한 위치엔 전부 옮기는 식으로 DP 시행. 코드 #include <iostream> ...

2252 줄세우기 알고리즘(위상정렬) 1. 그냥 위상정렬하면된다. 구현 1. Student 구조체 : beforeCount : 이전에 몇개있는지 셈, next : 큰 학생들 나열, isChecked : 라인에 넣어졌는지 확인 2. 처음에 beforeCount가 0인 학생들을 큐에 넣고, isCheked에 체크함 3. 하나씩 큐에서 빼면서 아래...

2239 sudoku 알고리즘(백트래킹) 1. 칸을 하나씩 탐방하면서, 0으로 기록돼있다면 수직, 수평, 3x3사각형을 검사하여 가능한 숫자를 하나씩 뽑아서 넣고 다음 칸 검사 2. 만약 0으로 기록되지않은 칸으로 갔다면 다음칸으로 넘겨주되, 마지막 칸일 경우 스도쿠가 완성된 것이므로 true를 반환한다. 3. 마찬가지로, 넣고 다음 칸으로 이동하...

2186 문자판 알고리즘(DFS, DP) 1. 문자판을 주어진 조건대로 순회하되, 결과값이 int 안이라는 걸보고 엄청 클 수도 잇다는 걸 예측 or 빙글빙글 계속 돌 수 있으니 DP가 잇어야겠다고 예측 2. DP를 DP[r][c][d] 로 구현하되, -1로 초기화를 시키고, 0인것도 기록 -> 문자열이 아예 없을 수도 잇으니 0도 기록하여 ...

2166 areaOfPolygon 알고리즘(기하학) 1. 사선정리 사용 구현법 1. 최대 4000000000000이 나올 수 있으므로, int대신 long long, float은 쓰지말고 double로 통일 시킨다. 2. double은 최대 15자리수를 표현가능하므로, 위 값도 충분히 들어갈 수 있다. 코드 #include <ios...