9328 key 알고리즘(BFS, 구현) 1. 방문한 곳을 체크하는 check 이차원 배열, 키를 저장하는 key 배열, 닫힌문을 저장하는 closedDoor 벡터가 필요 2. 먼저 키 배열은 26개의 원소로 이루어진 bool 자료형 배열로 선언. 각 알파벳에 해당하는 키가 들어오면 1을 저장한다. 3. 방문가능한지 체크하는 checkCell 함수...

9252 LCS2 알고리즘(최장 공통 부분 수열) 1. LCS 알고리즘 사용하면 됨 구현법 1. 문자열 입력 받을 땐. cin.getline(char *c, size) 넣으면 된다. 코드 #include <iostream> #include <cstring> #define MAX_LENGTH 1000 using nam...

7579 app 알고리즘(배낭정리, DP) 1. 배낭정리 응용. 최대 비용을 가방에 담을 수 있는 최대 무게로 보고, 메모리를 가치로 본다 2. 이렇게 2차원 배열을 완성하고, 필요한 메모리 이상이며 비용이 최소인 칸을 판별하고 출력하면 된다. 구현법 1. 최대 앱 개수는 100개이므로, 101행, 앱 당 최대 비용은 100 이므로 10001...

7453 four Integer’s sum should be zero 알고리즘(정렬, 이분탐색) 1. 앞 두개 정수의 합 배열, 뒤 두개 정수의 합 배열을 만듬.(배열 개수^2 가 합 배열의 길이) 2. 두 배열을 정렬 3. 앞 합 배열의 원소를 하나씩 빼며 검사 -> 뒤 합 배열에서, upper_bound - lower_bound 값이, 현...

6087 레이저통신 알고리즘(BFS) 1. visit 배열을 int로 선언. 이제까지 온 것들의 거울 개수를 저장 2. 갈 수 잇고, visit에 저장된 거울 개수와 같거나 작으면 이동 시킴 주의점 같은 레이저에 도달하지 않기위해 설정한 row != start.row && col != start.col 은 작동하지 않음 ->...

6064 카잉달력 알고리즘(수학) 1. n 을 M과 N으로 나누었을때 나온 수가 x와 y 이면 된다. 단, 나누었을때 나오는 수는 0~M-1 or N-1인데 문제에선 1~M, 1~N 까지이므로 이걸 고려해야한다. 2. 하나씩 증가시켜가면서하면 너무 오래걸리니, M과 N 중 더 큰수를 더하는 수로 삼고, 그것과 연결된 수부터 시작한다(M-x, N-...

5014 스타트링크 알고리즘 (BFS) - 직선으로의 BFS 를 사용하면 됨 - DP를 사용하면 시간초과가 발생함. - 도달시 다 종료한다고 해도, 그게 최소로 간건지 몰라서 결국 더 검사해야함. 코드 #include <iostream> #include <list> using namespace std; list<...

4991 로봇청소기 알고리즘(BFS, 브루트포스) 1. 구현이 더 중요한 문제. 2. 그냥 시작 + 각 더러운 곳(DT) 에서 다른 DT로의 최소 거리를 저장한 2차원 배열을 BFS로 만들고 3. 시작부터 모든 경로를 탐색하여 최소 거리를 뽑아내면 됨. 4. 방문 할 수 없는지 판별은 시작에서 갈 수 없는 DT가 있는지 확인하면 됨 구현 1....

4811 알약 알고리즘 (dp) 1. 하나의 완전한 알약을 one, 반쪽 알약을 half 라고 하면, dp[1001][1001] 를 선언하고, one, half를 기준으로 dp를 저장함 2. dp를 진행하면서 밑으로 내려가면서 one이 1개 이상이면 1 줄이고 half 1 증가하고 밑으로 내려갈 수 있고, half가 1개 이상이면 마찬가지로. ...

4386 make constellation 알고리즘(MST) 1. 모든 별들 사이의 거리를 구한 다음에, 두 별의 위치, 거리를 저장한 구조체 배열을 거리순으로 오름차순 정렬 2. 구조체 배열에서 하나씩 빼가며 크루스칼 시행 -> edge == numOfStar -1 이면 중지 후 출력 코드 #include <iostream>...