baekjoon 2193 이친수 2193번 이친수 접근 dp(n)을 n자리 이친수 개수라고 한다면 dp(n) = dp(n-2) + … dp(1) + dp(0)이 성립한다. n자리는 무조건 1, 그럼 n-1자리는 무조건 0 이상태에서 n-2자리부턴 1 또는 0으로 경우가 나뉘는데, 1이면 dp(n-2)이고 0이면 n-3자리로 넘어가서 또 1또는 0으...

baekjoon 2294 동전 2 2294번 동전 2 접근 각 동전이 서로 나눠지는 관계가 보장된다면 이 동전 문제는 greedy 문제가 된다. 하지만 그렇지 않은 경우도 있기 때문에 dp로 모든 경우의 수를 직접 해봐야한다. 각 동전을 무제한적으로 쓸 수 있기 때문에 각 동전을 몇개 썼는지 여부는 기록할 필요가 없다. 단지 내가 채워야하는 돈만 ...

baekjoon 9465 스티커 9465번 스티커 접근 지금 스티커를 놓아야 할 자리와 (column number), 직전 column에서 위에 스티커가 있는지 아래 스티커가 있는지 여부로 dp를 만들었다. 코드 //9465 #include <iostream> #include <vector> #include <array...

baekjoon 1463 1로 만들기 1463번 1로 만들기 접근 dp 탑 다운 방식으로 접근해서 풀었다. 코드 //1463 #include <iostream> #include <queue> #include <array> using namespace std; array<int, 1000001> cache...

baekjoon 2800 괄호 제거 2800번 괄호 제거 접근 괄호를 제거할 때 여는 괄호와 닫는 괄호 쌍을 맞추는게 중요한데 이 작업은 stack을 이용해서 했다. 그리고 이진수를 이용해서 어느 괄호를 지울지 경우의 수 생성을 했고 지울 괄호는 N으로 표시했다가 마지막에 N이면 무시하게 해서 괄호를 지웠다. 이번에도 map에 넣어서 자동 정렬시켰...

baekjoon 2230 수 고르기 2230번 수 고르기 접근 모든 경우의 수를 모두 계산하기 위해선 nC2의 횟수가 필요하기 때문에 너무 오래걸린다. 그래서 수 들을 일단 먼저 정렬 시킨후에, two-pointer 방식으로 앞에서부터 차가 너무 작으면 뒤를 늘리고 차가 너무 크면 앞을 늘리고 이런 방식으로 전체를 스캔해들어 간다. 그 숫자들을 또...

baekjoon 20327 배열 돌리기 6 20327번 배열 돌리기 6 접근 3, 4번 연산을 고민을 많이 했었다. 한 칸의 좌표를 기준으로 90도 돌리면 어떻게 바뀌는지 일대일대응 함수를 만들려 하니 어려웠다. 하지만 한 줄씩 돌려버린다 생각하니 쉬웠다. 5~8번 연산을 뭐 전체 블럭을 struct으로 묶어야하나 생각했었는데 그럴 필요 전혀 없이...

baekjoon 31404 아리스, 청소합니다! (Easy) 31404번 아리스, 청소합니다! (Easy) 접근 규칙에 맞게 움직이기만 하면 되지만 나머지는 다 쉬워도 더이상 움직이는게 무의미 해지는 순간을 찾는 것이 조금 어려웠다. 처음에는 전체 칸 수 만큼 움직여도 제거할 수 있는 먼지가 없으면 그렇게 판단 하도록 했더니 틀렸었다. 생각해보니 ...

baekjoon 12781 PIZZA ALVOLOC 12781번 PIZZA ALVOLOC 접근 ccw 알고리즘을 사용한다. ccw(counter clock wise)는 2차원에 있는 세점에 대해 서로의 상대적 위치를 나타낸다. 그리고 ccw는 외적을 이용해서 이를 구해낸다. 오른 나사 법칙에 의해 xyz공간에 xy평면에 세 점이 있다고 치면 두...

baekjoon 4386 별자리 만들기 4386번 별자리 만들기 접근 처음엔 눈치채지 못했지만 이 문제는 전형적인 mst문제이다. 각 별을 모두 연결하는 연결 그래프를 만들고 거기서 mst를 만들면 된다. mst를 만드는 알고리즘으로는 kruskal알고리즘을 사용했다. kruskal알고리즘은 모든 edge를 weight 오름차순으로 정렬해두고 작은...