백준

https://www.acmicpc.net/problem/4233 4233번: 가짜소수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, p와 a를 포함하고 있다. 입력의 마지막 줄에는 "0 0"이 주어진다. (2 < p ≤ 1,000,000,000, 1 < a < p) www.acmicpc.net 풀이 사용한 알고리즘 : 분할정복, 소수 구하기 풀이전략 이 문제를 풀기위해서는 소수 구하기와 분할정복 알고리즘을 알아야한다. 1. 소수 구하기 먼저 소수 구하기를 구현한 isPrime 함수부터 설명을 하겠다. static boolean isPrime(long num){ if(num

https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 사용한 알고리즘: 우선순위큐를 사용한 다익스트라 알고리즘 풀이전략 제출하는데 계속해서 42~26% 사이에서 틀렸다는 결과가 나왔다. 거의 1시간 동안 고민을 한 끝에 제출해왔던 코드가 틀린 이유를 찾아냈는데 바로 방문여부를 결정하는 visited를 잘못된 위치에서 값 변경했기 때문이었다. 이미 방문한 위치는 다시 방문하지 않도록 우선순위 큐에 새로운 노드..

https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 풀이 사용한 알고리즘 : 자료구조 중 Map(TreeMap) 풀이전략 해당 문제는 자료구조에 넣을 데이터들이 오름차순으로 정렬되어 저장되면서, 앞뒤로 삽입 및 삭제가 가능해야 한다. 데크를 사용하면 앞뒤로 삽입, 삭제가 가능하겠지만 오름차순으로 정렬시키기가 어렵다. 따라서 Map 중 TreeMap을 사용하여 자료구조 내 데이터를 오름차순으로 정렬하면서도키값을 통해 데이터에 접근해 앞뒤 또는 중..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 사용한 알고리즘 : 다익스트라 풀이전략 우선순위큐를 이용한 다익스트라 알고리즘을 통해 문제를 해결했다. 먼저 특정 위치로 이동했을 때 이동한 횟수를 알기위해 특정 위치와 해당 위치까지의 이동횟수를 저장하는 클래스를 선언한다. 문제에서 최소 이동횟수로 목적지에 도착하는 것이 목표이기 때문에 이동횟수를 우선순위 비교대상으로 삼고, 이를 Comparable 인터페이스를 ..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 사용한 알고리즘 : DP 풀이전략 다이나믹 프로그래밍을 사용해 바텀업 방식으로 풀이하면 되는 문제다. 정수 x에 사용할 수 있는 연산은 3개로, 3으로 나누는 경우, 2로 나누는 경우, 1을 빼는 경우가 있으며 이를 이용해 1을 최종적으로 도출하면 된다. 따라서 기본 세팅값으로 d[0]=0, d[1]=0, d[2]=1, d[3]=1 으로 하고 시작한다. d[i] 는 d[i/3]+1, d[i/2]+1, d[i-1]+1 셋 중 가장 작은 값을 가지면 된다. 따라서 이를 식으로 나타내면 if(i%2==0 && ..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 사용한 알고리즘 : BFS 풀이전략 기존 BFS에서 하나의 조건을 추가해야하는 문제이다. 기본적인 BFS 문제에서는 하나의 지점에서 조건이 충족되는 인접한 지점들을 방문하여 부분 집합의 개수를 구하는 것이 목표였다. 또한 전파가 걸리는 시간을 질문하지 않았다. 하지만 위 문제에서는 하나의 지점이 아닌 여러개의 지점에서 동시에 BFS 탐색이 진행되어야 한다. 그래야만 하루 간 ..

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 www.acmicpc.net 풀이 사용한 알고리즘 : DFS, BFS, 중복순열을 사용한 완전탐색 풀이전략 예외처리해야할 내용들이 많아 평균적인 골드5 문제보다 고생한 문제였다. 기본적인 풀이전략은 0~9까지의 원소들 중 제외된 원소를 뺀 나머지 원소들로 중복순열을 생성하고 목표로 하는 값을 생성한 값으로 뺀 뒤, 생성한 값의 자리수를 더하는 것이다. 예로 입력의 결과로 {0,2,4,6,7,8,9}를 제외시..

https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 사용한 알고리즘 : DFS를 이용한 조합, 백트래킹 풀이전략 조합을 사용하여 가질 수 있는 경우의 수를 모두 구한다. 단, DFS를 사용해 조합을 만들어 가는 과정에서 현재 탐색 노드의 계층이 마지막 최하위 계층과 동일한 경우에서 모음과 자음의 개수가 주어진 조건대로 모음은 한 개 이상이고, 자음은 두 개 이상이어야 한다. 이는 모음의 개수가 한 개 이상이면서 (원하는 결과가 가지는 원소의 개수 ..

https://www.acmicpc.net/problem/10974 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net 풀이 사용한 알고리즘 : DFS로 구현한 순열(Permutation) 풀이전략 순열을 사용하여 주어진 원소들 중 가질 수 있는 모든 경우의 수를 찾는다. 이를 그림으로 나타내면 아래와 같다. DFS를 사용해 완전 탐색을 수행하여 위와 같은 구조를 구현한다. 위 그림에서 맨 윗 노드를 0 계층이라고 하면, 맨 아래 노드는 3 계층(Layer)이다. 코드에서 L은 현재 탐색중인 노드의 계층을, R은 최하단의 계층을 뜻하는데 종료조건은 L==R 로, 현재 탐색 중인 노드의 계층이 최하단의 계..

https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 풀이 사용한 알고리즘 : 그리디, 정렬 풀이전략 먼저 문제에 대한 이해가 어렵기 때문에 아래 그림을 통해 문제 설명부터 하도록 하겠습니다.🎨 위 그림처럼 입력받은 센서들을 오름차순으로 정렬한 뒤에, K개의 집중국을 통해 최소 수신 가능 범위를 구하는 문제입니다. 이를 수학적으로 쉽게 나타내면 아래와 같습니다. 먼저 센서 간의 격차를 구한 뒤 이를 오름차순으로 정렬시킵니다...