분류 전체보기

[백준] 2527 - 직사각형 (자바/Java)

문제 2차원 격자공간에 두 개의 꼭짓점 좌표로 표현되는 직사각형이 있다. 직사각형은 아래와 같이 왼쪽 아래 꼭짓점 좌표 (x, y)와 오른쪽 위 꼭짓점 좌표 (p, q)로 주어진다. 이 문제에서 모든 직사각형은 두 꼭짓점의 좌표를 나타내는 4개의 정수 x y p q 로 표현된다. 단 항상 x

[SWEA] 1210 - Ladder (자바/Java)

사다리타기에 따라 정답으로 이어지는 시작점을 찾는 문제다. 정답에서부터 위로 올라가는 방식으로 구현하면 된다. 먼저 목적지의 row, col 좌표를 변수에 설정하고, 오른쪽이나 왼쪽 그리고 위로 올라가도록 구현한다. 이때 주의할 점은 위로 가는 것보다 오른쪽 왼쪽이 1인지를 먼저 검사해야 한다. 오른쪽, 왼쪽으로 가고 있다면 반대방향으로 돌아가서는 안된다. 이때 2를 고려하지 않아서 무한루프에 빠지는 문제가 발생했다. 그래서 dir 변수를 지정해줘서 오른쪽, 왼쪽으로 가는 경우는 반대방향이 아닐 경우에만 이동하도록 설정하였다. package SWEA0811; import java.util.Scanner; public class SWEA_1210_Ladder { static int[][] ladder = ..

[SWEA] 5432 - 쇠막대기 자르기 (자바/Java)

이 문제는 '(' 와 ')' 가 연속해서 나올 때는 레이저고, 나머지는 막대로 생각하면 된다. 그러면 입력을 세 가지로 구분할 수 있다. 1. '('가 나오는 경우: 이때는 막대인지 레이저인지 구분할 수 없다. 2. '(' 다음에 바로 ')'가 나오는 경우: 이 경우는 레이저이다. 3. ')' 다음에 ')'가 나오는 경우: 이때는 막대이며, 한 막대가 여기서 끝남을 알려준다. 1의 경우 막대인지 레이저인지 구분할 수 없으니, 일단 bar의 개수에 더한다. 2의 경우는 레이저인게 분명하다. 더해주었던 bar의 개수에서 1을 빼주고, 레이저가 있으면 막대가 두 개로 분열되는 것이니 막대의 수만큼 sum에 더해준다. 3의 경우 막대가 끝났음을 알려주는 것이니 bar에서 1씩 빼준다. sum은 전체 막대의 개수..

[SWEA] 6190 - 정곤이의 단조 증가하는 수 (자바/Java)

주어진 N개의 수에서 가능한 두 수의 곱 중, 가장 큰 단조 증가 수를 찾는 문제이다. 먼저 가능한 두 수의 곱을 이중 for문으로 찾고, 그 수가 단조 증가하는지를 찾으면 된다. 단조 증가 여부를 찾기 위해 정수형 숫자를 String으로 바꿔주고, 각 자리수를 돌며 앞의 자리수가 뒤의 자리수보다 클 경우 false를 return하였다. 또한, 단조 증가하는 수가 없을 경우 -1을 출력하기 위해, result의 초기값을 -1로 설정하였다. package SWEA0811; import java.util.Scanner; public class SWEA_6190_단조증가 { public static void main(String[] args) { Scanner sc = new Scanner(System.in)..

[SWEA] 1954 - 달팽이 숫자 (자바/Java)

2차원 배열의 순회를 활용한 문제이다. while 문을 활용해서 해당 방향의 index를 채우고, array의 끝을 만나거나 이미 방문된 노드를 만났을 때는 방향을 바꾸어 주었다. 각 방향을 1~4로 두고 switch문으로 케이스를 정하였다. case 1: 오른쪽으로 이동: row는 그대로, col을 증가 case 2: 아래로 이동: col은 그대로, row를 증가 case 3: 왼쪽으로 이동: row는 그대로, col을 감소 case 4: 위로 이동: col은 그대로, row를 증가 그리고 1에서 더 나아갈 방향이 없으면 2로, 2에서 3으로 재귀적으로 snail함수를 수행하도록 하였다 그리고 함수를 실행하였을 때 이미 그 칸이 칠해져있다면, 모든 칸이 칠해진 경우이므로 return으로 종료조건을 주었..

[백준] 2567 - 색종이 2 (자바/Java)

문제 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 둘레의 길이를 구하는 프로그램을 작성하시오. 예를 들어 흰색 도화지 위에 네 장의 검은색 색종이를 과 같은 모양으로 붙였다면 검은색 영역의 둘레는 96 이 된다. 입력 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연수는 색종이의 ..

[알고리즘] 카운팅 정렬(Counting Sort) (자바/Java)

목차 카운팅 정렬 데이터끼리 비교 없이 데이터의 개수를 세어 정렬하는 알고리즘 제한 정수나 정수로 표현할 수 있는 자료에 대해서만 한정 데이터의 입력 범위가 제한적인 경우에 효율적 데이터의 수는 적지만, 데이터 값의 범위가 큰 경우(ex. 1~10억) count 배열이 메모리를 과다하게 사용하여 비효율적! 시간복잡도 O(n+k) n: 배열의 길이 k: 정수의 최대값 과정 정렬할 배열에서 가장 큰 정수를 크기로 하는 count 배열을 선언한다.. 데이터 값이 i인 경우, count[i]를 1씩 증가시킨다. count가 모두 끝나면, 앞에서부터 누적합하여 count배열을 수정한다. 기존 배열의 맨 마지막 index부터 정렬을 시작한다. arr[n-1]이 k일 경우, count[k]의 값을 찾아, 그 값을 1..

[백준] 2407 - 조합 (자바/Java) BigInteger 클래스

문제 nCm을 출력한다. 입력 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) 출력 nCm을 출력한다. 굳이 재귀로 팩토리얼을 구하지 않아도 간단하게 풀 수 있지만, 수의 범위가 커서 BigInteger 클래스를 사용해야 한다. package BOJ0809; import java.math.BigInteger; import java.util.Scanner; public class BOJ_2407_조합 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); BigInteger n = new BigInteger(Integer.toString(sc.nextInt())); BigInteger ..

[SWEA] 1208 - Flattern (자바/Java) 배열, 우선순위 큐(힙)

처음에는 ArrayList를 매번 정렬하는 방법으로 풀었는데, 우선순위 큐를 이용하면 더 쉽게 풀릴 것 같아서 두 가지 방법을 모두 써봤다. ArrayList int N = sc.nextInt(); // 덤프 횟수 ArrayList box = new ArrayList(); for (int i = 0; i 0 && dis > 1) { box.set(0, box.get(0) + 1); box.set(size - 1, box.get(size - 1) - 1); Collections.sort(box); di..

[백준] 2564 - 경비원 (자바/Java)

문제 동근이는 무인 경비 회사 경비원으로 항상 대기하고 있다가 호출이 들어오면 경비차를 몰고 그 곳으로 달려가야 한다. 동근이가 담당하고 있는 곳은 직사각형 모양의 블록으로 블록 중간을 가로질러 차가 통과할만한 길이 없다. 이 블록 경계에 무인 경비를 의뢰한 상점들이 있다. 예를 들어 가로의 길이가 10, 세로의 길이가 5인 블록의 경계에 무인 경비를 의뢰한 3개의 상점이 있다고 하자. 과 같이 이들은 1, 2, 3으로 표시되어 있고, 동근이는 X로 표시한 위치에 있다. 1번 상점에서 호출이 들어 왔을 때 동근이가 블록을 시계방향으로 돌아 이동하면 이동 거리가 12가 된다. 반면 반시계방향으로 돌아 이동하면 이동 거리는 18이 된다. 따라서 동근이가 1번 상점으로 가는 최단 거리는 12가..