코테/코드트리

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • 시뮬레이션 1부터 n행까지 돌며 해당 행의 (k, k +m)열의 위치의 값이 모두 0이라면, 다음 행에 넣도록 넘어간다. 모두 0이 아니라면, 해당 행의 바로 위쪽 행에 블록을 넣는다. 💥 유의사항 마지막 행(n)까지 왔을 때는, 마지막 행의 (k, k+m) 위치의 값이 모두 0이라면 마지막 열에 블록을 두고, 0이 아니라면 바로 윗 행에 블록을 두도록 한다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • 시뮬레이션 최대 2*N번 동안 1,2번을 진행한다. ① 구슬들을 구슬 리스트에 저장하고 전부 한 번씩 움직이기 (moveAll()) - 벽이 있으면 방향을 전환하고, 벽이 없으면 한 칸 전진하게 한다. private static Marble moveMarble(Marble mm) { int nx = mm.x + dx[mm.d]; int ny = mm.y + dy[mm.d]; if(inRange(nx, ny)) // 벽이 없는 경우, 한 칸 전진 return new Marble(..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • 백트래킹 (중복 없는 순열) . 중복 없는 순열을 구하듯이 1에서부터 n개를 뽑는 백트래킹을 진행한다. (→ 방문 표시 배열 사용) . 1에서부터 백트래킹을 시도하기 전 방문 배열의 1은 방문 처리하고, 리스트에도 1은 미리 추가해둔다. - 시간 복잡도 : O(N! *N) 💥 유의사항 - 마지막 지점에서 뽑으려는 지점 간 이동 가능해야(= 비용이 0이 아니어야) 이동 가능하다. - 1번 지점으로 돌아오는 처리를 꼭 해야 한다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • 시뮬레이션 완전탐색을 통해 모든 점에 대해 K를 변경하며 채굴할 수 있는 금의 갯수를 센다. 이 때, (금 1개 가격 * 채굴한 금 개수)이 채굴에 드는 비용보다 같거나 큰 경우에만 금의 갯수를 더 큰 값으로 비교해 갱신한다. 💥 유의사항 k의 범위! 격자 내 모든 격자를 덮기 위한 가능한 K의 최대범위 = 가장 거리가 먼 두 점 (좌측 상단-우측 하단) 거리 계산 : 2 * (N-1) + 대각선 길이는 가로나 세로 길이의 2배이므로 2*(N-1)이면 충분히 모든 칸 커버 가능..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • (시작점이 여러 개인) BFS - 처음 상해있는 귤들을 전부 시작점으로 잡아 그 위치들을 큐에 추가하고, BFS는 한 번 수행한다. ▷ 시간 복잡도 : O(N^2) 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 6..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • 다익스트라 (397ms, 29MB) 연산횟수를 저장하는 1차원 int형 배열을 생성해 초기값을 큰 값으로 저장해두고, 시작점 N은 거리를 0으로 설정한다. 연산횟수가 적은 순으로 오름차순 정렬하는 우선순위 큐에 4가지 경우(현재 숫자에서 1을 뺀 경우, 1을 더한 경우, 2로 나눠 떨어질 경우 2로 나눈 경우, 3으로 나눠 떨어질 경우 3으로 나눈 경우)를 추가한다. 그리고 이동했을 때의 연산횟수와 현재 위치에서 1초 지난 값을 비교해 연산횟수 배열을 둘 중 더 값이 작은 값으..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • 시뮬레이션 - 2차원 격자 안에서의 폭발과 중력 적용하기 1) 범위 내의 폭탄을 터뜨린다. → 범위 확인 시, 맨해튼 거리 이용 2) 중력을 적용해 값이 0인 칸은 아래로 떨어트린다. → 새로운 2차원 배열을 생성해 각 열을 아래에서부터 위로 0이 아닌 값으로 채운다. 3) 완성된 임시배열의 결과를 원본배열에 적용한다. 💥 유의사항 맨해튼 거리 식 (|x1 - x2| + |y1 - y2|) 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • 시뮬레이션 필요 변수 - 배열 정보 저장할 int형 배열 arr - 원본 배열의 마지막 인덱스를 나타내는 int형 변수 endOfArr - 삭제한 결과 저장할 int형 임시 배열 tmp (크기 : endOfArr) - 임시 배열의 마지막 인덱스를 나타내는 int형 변수 endOfTmpArr 1) tmp 배열에 (s, e) 범위의 숫자만 제외하고 저장한다. 2) tmp 배열을 arr 배열로 다시 옮긴다. (copy) 💥 유의사항 🔺 코드 1 2 3 4 5 6 7 8 9 10 11..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • 백트래킹 + BFS 필요 자료구조 - dx/dy 배열 - 2차원 격자 저장용 int형 배열 - 2차원 최단 거리 저장용 int형 배열 - 벽 위치 저장할 리스트 - dfs용 뽑은 벽 인덱스 저장할 리스트 - bfs용 방문 표시 배열 - bfs용 위치 저장할 큐 백트래킹으로 없앨 벽 k개를 고른다. 벽 k개를 골랐을 때, 해당 인덱스의 벽을 제거하고 > BFS 통해 최소 시간을 구하고 > 없앴던 벽을 원상복구한다. BFS는 아래 과정으로 진행한다. 1) 방문 배열과 최단 거리 배..