코딩하기 좋은날

이 문제는 각판을 상하좌우로 움직여서 같은 숫자들끼리 합치는 게임입니다. 이때 한번 움직일때는 이미 합쳐진 숫자끼린 합쳐지지 않는 다는점을 주의 하셔야합니다. 2 2 2 2 가있다면 한번 왼쪽으로 움직이면 8 0 0 0 이 아니라 4 4 0 0 이 됩니다. 먼저 5번까지 움직일수 있으므로 5번 움직이는 재귀함수를 하나 작성합니다. 이 함수내부에서 현재의 배열을 각각 상하좌우로 움직여보고 그 결과값을 호출하는 함수에 전달하면 됩니다. 상하좌우로 움직이는 코드는 저는 각각 함수로 만들었는데 만약 위로 움직인다면 각 열을 기준으로 위에서 부터 아래로 훑으면서 같은 숫자가 있다면 더해서 맨 윗칸에 채우고 다른 숫자라면 이전 숫자를 들어가야 하는 윗칸에 채우는 식으로 채워주었습니다. 아래로 움직인다면 각열을 기준..

최근에 열린 백준 대회의 삼성 코딩테스트 모의고사 두번째 문제입니다. 주어진 땅에 초록색 빨간색 배양액을 먼저 뿌리고 이 배양액들이 상하좌우로 퍼져갑니다. 이때 동일 시간에 서로 만나게 되면 꽃이피게 되고 배양액을 잘 뿌렸을때 최대의 꽃 개수를 구하는 문제입니다. 먼저 배양액을 뿌릴 순서를 정해야 하는데 입력 받을때 배양액을 뿌릴 수 있는 땅의 개수를 세준뒤 그 개수만큼 벡터를 0으로 초기화 시켜줍니다. 이후 초록색 배양액의 숫자만큼 처음에 3을 채워주고 나머지 빨간색 배양액의 숫자만큼 4를 채워주고 정렬을 한번 합니다. 이후 이배열을 next_permutation 해주면 모든 경우의 수를 한번씩 해볼 수 있습니다. 각 인덱스에 해당하는 배양액을 채워준뒤 bfs를 돌리면 됩니다. bfs에서는 cur이라는..

최근에 백준 대회에 열린 삼성 코딩테스트 모의고사 문제중 하나입니다. 나의 N*M노트북에 주어진 스티커를 붙여야 하는데 왼쪽 위를 우선으로 붙여야하고 현재 상태에서 붙일 수 없다면 90도 씩 회전시키며 가능여부를 확인하고 붙일 수 있다면 붙이면서 끝까지 진행 했을 때 노트북에 붙어있는 스티커 수를 세는 문제입니다. 스티커를 90도씩 회전하여야 하므로 우선 배열을 90도 돌리는 함수를 하나 만들어주고, 90도로 돌린뒤에는 행과 열이 뒤바뀌므로 그부분을 따로 변경해주어야 합니다. 판의 좌표를 모두 돌며 현재 이 스티커를 붙일 수 있는지를 모두 확인해주면 됩니다. 주어진대로 열심히 구현하면 되겠습니다. 다음은 코드입니다. #include using namespace std; //스티커는 왼쪽 위를 우선으로 붙..

주어진 문자열에서 가장 긴 팰린드롬 부분 문자열을 찾는 문제입니다. 문자열의 길이가 10만이므로 단순히 찾아보는 방법으론 해결을 할 수 없고 Manacher의 알고리즘을 이용하여야 합니다. 이 알고리즘은 배열에 현재 위치에서 가장 긴 팰린드롬의 길이를 저장함으로써 O(N) 만에 가장 긴 팰린드롬을 찾을 수 있는데 palin[i] -> i를 중심으로 길이가 가장긴 팰린드롬 길이의 절반값을 의미합니다. 이 과정을 거치기전에 짝수 길이 팰린드롬도 찾기 위하여 입력받는 문자열 양단에 #을 모두추가해주고 시작합니다. maxlen이라는 변수에 i+palin[i] 값이 가장 큰 값을 유지시켜 주는데 즉 팰린드롬중 현재 가장 오른쪽 끝에 위치한 부분을 저장 하겠다는 의미입니다. 이 값을 저장 함으로써 다음 인덱스를 진..

이 문제는 주어진 문자열과 T와 P가 주어질때 T에 P가 몇번 등장하는지 찾는 문제입니다. 문자열 최대길이가 100만이므로 단순히 찾는건 불가능이고 KMP 알고리즘을 이용하면 O(N) 만에 해결을 할 수 있습니다. KMP 알고리즘은 종만북을 참고해서 공부했습니다. 처음에 이해가 조금 힘들었지만 테이블 그려보고 보다보면 이해가 되실겁니다! P를 찾아야 하는 문자열이라고 하면 우리는 이 P에 대하여 pi 배열을 먼저 찾아주어야 합니다.(실패 함수라고 부르더라구요.) 이떄 pi[i] 의 의미는 P의 부분 문자열 0~i의 접두사도 되고 접미사도 되는 최대 길이를 의미합니다. 우리는 이 배열을 이용해서 비교하지 않아도 되는 부분을 점프 할 수 있습니다. pi 배열을 구하는 코드와 KMP를 구하는 코드의 함수는 거..

이 문제는 nCk를 구하는 문제이지만 n이 400만으로 굉장히 큽니다. 이항계수는 보통 n이 작을때 nCk = n-1Ck-1 + nCk-1 다음과 같은식으로 동적계획법을 이용해서 구할 수 있지만 이경우 시간복잡도가 O(N^2)이 걸리게 됩니다. 따라서 이문제는 좀더 빠른 방법을 이용하여야 하는데 바로 nCk = n!/k!(n-k)! 식을 이용하는 겁니다. 페르마의 소정리에 따라 n^p-1 = 1 (mod p) 임을 알고 있습니다. 따라서 n^p-2 = n^-1 (mod p) 가되고 결론적으로 우리는 1 / k!(n-k)! 이라는 식을 k!(n-k)!^p-2라는 식으로 치환 할 수 있습니다. 총 정리를 하면 1. 1~n 까지 각 n! % MOD 를 구합니다. ( fac[] 배열) 2. n의 modular ..

볼록 껍질(convex hull) 알고리즘의 기본 문제입니다. 기하는 역시 이것저것 할게 많아서 어려운 것 같습니다 ㅠㅠ.. 진행 순서는 1. y좌표가 가장 작고 그중 x좌표가 가장 작은 점이 나오도록 먼저 정렬을 해서 시작점을 정합니다. 2. 0번째 원소를 시작점으로 두고 나머지 N-1개의 점들을 0번째 점과 각도가 작은 순으로 다시 정렬을 합니다. 3. 이후 스택에 0,1번째 점을 집어넣고 2번째 점부터 스택의 상위 2개에 있는 점과 CCW를 검사해줍니다. 이때 CCW 값이 > 0 이라면 second 점을 포함하고 그렇지 않으면 넣지 않고 진행 해주면 답을 구할 수 있습니다. 각도 정렬 조건 함수 같은 경우 두점과 시작점과 CCW를 하여 이 값이 > 0 보다 크면 좌회전을 했다는 의미이므로 시작점과의..

이 문제는 각역사간 관계가 주어졌을때 각 사건들의 관계를 파악하는 문제입니다. 각 사건들의 전후관계를 알기 위해서는 결국 이 두사건이 한사건에서 다른사건으로 도달 할 수 있느냐를 알면 됩니다. 따라서 주어진 사건의 관계들을 단방향 그래프로 생각하여 사건노드에서 다른사건노드로 가는 경로의 존재유무를 알면 문제를 해결 할 수 있습니다. N이 400이하이므로 플로이드 와샬 알고리즘을 이용하면 모든 사건에 대한 경로를 파악할 수 있습니다. 이때 a,b가 순서대로 주어진다면 dp[a][b] 의 값이 존재하면 a가 더 빨리 발생한 사건이고 dp[b][a]값이 존재한다면 b가 더 빨리 발생한 사건이고 둘다 존재하지 않는다면 둘은 서로 관련이 없음을 알 수 있습니다. 다음은 코드입니다. #include #include..