준카판다

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 2가지 방법이 존재한다. 모든 그래프가 그렇듯이 dfs 또는 노드의 연결(노드의 parent를 저장하여 parent를 방문하는 것이다.) 방법 1. bfs 또는 dfs 나는 bfs방식으로 해결하였다. 우선 전부 입력을 받고 그 값을 vector또는 bool배열에 저장한다. 나는 vector로 저장하였다. 그리고, 차례로 방문하여 해당 ..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 개신기함! 이게 약간 효율적으로 할 수 있는데 그 방법이 생각나지 않았다. 근데 그 방법을 참신하게 한 코드가 있었다. 우선 내가 생각한 방법을 알려주려 한다. 2가지 방법 모두 백트래킹을 이용한 방법이다. 하나는 2개의 배열에 저장하는 형식으로, 나머지 하나는 매개변수로 답을 전달하는 형식으로 하는 것이다. 2개의 배열에 저장하는 형식은 대부분 눈치 챌 것이다. 스타트 팀과 링크 팀을 따로 저장하는 것이다. 그리고 ..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 약간 이 문제를 저번에 사용했던 비트마스킹으로 해결하려 했다. 하지만, 일반적인 dfs와는 다르게 시간이 많이 잡아먹혔다. 그래서 원인을 분석했는데, 그거에 대해 알아보자. 이 문제는 2가지 방법으로 해결가능하다. 방법 1. 비트마스킹 방법 2. 백트래킹을 이용한 브루트포스 방법 1. 비트마스킹 https://jhcard.tistory.com/81 [알고리즘] ..

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 보니까 좌표압축이라는 알고리즘이 존재했다. 그래서 한번 검색을 해서 찾아봤는데, 이상하게 내가 푼 방식이 더 효율적이라 생각한다. 그래서 내가 푼 방식과 원래 이 알고리즘을 해결하는 방식 이렇게 2가지를 소개하려 한다. 이 문제는 하나의 배열을 이용하여 단순 정렬하기에는 어렵다. 하나의 배열을 이용한다면 3번의 정렬이 필요하기 때문이다. - 그래도..

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 보면 간단한 dp문제이다. 하지만, 보다 더 효율적으로 알 수 있는 방법이 존재한다. S3에서 해결하였던 four squares 문제와 비슷하다. https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤..

https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 이 문제는 간단하게 백트래킹을 이용하여 해결이 가능하다. 하지만, TSP알고리즘이라고 다른 방식이 존재한다. 그 방식에 대해 알아보려고 한다. 우선 백트래킹은 브루트포스로 모든 경우를 확인하고, 그 중에서 가장 비용이 적은 경로를 찾아 출력하면 되는 것이다. 간단하기 때문에 코드부터 확인해보자. #include int N, val[10][10], R =..

https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 이 문제는 보면 ''의 기능도 존재한다. 커서가 이동한다는 것이다. 만약 하나의 배열만을 이용하여 커서를 이동시킨 후 삭제를 하거나 추가를 한다면 그만큼 뒤에 있는 수들은 뒤로 한칸씩 전부 밀려나거나 앞당겨 지는 경우가 생길 것이다. 이러한 경우가 계속해서 일어난다면 매우 비효율적으로 수행될 것이다. 그렇기 때문에 다른 방법을 생각해야 한다. 여기에서 그 방법으로 2가지가 존재한다. 1. ..

https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 흔한 브루트포스 문제이다. 이 문제를 3가지 접근으로 해결하였다. 1,2방법은 비슷하지만, 문제를 정확하게 해결하지 못할때 작성한 코드이고, 3방법은 이렇게도 풀 수 있었지 라는 방법이다. 이 문제는 그냥 주어진 땅의 높이 중 가장 낮은 높이 ~ 가장 높은 높이를 하나하나 찾아서 해결하면 된다. 만약 블록을 제거하거나 블록을 위에 놓을 경우 보유한 블록의 수가 -가 나오면 가능한 높이가 아니기 ..