본문 바로가기

전체 글

 (215)
메이즈 러너[G3] [실패] 배열 돌리기 이슈로 문제 풀이 실패하였음.. 이후 예술성에서도 똑같은 유형이 나오니 참고할 것. https://www.codetree.ai/training-field/frequent-problems/problems/maze-runner/description?page=1&pageSize=20 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai // 3: 00 (Fail) 중도 포기 //다음에 풀 때는 A4와 종이를 가져오자 //암산으로 못 풀겠음 도형.. //그 외에는 전보다 나아짐 //PQ 통해서 우선순위 골라서 사각형 범위에 맞는 모험가 탐색 -> 이후..
3109 - 빵집(G2) 문제 https://www.acmicpc.net/problem/3109 풀이 문제를 읽어 보자면, 단순 탐색의 시간 복잡도는 3^c * R임을 알 수 있다. 최악의 경우를 고려하면 시간 초과가 날 것이다. 파이프는 겹쳐있을 수 없으므로 성공한 파이프는 그 자리에 유지시켜야 한다. 따라서 파이프가 있는 자리를 따로 표시해야 한다. 일반적으로 for 반복을 돌려 현재 자리에 파이프가 있는 지 체크하고, 파이프가 없다면 파이프를 놓은 뒤 조건이 맞지 않는다면 파이프 되돌리기를 수행한다. (백트래킹) 하지만 해당 문제에서는 이런 방식을 하면 안 되는데 이는 이전 백트래킹에서 새로운 경우의 수를 찾는 과정에서 똑같은 실패 과정을 반복하기 때문이다 (위, 아래, 중간의 세 방향이 있기에 실패가 겹칠 수 있음.) 중..
16236 - 아기상어(G3) 문제 https://www.acmicpc.net/problem/16236 풀이 문제의 핵심은 BFS를 사용하여 가장 가까운 먹이를 찾고 이를 반복하는 것이다. 이 부분에서 문제의 조건인 '먹을 수 있는 물고기가 1마리보다 많다면' 의 조건을 올바르게 구현하는데 많은 시간이 들었다. 첫 번째는 단순히 BFS의 사방 탐색 방향을 조건과 같이 위쪽 / 왼쪽 / 오른쪽 / 아래로 설정했으나, 이러한 방법이 문제가 있다는 사실을 파악하였다. 두 번째로 조건에 맞는 값들을 완전 탐색으로 전부 포집 후, 이를 소팅하려 했으나 의미없는 반복문이 너무 늘어나고 방향성을 수정하게 되었다. bfs문을 돌리면서 상어가 먹을 수 있는 조건의 먹이들을 확인하고 이를 우선순위 큐에 집어넣어 정렬한 뒤 최소값을 찾는 방법을 생각해보..
17144 - 미세먼지 안녕(G4) 문제 https://www.acmicpc.net/problem/17144 풀이 시뮬레이션 문제로, 사방탐색을 제외하면 별도의 특별한 알고리즘은 사용하지 않았다. 대개 헷갈릴 부분이 '미세먼지의 확산'을 구현하는 것이라고 생각되는데, 완전탐색으로 해당 기능을 수행하면 확산이 동시에 일어나는 것이 아니라, 이전 확산 값에 영향을 받는다. 이러한 문제를 해결하기 위해 1. 미세먼지 클래스를 생성 후, 완전탐색으로 조건에 맞는 미세먼지 객체를 생성하여 큐에 저장한다. 2. map(2차원 배열)의 값들을 전부 0으로 초기화하였다. 영향을 받게 하지 않기 위함으로, Dust Class의 내부 메서드로 확산량을 계산 후 값을 더해주는 방식으로 영향을 받지 않게 하였다. 3. 이후 자체 메서드로 구현한 바람으로 인한 ..
1780 - 종이의 개수(S2) 문제 https://www.acmicpc.net/problem/1780 풀이 간단하게 분할 정복으로 풀 수 있는 문제이다. 분할 정복을 사용하지 않으면 시간 초과 문제가 발생한다. 재귀함수를 사용하여 작은 범위로 나눈다. 나눈 범위를 카운팅하며 예외(다른 숫자)가 발생할 시 다음 단계로 분할하고, 아니라면 모두 카운팅 후 값을 증가시킨다. 코드 import java.util.*; import java.io.*; /* 분할 정복 사용. 자세한 것은 세부 주석 참조. */ public class Main { static int[][] board; static int res[] = {0, 0, 0}; // -1, 0, 1 public static void main(String[] args) throws IOE..
2630 - 색종이 만들기(S2) 1. 문제 https://www.acmicpc.net/problem/2630 2. 풀이 색종이를 재귀함수를 통해 반복하여 분할정복하는 문제이다. 해당 문제를 풀기 위해 다음과 같은 방법을 설정할 수 있다. 주어진 색종이가 1 또는 0으로 이루어졌는지 확인한다. 해당 조건일 경우 값을 추가하고, 아닐 경우 4분할을 실행한다. 크기의 경우 size를 통해 확인하고, 분할 시행시 1/2로 줄여준다. 기저조건으로 size == 1을 설정한다. 이를 코드를 통해 보면 다음과 같다. 3. 코드 import java.util.*; public class Main { static int map[][]; static int[] res = new int[2]; public static void main(String[] a..
11404 - 플로이드(G4) 1. 문제 https://www.acmicpc.net/problem/11404 2. 풀이 플로이드 워셜 알고리즘을 사용하여 쉽게 풀 수 있는 문제였다. 다만, 입력값 중 동일 경로에 다른 비용이 존재하는 점, INF 값을 너무 크게 할 경우 오버플로우가 날 수 있다는 점과 적을 경우 값이 적용되지 않는다는 점을 유의하도록 하자. 3. 코드 public class BOJ_11404_플로이드 { static final int INF = Integer.MAX_VALUE / 2 - 1; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System..
16928 - 뱀과사다리게임(G5) 1. 문제 https://www.acmicpc.net/problem/16928 문제 뱀과 사다리 게임을 즐겨 하는 큐브러버는 어느 날 궁금한 점이 생겼다. 주사위를 조작해 내가 원하는 수가 나오게 만들 수 있다면, 최소 몇 번만에 도착점에 도착할 수 있을까? 게임은 정육면체 주사위를 사용하며, 주사위의 각 면에는 1부터 6까지 수가 하나씩 적혀있다. 게임은 크기가 10×10이고, 총 100개의 칸으로 나누어져 있는 보드판에서 진행된다. 보드판에는 1부터 100까지 수가 하나씩 순서대로 적혀져 있다. 플레이어는 주사위를 굴려 나온 수만큼 이동해야 한다. 예를 들어, 플레이어가 i번 칸에 있고, 주사위를 굴려 나온 수가 4라면, i+4번 칸으로 이동해야 한다. 만약 주사위를 굴린 결과가 100번 칸을 넘어간..

티스토리툴바