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. 검사내용 -출발점이 이전 버...

1007 vector matching 알고리즘 1. 각 테스트 케이스 별로 모든 x좌표와 y좌표를 더함 2. n/2개의 점을 고르고, 그 고른 점들의 모든 x좌표와 y좌표를 더함 3. 1에서 구한 x,y 에 2에서 구한 x,y를 2곱하고 뺌. (sumOfEveryX - 2*sumOfChoosedX) 4. 3.에서 구한 벡터의 길이를 구한 후 반환....

1005 ACM Craft 알고리즘(위상정렬, DP) 1. 1516 게임개발과 비슷한 유형이다 2. 위상정렬하여 푼다. 단, 1516과는 다르게 목표건물을 지었다는게 확인되면 while문을 종료하고 출력해도 됨. 3. 단, 진짜로 위상정렬한 배열을 만들 필요는 없고, 위상정렬식으로 풀어도 시간은 비슷하다. 오히려 위상정렬을 굳이 안만드는 편이 더 ...