알고리즘 (364) 썸네일형 리스트형 [C++] 25832번 Making Connections https://www.acmicpc.net/problem/25832 25/01/01 약간의 트릭을 가미한 유니온 파인드 문제다. 이 문제를 참 많이 틀렸었는데... 허무하게 원인을 찾아버려서 글로도 남겨보고, 복습도 해보고자 한다. 문제 접근 방식: 결론적으로 틀린 원인만 말하면 long long이슈다. long long자료형을 써야하는데 int를 써서 값이 이상하게 나왔다. 문제는 두 가지 쿼리를 처리해야한다. 첫번째로 두 노드를 합치는 연산. 두 노드를 합친다면 두 노드는 같은 그룹에 속해있게 된다. 두번째로 그래프의 복잡도를 구하는 연산. 이때 모든 그룹의 크기와 그룹의 개수를 구해야 한다. 유파로 처리해보이는건 당연하고, 두번째를 어떻게 빠르게 처리할 지가 의문일 것이다. 따라서 나는 그룹의 .. [C++] 10246번 부동산 경매 https://www.acmicpc.net/problem/10246 25/01/05 간단한 수식 정리 문제인데, 나이브하게 돌려서 미리 계산해놓고 푸는 풀이도 꽤 빠른 것 같다. 문제 접근 방식: 각 테스트 케이스 별로 다음을 계산하면 된다. 두 수 사이의 연속 된 수들의 합으로 $N$을 표현할 수 있는 경우의 수. 유의할 점은 테스트 케이스의 개수가 안나와있고, 시간 제한은 10초이며, 실제로도 테스트 케이스의 개수가 매우 많다는 점이다. $N$의 범위가 $1 \ 000 \ 000$까지이기 때문에, 어떤 사람들은 미리 그 크기의 배열을 선언해두어 계산을 다 한 후에 쿼리를 처리하는 방식을 하기도 했다.(이 경우 쿼리 당 소요되는 시복도는 상수다.) 나의 경우는 수식으로 접근하여, 쿼리 당 $\mat.. [C++] 28774번 Шестизначные документы https://www.acmicpc.net/problem/28774 25/01/02 백준 땅따먹기에서 나온 문제 중 하나인데, 내가 풀었을 당시에는 골드 4였으나 골드 4치고는 굉장히 어렵다고 느꼈던 문제였다. 이러한 아이디어를 복습해보고자 글을 적어본다. 문제 접근 방식: 일단 문제가 러시아어로 적혀있기 때문에 번역을 하면 다음과 같다. 회계사 발레리(Valeiry)는 회계 보고서에서 불일치를 해결하고 있습니다.그는 총 $n$개의 문서를 확인해야 하며, $i$번째 문서는 여섯 자리 정수 식별자 $a_i$를 통해 회사 네트워크에서 접근할 수 있습니다.역전(inversion)이란, 두 번호 $i$와 $j$($i 배열 ${a_i}$의 복잡성(complexity)은 여섯 자리 각각에서 발생하는 모든 역전의.. [C++] 26648번 물정수열 https://www.acmicpc.net/problem/26648 25/01/04 그리디적으로 생각하면 해결할 수 있는 문제다. 그리디적으로 접근하기 위한 한 가지 핵심적인 관찰이 필요하다. 문제 접근 방식: 한 가지 핵심적인 관찰을 해야한다. 우리는 결국 중앙값이 항상 증가하도록 세 과목 중 한 과목의 점수를 조작할 수 있다.(혹은 조작해야만 한다.) 기존 세 과목의 점수가 $a, b, c$라고 가정하자. 일반성을 잃지 않고, $a 만약 $a$를 더 작게 조작한다고 해도 기존 중앙값 $b$에는 변함이 없다.만약 $a$를 $b$보다 크거나 같고 $c$보다 작도록 조정한다면, 그 조정한 값이 중앙값이 된다.만약 $a$를 $c$보다 크거나 같도록 조정한다면, $c$가 중앙값이 된다. 만약 $b$를 $.. [C++] 1007번 벡터 매칭 https://www.acmicpc.net/problem/1007 24/12/26 약간의 아이디어가 필요한 브루트포스 문제이다. $N$의 제한이 $20$으로 수상하게 작은데, 어떻게 하면 효율적으로 탐색할 수 있는지를 고민하면 해결할 수 있다. 문제 접근 방식: 시작 점과 끝 점을 정해서 이음으로써 하나의 벡터를 만들 수 있다. 이렇게 해서 $N$개의 점으로 $N/2$개의 벡터를 만들 수 있는데, 이 벡터들의 합의 길이의 최솟값을 구하는 것이 문제의 목적이다. $N$의 제한이 $20$으로 수상하게 작은 것을 쉽게 관찰할 수 있는데, 효율적으로 브루트포스를 해야함을 확인할 수 있다. 시작 점 $S$과 끝 점 $E$로 이루어진 하나의 벡터 $\mathbf{V}$가 주어지면, 이 벡터는 시작 점이 $O$이.. [Python] 32871번 돌 게임 nm https://www.acmicpc.net/problem/32871 24/12/03 좋은 아이디어를 가진 게임 이론 문제다. 문제 접근 방식: 문제 접근 방식의 핵심은, 행과 열의 쪼개진 부분을 붙여서 새로운 블록으로 생각해도 상관 없다는 것이다. 예를 들어, 다음과 같다.$3 \times 4$크기의 판에서 $2$번 열을 선택해서 없앴다면,이렇게 그냥 새로운 $3 \times 3$짜리 크기의 판으로 생각해도 된다는 점이다. 편의 성을 위해, $N 그러면, 일단 $N = 1$인 경우 선공이 항상 이김은 당연하다. $N = 2$이고 $M = 2$라면, 선공은 무슨 짓을 해도 $N = 1$인 경우로 되돌아가므로 선공이 진다. $N = 2$이고 $M = 3$이라면, 선공은 $N=2, M=2$인 상태를 상대.. [Python] 9612번 Maximum Word Frequency https://www.acmicpc.net/problem/9612 24/11/30 간단한 실버 문제다. 문제 접근 방식: 각 단어의 빈도 수를 나타내는 딕셔너리 $D$를 선언해준다. 이후 각 단어가 새로 나오면, 그 단어를 딕셔너리에 새롭게 넣고 값을 $1$로 설정, 이미 나왔던 단어였다면 기존 값을 $1$ Increasing하도록 설정했다. 이후 가장 자주 나오는 빈도수를 가진 단어, 그 중에서도 가장 사전순으로 뒤에 있는 단어와 그 빈도수를 출력하면 되는데, 이건 그냥 $D$에 있는 각 단어의 빈도수를 계속 비교하면서 갱신하는 형식으로 구현했다. 파이썬에서는 두 문자열이 사전 순인지를 그냥 맨 처음에는 파이썬 collections모듈의 Counter자료형을 쓸 까 생각했지만, Counter자료형.. [Python] 8094번 Canoes https://www.acmicpc.net/problem/8094 24/11/29 간단한 정렬 + 두 포인터 + 그리디 문제다. 문제 접근 방식: 간단하게 문제를 요약하면 다음과 같다. 카누 한 대에는 최대 사람을 두 명 태울 수 있다. 문제에서 카누 한 대의 최대 중량 제한 $W$를 주고, $N$명의 사람들의 몸무게를 준다. 모든 사람을 카누에 태우려고 할 때, 필요한 카누의 최소 대수를 구하는 것이다. 가장 무거운 사람과 가장 가벼운 사람을 짝지어서 태우는 방법을 먼저 생각했다. 예를 들어 무게 제한이 $100$이라면, $90$과 $10$을 짝지어서 태울 수 있을 것이다. 만약 그게 불가능 하다면, $90$만 먼저 태우고, $10$은 그 다음으로 무거운 사람과 짝지어서 태우면 될 것이다. 그래서 .. 이전 1 2 3 4 ··· 46 다음
