코딩하기 좋은날

이 문제는 각 행과,열을 길이라고 할 때 지나갈 수 있는 길의 개수를 구하는 문제입니다. 길을 지나간다는 것은 높이가 같은경우 통행이 가능하고 만약 높이가 정확히 1차이난다면 문제에 주어진 길이 L만큼의 경사로를 설치 할 수 있습니다. 이 경사로를 배치하면 그 구간은 지나갈 수 있게 됩니다. 이때 이 경사로는 높이가 더 낮은 곳에만 설치 할 수 있습니다. 즉 정리하면 각 행과 열을 훑어보면서, 높이가 1차이 나는 순간 높이가 더낮은 바닥이 최소 L이상 존재하는지 확인 해주면 되는 문제입니다. 구간을 보면서 현재 연속된 구간의 개수인 curlen을 추가해주며 진행해줍니다. 이때 높이가 1 차이나는 순간을 만났을 때 만약 전에 본 부분이 높이가 낮다면 curlen 이 주어진 길이 L보다 크거나 같은지 확인 ..

이 문제는 해당판에 주어진 5개의 테트로미노를 회전,대칭을 포함해서 놓았을때 가장 큰 값을 구하는 문제입니다. 원하는 테트로미노 모양마다 각칸에 넣어보면 되는 브루트 포스 문제입니다. 그렇다면 존재하는 모든 테트로미노의 모양을 구하는게 핵심인데 ㅗ ㅓ ㅏ ㅜ 이모양 말고는 dfs로 만들 수 있습니다. 그런데 사실 모든 경우를 따져봐도 19가지? 정도가 나와서 저는 그냥 모든 모양을 다 넣었습니다. 문제의 의도는 dfs를 이용하는 것이겠지만 그냥 뭐 이렇게 해도 풀리긴 합니다~. 물론 모양이 더많아지면 이렇게 하면 너무 힘들겠죠,, 다음은 코드입니다. #include using namespace std; int board[510][510]; int one[2][4][4] = { { 1,1,1,1, 0,0,..

이 문제는 각판을 상하좌우로 움직여서 같은 숫자들끼리 합치는 게임입니다. 이때 한번 움직일때는 이미 합쳐진 숫자끼린 합쳐지지 않는 다는점을 주의 하셔야합니다. 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를 구하는 코드의 함수는 거..

이번에도 게임을 하나 만들었습니다! 이번에는 무려 출시를 하려고 마음을 먹었기 때문에 처음으로 만든 것 보다 좀더 생각을 하고 만들었습니다. 대략적으로 말씀드리면 이걸 퍼즐게임?이라고 하면 될까요. n*m의 판이 주어지고 (몇개의 블럭은 이미 칠해져 있을수도 있습니다.) 슬라임이 움직일때 마다 그 블럭이 칠해지게 되고 모든 블럭을 칠해야 하는 게임입니다. 이때 이미 칠해진 블럭으로는 이동이 불가하니 잘 생각해서 이동을 해야 하는 게임입니다. 하나의 스테이지는 이렇게 구성되어 있습니다. 그냥 모든 블럭을 칠하기만 되는 간단한 게임입니다 ㅋㅋ. 터치를 통해 현재 방향에서 상하좌우로 이동이 가능하고 이미 칠해진 블럭은 벽이라고 생각하시면 됩니다. (지나갈 수 없습니다) 총 50개의 스테이지로 구성되어 있습니다..