3197 백조의 호수 알고리즘(구현) 처음 방법 1. 한 백조에서 BFS 실시하여 다른 백조를 만날 수 있는지 검사 2. 전체 맵을 검사해서 녹일 수 있는 걸 녹임 3. day 추가하고 다시 1부터 -> 시간이 너무 걸림. 특히 맵 초기화하는 부분이 많이 걸림 두번째 방법 1. 1번은 유지 2. 녹을 수 있는 얼음만 저장한 q에서 ...

3190 Samsung sw test 알고리즘 1. 그냥 대가리 옮기고 꼬리 잡히는지, 칸 밖인지 확인하고, 또 사과있는지 확인하고, 또 시간이 바꿀때가 됐는지 확인 2. 뱀 몸은 vector로 저장 / 사과 위치는 2차원 bool 배열로 저장하여 메모리랑 참조시간 아낌. / 시간은 Direction 구조체에 저장하고, directionInde...

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. 마찬가지로, 넣고 다음 칸으로 이동하...