본문 바로가기

로봇이아닙니다

백준 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이 될때마다 체크를 하지말고, 숫자가 담길떄 마다 체크를 실행하는 것이다. 이런 자잘한 아이디어를 생각해내기 힘들기 떄문에 굉장히 ..
백준 14889 / 스타트와 링크 순열을 이용한 브루트 포스 문제. 아이디어가 필요하다. n의 최대값이 20이기 떄문에 20명으로 구성된 순열에 대해 모든 값을 구하는 건 시간초과가 발생한다 (20!) 그렇다면 20명을 두 팀으로 나누는 아이디어가 필요. 해결법은 0(n/2개)과 1(n/2개)로 구성된 n짜리 배열을 만들고, 첫번째 팀은 0 두번쨰 팀은 1로 배정받는 방식이다. 코드 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788#include#include#include#include#i..
백준 1339 / 단어 수학 순열, 백트래킹을 이용한 문제. 처음에 풀땐 굉장히 헤맸다. 들어간 알파벳의 우선순위를 정하고 우선순위에 맞게 숫자를 부여하는 방식을 사용했었는데, 계속 반례에 걸리는 듯하여 순열을 사용해서 풀어보았다. 여기서 처음 알게된 유용한 함수가 있다. 바로 vector안의 중복된 것들을 모두 지워주는 함수. v.erase(unique(v.begin(), v.end()), v.end()); unique 함수는 vector 내부의 중복된 값들을 맨 뒤로 정렬하고, 자신이 바꾼 vector의 end() 부분을 반환한다. 그 부분만 erase해주면 중복제거가 된다. 또 string s 에 대해 for(char x : s)를 사용하면 x가 s의 한 글자씩 입력받는다는 사실도 처음 알았다. 두 개다 유용한 함수니 기억해두..
백준 2529 / 부등호 순열을 먼저 만들고, 그 사이사이에 입력된 부등호를 껴놓은 후 모든 조건을 만족하면 출력하는 문제. n개의 숫자로 모든 순열을 만들어보는 함수인 next_permutation과 prev_permutation이 있음을 잊고 있었다. next_permutation은 오름차순이기 때문에 최소값을 구할 때 쓰고, prev_permutation은 내림차순, 최대값을 구할 때 쓰면 된다. 코드 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include#include#include#include using namespace std; int n;vec..
백준 6064 / 카잉 달력 정확히 1년전에 풀어봤던 문제. 그때는 막 공약수도 구하고 복잡하게 풀었던 거 같은데. 강의를 보니 꽤 쉽게 풀리는 문제였다. 우선 year를 1씩 늘려가며 푸는 방식은 m,n의 제한이 4만이기 떄문에 시간초과가 발생한다. 카잉달력에서 앞자리와 뒷자리를 1씩 빼본 것이다. 1을 뺴보니 정확히 눈에 띄는 특징이 생긴다. 23을 예로 들면, 23을 5로 나눈 나머지가 3이고 7로 나눈 나머지가 2, 즉 가 됨을 알 수 있다. 이 패턴을 발견하면 쉽게 풀 수 있다. 코드 12345678910111213141516171819202122232425262728293031323334353637383940#include#include#include#include using namespace std; int main()..

티스토리툴바