본문 바로가기

BOJ

백준 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..
백준 14391 / 종이 조각 문제를 풀 방법을 궁리하는데 꽤 걸렸다. 내가 발견한 해결책은 예를 들어 2x2라면 0000,0001,0010........1111(총 16가지)를 배열에 넣고 (넣는 방법은 이진수를 이용했다) 0이면 가로 1이면 세로로 정한다음 가로로 한번 읽어 생긴 값과 세로로 한번 읽어 생긴 값을 더하는 것이다. 어려운 문제처럼 보이지만 해결법만 찾으면 그리 어렵지 않게 풀 수 있는 문제다. 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949..
백준 2580 / 스도쿠 백트래킹로도 풀 수 있지만 충분히 DFS로도 가능한 문제. 처음에 접근을 잘못해서 굉장히 헤멨다. garo[i][j]는 i 번쨰 가로에 j라는 수가 들어갔는지를 나타내는... 식으로 sero와 sq를 선언했다. 그중에서도 3X3 구역을 정하는 3*(x/3) + (y/3) 같은 수식을 만들어내는 머리가 필요한 문제다. 코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889#include#include#include#includeusing namespace ..
백준 9663 / N-Queen 어느 기업 입사 문제라던데, 생각해내기 너무 힘들어서 결국 답을 봐버렸다. 이 문제는 진짜 머리가 좋아야 풀 수 있는 거 같다. n의 최대값이 15이기 때문에 최적화를 해야되는 문제. 아이디어는 이렇다. 모든 행과 열에 하나씩 놓여야하는 건 기본, 대각선이 문제인데, 대각선을 체크하는 배열을 1차원으로 선언해야한다. /의 경우, (row+col)의 값이 일정함을 이용. /(의 반대대각선)의 경우, (row-col+n)의 값을 일정함을 이용. 한 행마다 퀸을 하나씩 추가하는 방식으로, 추가하기전 체크를 해주고 추가하는 방식으로 풀 수 있다. 아마 시간초과 때문에 이렇게 최적화를 한것 같다. n이 작다면 그냥 2차원 bool 배열로 쉽게 풀 수 있다. 코드 1234567891011121314151617181..
백준 1248 / 맞춰봐 문제 설명에 온갖 말장난을 쳐놔서 이해하는데 오랜 시간이 걸렸다. 요약하자면, -10~10, 총 21개의 수로 입력받은 결과를 만족하는 n개의 수를 찾는 문제. 중복이 가능하기 떄문에 총 21^n개의 경우의수가 발생한다. (n=10일 경우 시간초과가 무조건 발생한다) 그렇기에 몇몇 체크를 추가하여 걸리는 시간을 줄여야 한다. 여기서 관찰력과 아이디어가 필요한데, 입력받은 부호(-,0,+)중 S[i][i]는 i의 부호를 말하고 있다는 점이다. 그러나 이 점을 활용하여 코드를 구성해도 시간초과가 걸린다. 여기서 또 하나 체크를 추가해주어야한다. 정답 배열 ans에 담긴 숫자가 n이 될때마다 체크를 하지말고, 숫자가 담길떄 마다 체크를 실행하는 것이다. 이런 자잘한 아이디어를 생각해내기 힘들기 떄문에 굉장히 ..

티스토리툴바