Coding Test

문제https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커www.acmicpc.net 접근법문제를 이해하는 데 시간이 많이 걸렸다.이 직선을 시계 방향으로 90도 회전하면 ↓ 이고, 이걸 끝 점에 붙이면 아래와 같은 드래곤 커브가 생긴다고 이해해서 문제가 도통 이해가 되질 않았다. 그래서 예제 1번에 있는 3개의 드래곤 커브 중, 3세대까지 진행되는 2번째 예시를 가지고 규칙을 찾아냈다. 문제 하단에 힌트로 그림이 주어져 있어서 다행이였다. (4, 2)에..

문제https://www.acmicpc.net/problem/15684 15684번: 사다리 조작사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선www.acmicpc.net 접근법N이 10이하, H가 30이하이기 때문에 완전 탐색으로 풀어도 되겠다고 생각했다. 그리고 놓여진 가로선의 개수가 최솟값보다 큰 경우와 3보다 큰 경우를 가지치기 할 수 있기 때문에 백트래킹을 사용했다. 문제에서 보여주고 있는 사다리를 2차원 배열로 표현하였고, 아래와 같이 배열의 값을 통해 사다리 존재 여부를 판단했다. 0: 빈칸1: 왼쪽으로 이동할 수 있는 사다리 존재2: 오른쪽으로 이동..

문제https://www.acmicpc.net/problem/14890 14890번: 경사로첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.www.acmicpc.net 접근법각 행과 열 마다 경사로를 설치할 수 있는지 확인하면 된다. 경사로를 설치할 수 있는 조건을 간단히 정리하면 높이의 차가 1인 곳에서 낮은 곳에 L만큼 설치할 수 있는 칸이 존재하면 된다. 나는 (r, c)에서 direction(수평 or 수직) 방향으로 경사로를 설치할 수 있으면 true, 아니면 false를 반환하는 함수를 만들었다. -> 가독성이 안 좋고 어차피 (0, i)와 (i, 0)에서 검사를 시작하도록..

문제https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14QpAaAAwCFAYi  SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 접근법회문의 길이가 정해져있기 때문에 각 위치에서 정해진 길이만큼을 회문인지 아닌지 판단하면 된다. 나는 입력을 2차원 배열로 저장했고, (0, 0)부터 시작한다면 오른쪽(가로 문자열), 아래(세로 문자열)만 확인하면 되기 때문에 이를 참고해서 반복문을 작성했다. 매번 (r, c)에서 회문의 길이만큼 문자열을 만들어서 회문인지 아닌지 판단하는 것은 중복되는 연산이 많이 생길 것이라고 생각해서 슬라..

문제https://swexpertacademy.com/main/code/problem/problemDetail.do SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 접근법알고리즘은 문제에서 말해주는 그대로 100개의 숫자 중 가장 큰 수와 가장 작은 수를 가져와 가장 큰 수는 -1, 가장 작은 수는 +1 해주면 된다. 가장 작은 수와 큰 수를 쉽게 가져오기 위해 배열은 항상 정렬된 상태여야 한다.시간 제한이 20초라 덤프 -> Arrays.sort()를 반복해도 문제가 없을 듯 한데, 나는 배열의 양 끝에서만 이동이 주로 발생하지 않을까? 싶어서 양 끝에서 반복문을 사용해 정렬해주었다. 코드import java.i..

문제https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터www.acmicpc.net 접근법문제 그대로 구현하면 되는 쉬운 문제이다. 톱니바퀴를 나타내는 클래스를 하나 만들고, 시계 또는 반시계 방향으로 움직이는 메서드를 만들었다. 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class ..

문제https://www.acmicpc.net/problem/14502 14502번: 연구소인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크www.acmicpc.net 접근법세로와 가로 크기가 최대 8이기 때문에 3중 for문을 사용해 벽의 위치를 선택해도 된다. 나는 for문이 아니라 재귀 함수를 사용했다. 3개의 벽 위치가 다 정해졌으면 BFS를 사용해 바이러스를 퍼트리고, 바이러스가 다 퍼진 후에는 안전 영역의 개수를 세어 현재 최댓값과 비교했다. 코드import java.io.BufferedReader;import java.io.IOException;import ja..

문제https://www.acmicpc.net/problem/1912 1912번: 연속합첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.www.acmicpc.net 접근법연속된 수의 합을 보자마자 투포인터구나 하고 투포인터로 풀었는데 DP 문제였다. 그런데 채점현황을 보니 투포인터나 DP나 성능 차이는 크게 나지 않는 것 같다. 두 풀이 다 설명해보겠다. 투포인터기본적인 투포인터 문제는 sum의 크기에 따라 오른쪽 포인터가 가리키는 값을 더해주거나, 왼쪽 포인터가 가리키는 값을 빼주어야 하지만 이 문제는 다르다. 누적해서 더해주다가 sum이 음수가 되었을 때 sum을 ..