1644 소수의 연속합 알고리즘(에라토스테네스의 체, 두 포인터) 1. 에라토스테네스의 체로, N이하의 소수를 모두 구함 2. 두 포인터로 일치하는 해당하는 연속합을 구함 초기 : start = 0, end = 1, sum = prime[0] while start < end if sum == N count++ ...

1562 계단수 알고리즘(DP, 비트마스킹) 1. 숫자를 기록하는 num[101] 배열과, DP[101][10][1 << 10] 배열을 이용하여 DP로 품 2. 앞에서부터 길이에 맞게 숫자를 하나하나 기록해감. 기록하면서 비트마스킹으로 0~9가 있는지 표시 -> 이때 이미 표시된 비트에 또 표시하면 기록이 망가짐. 따라서 &...

1516 Developing game 알고리즘(위상정렬, 그래프. DP) 1. 어떤 건물을 짓기 위해 필요한 건물을 짓는 시간의 최대 + 이 건물을 짓는데 걸리는 시간을 출력하면 됨. 2. 예를 들어 A -> -> D C B -> -> E 로 그래프가 이루어져 있을 때, A : A를 짓는 시간 B ...

1509 팰린드롬 분할 알고리즘(Manacher’s Algorithm, DP) 1. 2차원 bool 형 배열 palindrome에 모든 팰린드롬을 저장. -> palindrome[i][j] 엔 시작이 i이고 끝이 j인 문자열이 팰린드롬인지 아닌지 저장돼있음 -> 구하는 법은 처음부터 i = 0~length, j = i~length; ...

14939 불끄기 알고리즘(브루트, 그리디, 비트마스킹) 1. 최소한으로 눌러야하는 경우 : 한 칸은 한번만 눌러야함. 두번 이상누르면 최소가 아니고, 무한 루프가 될 수 잇음 2. 모든 방법을 다 검사해봐야 정답을 얻을 수 있음 -> 브루트 포스 3. 한번씩만 누르면 누르는 순서는 중요하지않음 -> 첫줄부터 차례대로 누름 4. 이때 첫...

14938 서강그라운드 알고리즘(플로이드워셜) 1. 접근 방법 - 처음엔 DFS 또는 BFS로 접근 - 근데 해보니 이전에 왔던 것보다 적은 거리를 써서온건 보내고, 보낸 다음부터 이어지는 건 겹치면 빼야함. - 결국 플로이드워셜로 최소거리를 모두 구한 후, 탐색범위 안에 들어오는 지역의 아이템을 모두 더하는 방식과 동일함. 코드 #in...

14500 Samsung sw test 알고리즘 1. 가능한 모든 모양으로 검사. 코드 #include <iostream> #define MAX_WIDTH 501 using namespace std; int width, height; int map[MAX_WIDTH][MAX_WIDTH]; void getProperties();...

14499 Samsung sw test 알고리즘 1. 각 명령별로 검사. 초기 주사위 상태 (top : 1, north : 2, east : 3, south : 5, western : 4, bottom : 6) 2. 명령대로 주사위를 굴리고 -> 그 위치가 맵 밖이면 다음 명령 실행 맵 안이면 이동시키고, 주사위 상태 변경 ->...

14003 LIS5 알고리즘 (LIS) 1. LIS 로 구함 2. 수열 출력 1. LIS구하면서, 현재 LIS의 인덱스를 항상 저장함 2. LIS를 구하면, 가장 뒤에있는 LIS의 가장 뒤 원소의 인덱스가 저장됨 3. 그 인덱스로부터 길이를 하나씩줄여가며 앞으로 가면서 길이가 맞는걸 뒤에서부터 저장 4. 길이가 0이되면 종료 5. 이렇게하...

13549 숨바꼭질 3 알고리즘(BFS) 1. BFS로 가능한 곳은 가되, check엔 이전에 온 것보다 적은 시간을 걸리며 온 것을 받아주기 위해 시간을 저장하자. 코드 #include <iostream> #include <cstring> #include <list> using namespace std; ...