1107 리모컨 알고리즘(브루트 포스) 1. 0~100만까지 하나씩 올라가며, 되는지 검사하고, 가장 적게 누르는 건지 저장 2. 되는지 검사할 때는, 고장난 버튼을 bool 배열에 저장하여 바로바로 참조가능하게 하고, 뒤에서부터 하나씩 검사하자 헛발질 기록 1. 처음엔 들어온 버튼의 자릿수에 맞게, 모든 숫자를 검사하되 재귀로 수를 하나씩 ...

11066 파일합치기 알고리즘(DP) 1. 긴 한 줄의 파일들을 두조각으로 분리해서 찾는 방식으로 DP를 함 2. 먼저 0, k-1를 넣음 3. (0, k-1)의 파일 크기의 합을 구한 후, (0,0)-(1,k-1), (0, 1)-(2,k-1) ... 로 모든 두 조각을 만든 후, 그 조각의 비용을 구함 -> start == end 일 경우...

11054 가장 긴 바이토닉 부분수열 알고리즘(LIS) 1. 왼쪽에서 오른쪽으로 LIS, 오른쪽에서 왼쪽으로 LIS 후, 모든 점에 대하여 l[i] + r[i] - 1 (길이가 1이면 1일때, 0일경우는 + 1 해줌) 가 최대가 되는 점을 찾고 그점에서의 l[i] + r[i] -1 를 출력하면 됨. 2. 길이가 최대1000이므로 dp로 안해도 ...

11049 행렬곱셈순서 알고리즘(DP) 1. 연속된 원소를 크게 이등분하여 계산할 수 있음 ex) (start ~ i, i+1~end) 2. dp(start, end)는 start에서 end까지의 범위를 계산할 때 최소비용. 3. 현재 비용은, matrixt[start][0]*matrix[i][1]*matrix[end][1] 로 계산할 수 있음. ...

10942 Palindrome 알고리즘(DP) 1. 입력으로 받은 것이 팰린드롬인지 확인 2. 팰린드롬이면 from-to 사이에 있는 모든 건 다 팰린드롬이다. -> DP에 팰린드롬임을 표시 아니면, from-to에서 팰린드롬이 아님을 판별한 곳까지 팰린드롬이 아니다 -> DP에 팰린드롬이 아님을 표시 주의점 아무리 잘 짜도 i...

10830 행렬제곱 알고리즘 (거듭제곱, 행렬곱) 1. 그냥 행렬 거듭제곱으로 풀면됨 주의점 1. 입력의 B를 long long으로 받아야한다 2. AB = A 가 나오도록 하는 B행렬은 대각선이 모두 1이고 나머지는 0인 행렬이다 코드 #include <iostream> #include <cstring> using...

10775 airport 알고리즘(자료구조, 트리를 이용한 이진탐색) 1. 게이트의 개수에 맞게 1~G를 set에 넣음 2. bool형 check 배열에서, gi에 아무것도 없으면 gi에 넣고 set에서 gi 삭제 3. 이미 gi에 들어가 있으면, set에서 upperbound로 gi초과하는 첫번째를 찾음 -> 만약 그 첫번째가 begin...

1043 거짓말 알고리즘(DFS) 1. 처음 진실을 알고있는 사람과 연결돼있는 파티 그룹과, 절대 연결되지 않은 그룹을 나눠야함. 2. 나는 단순히 변화가 발생하지 않을 때까지 반복하였음. 그리고 그런 사람이 없는 그룹의 개수만 세서 출력함. 다른 풀이 1. 내꺼에서 좀더 최적화된 풀이 2. 처음에 입력을 받으면서, 각 사람들이 어디 파티와...

10217 KCM Travel 알고리즘(다익스트라, DP) 1. 기본적으로 다익스트라를 사용하여 최소경로를 찾아야하는 것을 맞으나, 비용이 넘어버릴경우 이전의 최소경로로 간 것이 의미가 없어진다. 따라서 현재 큐에서 꺼낸 노드가, 이전에 지나간 노드보다 같은 비용일때 더 시간이 많이 걸렸을 경우만 패스. DP[101][10001] 선언 2...

10165 KOI 2014_Elementary 알고리즘 1. 각 버스노선의 출발점, 도착점, 번호를 기록한 구조체를 만들고, 출발점을 기준으로 정렬. 출발점이 같으면 도착점이 작은 것이 앞에 위치하도록함. 2. 버스노선인덱스를 저장하는 배열을 만들어, 버스노선을 하나씩 검사함. -초기 : 첫번째 버스노선을 넣음 3. 검사내용 -출발점이 이전 버...