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>...

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

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