1. 문제  2. 접근우선 그려봤다. N이 2일 때, 4일 때, 6일 때그려보니 4일 때 새로운 경우가 2가지 나오는 것을 알았다. 이것을 제외하면 dp[i-2]*3을 해주면 되는데, 새로운 경우를 어떻게 처리할지 몰랐다.  근데 N이 4일 때 말고도 6, 8... 이 될 때마다 새로운 경우가 아래 처럼 2가지 추가됐다.이 경우를 따로 구해줘야 한다.dp[0] = 1;dp[2] = 3;for(int i=4; i=0; j-=2){ dp[i] += dp[j]*2; }} 만약 내가 구하는 것이 dp[6]이라할 때, 우선 dp[4]에서 3을 곱한다. 왜 3을 곱하냐면 dp[2]가(3x2), 즉 3x2를 구성하는 경우의 수가 3이기 때문이다. 그래서 3x4를 이루는 블록에 3x2 블록을 붙여주는..

1. 문제  2. 접근문제 읽고 평소에 풀던 BFS 문제들이랑 비슷해서 별로 생각 안하고 풀다가 시간초과가 났다. 접근1. 모든 좌표를 다 돌면서 모래성(1~9)인 경우 주변(대각선, 상하좌우)을 체크한 후 무너지면 체크해주기, 그리고 체크 된 모래성들을 한 번에 0으로 표시하기 이렇게 풀었더니 시간초과가 났다. 로직에는 문제가 없는 줄 알고 모든 좌표가 아닌 -> 모래성 좌표만 큐에 저장해서 찾아가는 식으로 바꿔봤다. 하지만 이 방법도 시간초과가 났다. 시간 복잡도를 구해보니 모래성의 크기가 1000X 1000 = 10^6(백만)이고, 모래성의 개수가 평균 50%라고 했을 때 50만이고 BFS니깐 한 파도가 칠 때 평균 50만 * (8방향)이고 파도가 약 (Max(H, W) 이니깐 약 400,000만...

1. 문제  2. 접근부메랑을 만들기 위해서는 3 depth가 필요하고 부메랑을 만든 결과가 이어지면서 탐색을 진행해야한다.-> 백트랙킹 이용 어떤 데이터가 필요?-> 완성된 부메랑과 방문한 좌표를 저장할 boolean 배열, depth depth가 3이 되어서 부메랑이 만들어진 후엔?-> 새로운 부메랑을 만들어야 함. 하지만 다음 좌표의 기준이 모호함. 전체 좌표 중 방문 안한 모든 좌표?이러면 처음 함수를 호출할 때랑 달라지는 것이 없어짐 --> 시도 했지만 시간 초과  다른 방법 부메랑을 만들 때 DFS 방식으로 depth가 3이 될 때까지 계속 호출하는 것이 아닌, 부메랑이 만들어질 수 있는지 바로 체크하기-> 현재 좌표를 제외하면 딱 2좌표만 확인하면 되기 때문에 가능함. 그리고 이 방법은 부메..

1. 문제  2. 접근다각형은 삼각형으로 구성되니깐 한 점을 고정 시킨 다음 두 점을 이동시켜서 삼각형의 넓이를 구해주면 되겠구나 했다.근데 계속해도 틀렸다고 나오길래 포기했다. 나는 처음 들어보는 신발끈 공식을 이용하는 풀이였다. 삼각형은 왜 안되나 봤더니 아래그림에서 점 P2, P3, P4으로 삼각형의 넓이 공식을 적용하면 제대로 된 넓이를 구할 수 없었다.  신발끈 공식은 시계 반대(정) 방향으로 돌면서 두 점을 정해 각 x, y를 곱해주어서 빼준다. 이때 마지막 점은 다시 첫 점으로 돌아와야 한다.코드로 구현하면 다음과 같다.for(int i=0; i 이때 중요한 점은 sum에다가 값을 더할 때 절대값으로 붙이면 안되는 것이다. 다 더한 다음에 결과에 절대값을 붙여야한다. 부호가 다른 것도 다 적..

1. 문제  2. 접근이 문제는 알파벳 N개를 사용해서 최대 연속된 문자열의 길이를 구하는 것이다. 처음에 N이 2로 고정된 줄 알고 완탐 돌릴려고 했는데 1부터 26까지 주어지는 것이었다. 그래서 생각한 아이디어는 set과 투 포인터를 이용한 풀이었다. 중복이 허용되지 않는 set으로 알파벳을 저장하고 set의 사이즈가 N을 넘어가면 사이즈가 N이 될 때가지 빼주면 되겠구나 했다.  하지만 'cacc' 처럼 c가 연속적으로 나오지 않는 경우를 고려하지 못한 풀이였다. 단순히 c를 만나면 다음 문자열이 c가 아닐 때까지 빼주고 c를 set에서 삭제했더니 a 뒤에 나오는 cc를 삭제하지 않고 있었다. 그래서 `HashMap`을 이용해서 카운팅한 문자의 카운트를 저장하고, 값이 0이 될 때 map에서 삭제해..