본문 바로가기
백준 1525 / 퍼즐 나올 수 있는 경우의 수가 총 9!. 그러나 현 퍼즐의 상태를 저장하기 위해선 (빈칸이 0이라 가정하고) 최대 876543210 짜리 배열이 필요하다. (약 4기가) 무조건 메모리초과가 난다. 이 문제를 해결하기 위해선 map이란 클래스가 필요하다. map은 쉽게 생각해서 map["string"]이나 map[92342384023] 같은 일반적인 배열이 할 수 없는 것들을 가능하게 하는 자료구조다. ( ) 문제에서 사용된 map의 기능은 count. map.count("바보")는 "바보"란 스트링이 한번이라도 들어갔으면 1, 들어간 적이 없으면 0을 출력하는 기능이다. (BFS 문제에 자주 사용되는 부울 배열의 기능과 같다.) 또한 코드는 string의 기능을 잘 이용해야 쉽게 풀 수 있다. string...
백준 1208 / 부분집합의 합 2 굉장히 어려운 문제. 부분집합의 합이라 나올 수 있는 경우의 수의 최대가 2^40. 시간초과가 난다. 그러하므로 n을 2로 나눈 후 두 경우로 나누어 해결해야한다. n을 2로 나눈 후 두 경우로 나누어 해결하는 알고리즘을 Meet in the middle, MITM이라 부른다고 한다. 1. n개의 수를 n/2짜리 배열과 n/2짜리 배열 두 개로 나누어 담는다. 2. 각각의 배열에 담긴 수의 부분집합의 합을 모두 구하여 새로운 배열 n1, n2에 담는다. 3. n1의 인덱스 하나 n2의 인덱스 하나를 합한 값을 정답 s와 비교하여 체크한다. (투 포인터스 알고리즘 이용) 여기서 가장 어려웠던 건 투 포인터스 알고리즘을 이용하는 법이다. 위의 배열이 n1, 밑의 배열이 n2라 가정하자. n1은 시작 인덱스부..
백준 1644 / 소수의 연속합 일단 n 이하의 소수를 모두 구해놓으면 투 포인터스 알고리즘을 통해 O(n)만에 답을 구할 수 있지만 n의 제한이 400만이기 때문에 400만 이하의 소수를 모두 구하는 것은 빠른 시간내에 불가능하다. 400만이하의 어떤수 i를 2부터 루트 i까지 나누어 본 다음, 나눠지지 않으면 소수로 판별하는 알고리즘이 있지만 이마저도 느리다. 해답은 에라토스테네스의 체 어떤 소수를 구하면 그 소수의 배수들을 모두 체크하는 방법이다. 에라토스테네스의 체를 사용하면 빠르게 해결가능하다. 코드 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include#..
투 포인터스 알고리즘 (Two Pointers Algorithm) 투 포인터스 알고리즘 (Two Pointers Algorithm) 절대 정답이 되지 않는 경우를 Skip하는 알고리즘. 보통 a부터 b까지의 합이 ~되는 경우를 묻는 문제에서 이중 포문을 사용해야하는데 경과되는 시간을 줄이기 위해 사용하는 알고리즘이다. 위의 배열에서 i번쨰 인덱스부터 j번째 인덱스까지 합이 7이 되는 경우의수를 모두 구하는 문제라 가정해보자. (배열의 길이가 짧아 이중포문을 사용하면 금방 구할 수 있지만 배열의 크기가 어느 수준 길어지면 시간초과가 발생한다.) 투 포인터스 알고리즘은 Left (시작:0), Right (시작:0)을 선언하고 Right를 한칸씩 이동시키면서 답을 찾으면 Left를 한칸 이동시키는 알고리즘이다. Right를 이동시켜줄떄마다 변한 Right에 위치하는 값을 s..
백준 1806 / 부분합 이중포문을 사용하면 쉽게 풀릴 것 같지만 n의 최대값이 100000이라 시간초과가 무조건 발생한다. 이중포문을 사용하면 O(N^2)의 시간복잡도가 발생하지만 투 포인터스 알고리즘(Two Pointers Algorithm)을 사용하면 O(N)으로 줄일 수 있다.https://naivep.tistory.com/52 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include#include#include#include using namespace std; int arr[100000]; int main() { //freopen("Text.txt", "r", stdi..
백준 12100 / 2048 (Easy) 2048 게임 주어지는 상황 (보드의 크기 최대 20x20)에서 최대 5번 굴려서 나오는 가장 큰 블록의 값을 출력하는 문제다. 5번 굴리는 것부터 먼저 정했다. 직전에 풀었던 구슬 게임과는 다르게 같은 방향으로 두번 이동하는 것이 의미가 있기 때문에 총 경우의 수는 4^5=1024번이다. 1024번의 경우의 수에 대해 기울여서 숫자를 모으고 합치는 알고리즘은 1. 사이사이 끼어있는 0을 없앤다. (ex 20204 -> 00224) 2. 옆에있는 숫자가 같을 시 합친다. (ex 00224 -> 00404) 3. 1을 반복한다 (ex 00404 -> 00044) 로 구성했다. 코드 (코드가 굉장히 더럽다. 동,서,남,북으로 기울이는 코드가 서로 다르기때문에 귀찮아도 각각 짰다) 123456789101112..
백준 13460 / 구슬 탈출 2 (해결) 캐도캐도 끝없이 반례가 나온다. 정신나간다. 내 코드는 500줄 가까이되도 정답이 아닌데 다른 정답코드를 보니 100줄만 되도 맞더라. 다음에 다시 꼭 풀어볼문제. 코드가 굉장히 더럽다. 반례 https://www.acmicpc.net/board/view/23382 풀었다. 해답은 '10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.' 에 있다. 판을 기울이는 모든 경우에 대해 생각해보자. 일단 첫번째, 오,왼,위,아래로 기울일 수 있다. 그다음 두번째도 물론 오왼위아래로 기울일 수 있지만, 잘 생각해보면 오오, 왼왼, 위위, 아래아래가 의미가 없다. 또한 오왼, 왼오, 위아래, 아래위는 구슬의 위치가 다시 돌아옴으로 이것또한 의미가 없다. 그렇다면 오아래, 왼아래, 왼위,..
백준 1062 / 가르침 단어들이 anta- -tica로 이루어져 있기 때문에. a,n,t,i,c 중 하나도 모르면 모든 단어를 읽을 수 없다는 점을 이용해서 시간초과를 극복했다. 우선 모든 단어들을 한 벡터에 넣고 중복을 제거, k개의 알파벳을 아는 모든 경우에 대해 a,n,t,i,c 중 하나라도 모르면 continue. 비트마스크를 이용하면 더욱 시간이 짧아진다고 한다. 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102..

티스토리툴바