이분 탐색 문제를 풀어봤었지만 조금만 응용하니까 못 푸는 문제가 발생했다. 이 문제는 이분 탐색으로 상한 과 하한을 구해서 그 길이를 빼서 같은 값의 길이를 구하는 문제이다. 하한을 구하는 메서드에서 만약 찾으려는 값이 arr배열 mid위치의 값보다 같거나 작을 때 end를 mid값으로 바꾸고 조건에 만족하지 않을 때 start를 mid + 1 값으로 바꾼다. 상한의 경우에는 찾으려는 값이 arr배열 mid 위치의 값 보다 크거나 같을 때 start 값을 mid + 1의 값으로 바꾸고 조건에 만족하지 않으면 end 값을 mid 값으로 바꿔준다.
정확한 풀이
import java.util.*;
import java.io.*;
public class Baek10816 {
static int[] arr;
static int n;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
n = Integer.parseInt(br.readLine());
arr = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
int m = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for(int i = 0; i < m; i++) {
int find = Integer.parseInt(st.nextToken());
bw.append((right(find) - left(find)) + " ");
}
bw.flush();
bw.close();
}
private static int left(int find) {
int start = 0;
int end = n;
while(start < end) {
int mid = (start + end) / 2;
if(find <= arr[mid]) {
end = mid;
}
else {
start = mid + 1;
}
}
return start;
}
private static int right(int find) {
int start = 0;
int end = n;
while(start < end) {
int mid = (start + end) / 2;
if(find >= arr[mid]) {
start = mid + 1;
}
else {
end = mid;
}
}
return start;
}
}
직각 삼각형 4153번
내가 떠올린 풀이 해설
단순히 구현문제인것 같다. 하지만 이렇게 코드를 짜면 정답은 나오지만 좋지 않은 풀이인 것 같다. 단순이 if, else if, else로 피타고라스 정리를 이용해 풀었다. 각 변을 제곱해서 두 변을 합한 값이 다른 값과 같으면 right 다르면 wrong으로 풀었다.
정확한 풀이
import java.util.*;
import java.io.*;
public class Baek4153 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int h = Integer.parseInt(st.nextToken());
while(n != 0) {
if((n*n + m*m) == h*h) {
System.out.println("right");
}
else if((h*h + m*m) == n*n) {
System.out.println("right");
}
else if((n*n + h*h) == m*m) {
System.out.println("right");
}
else {
System.out.println("wrong");
}
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
}
}
}
오늘의 회고
오늘은 단순 수학문제와 이분 탐색 문제를 풀었습니다. 이분 탐색 문제를 그 전에도 풀어봐서 금방 해결할 수 있을 것이라고 생각했는데 조금만 응용해서 나오면 풀지 못하는 문제가 발생했습니다. 문제를 해결할 때 넓은 시야로 접근하는 방법에 대해 공부를 해야 될 것 같습니다. 알고리즘을 공부해도 잘 늘지 않는 것 같습니다ㅠㅠ 더 열심히 공부하겠습니다.
위의 코드 if문이 실행되면 소수가 아니므로 isPrime에 false를 하고 break로 빠져나왔다. 마지막에 만약 isPrime이면 cnt를 늘려주는 식으로 소수의 개수를 구했다.
정확한 풀이
import java.util.*;
public class Baek1978 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for(int i = 0 ; i < n; i++) {
arr[i] = sc.nextInt();
}
int cnt = 0;
for(int i = 0; i < n; i++) {
boolean isPrime = true;
if(arr[i] == 1) {
continue;
}
for(int j = 2; j < arr[i]; j++) {
if(arr[i] % j == 0) {
isPrime = false;
break;
}
}
if(isPrime) {
cnt++;
}
}
System.out.println(cnt);
}
}
1654번 랜선 자르기
내가 떠올린 풀이 해설
변수의 크기를 고려해서 변수를 선언해야 된다. 그렇지 않으면 답이 틀렸다고 나온다. 이 문제 또한 기본 이분 탐색 문제이다. 렌선의 최소 길이인 1로 start를 잡고 end는 렌선 배열의 최대 값을 선언해준다. while문에서 start가 end보다 작거나 같을 때까지 반복한다. while문 안에서 이분 탐색으로 총 만들 수 있는 개수를 구해주면 된다.
정확한 풀이
import java.util.*;
import java.io.*;
public class Baek1654 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int k = Integer.parseInt(st.nextToken());
long n = Long.parseLong(st.nextToken());
long[] arr = new long[k];
for(int i = 0; i < k; i++) {
arr[i] = Long.parseLong(br.readLine());
}
Arrays.sort(arr);
long start = 1;
long end = arr[k - 1];
long mid = 0;
while(start <= end) {
mid = (start + end) / 2;
int sum = 0;
for(int i = 0; i < k; i++) {
sum += arr[i] / mid;
}
if(sum < n) {
end = mid - 1;
}
else {
start = mid + 1;
}
}
System.out.println(end);
}
}
오늘의 회고
기본 문제들이라 문제를 해결하는데 어려움은 없었습니다.
제가 이번에 스터디에 참여하게 되었습니다. 주제를 잡고 스터디하는 것이 아니라 모여서 각자 코딩하고 어떤 공부를 하는지 이야기하는 모임입니다. 일요일에 처음 참여하게 되었는데 앞으로도 다른 스터디나 스터디를 꾸준히 할 생각입니다. 스터디에 참여하게 된 이유는 따로 같은 분야에 계신 선배님들을 만날 기회가 없고 스터디 카페에 박혀있어 우울해지는 것 같아 참여하게 되었습니다. 스터디에 계신 분들도 다 저보다 연차가 높은 선배님들이라 열심히 배우겠습니다. 내일은 프로그래머스 중간고사가 있어서 중간고사 시험을 보고 오겠습니다. 중간고사 문제는 외부로 유출이 안돼서 블로그에 작성은 하지 못할 것 같습니다.
단순하게 확률로 풀었습니다. 조약돌 개수를 배열에 담아서 한 색깔의 조약돌만 뽑을 확률을 색깔별로 모두 구하고 각각의 확률을 더해 정답으로 출력했다.
ex) 5개 조약돌이 있는 색만 뽑을 확률 : 5/18 * 4/17
정확한 풀이 1
import java.io.*;
import java.util.*;
public class Baek13251 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int M = Integer.parseInt(br.readLine());
int[] cnt = new int[M];
double sum = 0.0;
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < M; i++) {
cnt[i] = Integer.parseInt(st.nextToken());
sum += cnt[i];
}
int K = Integer.parseInt(br.readLine());
double answer = 0.0;
for(int i = 0; i < M; i++) {
double max = 1.0;
for(int j = 0; j < K; j++) {
max *= (cnt[i] - j) / (double)(sum - j);
}
answer += max;
}
System.out.println(answer);
}
}
81번 순열의 순서
내가 떠올린 풀이 해설
이 문제는 조합 문제와 다르게 순열의 개념을 알아야 풀 수 있다. 순열은 순서가 다르면 다른 경우의 수로 인정된다. N자리로 만들 수 있는 순열의 경우의 수를 구해야 한다는 것이 이 문제의 핵심이다. 먼저 각 자리에서 사용할 수 있는 경우의 수를 구한다. 각 자리에서 구한 경우의 수를 모두 곱하면 모든 경우의 수가 나온다. 4자리로 표현되는 모든 경우의 수는 4! = 24이다. N자리로 만들 수 있는 순열의 모든 경우의 수는 N!이다.
k번째 순열 출력하기
주어진 값(k)과 현재 자리(n) - 1에서 만들 수 있는 경우의 수를 비교한다.
1에서 k가 더 작아질 때까지 경우의 수를 배수(cnt)로 증가시킨다.(순열의 순서를 1씩 늘림)
k가 더 작아지면 순열에 값을 저장하고 k를 k - (경우의 수 * (cnt - 1))로 업데이트한다.
순열이 완성될 때까지 1 ~ 3을 반복하고 완료된 순열을 출력한다.
입력된 순열 순서 구하기
N자리 순열의 숫자를 받아 몇 번째 순서의 숫자인지 확인한다.(현재 숫자 - 자기보다 앞 숫자 중 이미 사용한 숫자)
해당 순서 * (현재 자리 - 1에서 만들 수 있는 순열의 개수)를 k에 더한다.
모든 자릿수에 관해 1 ~ 3을 반복한 후 K값을 출력한다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek1722 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
ArrayList<Integer> arr[] = new ArrayList[n];
StringTokenizer st = new StringTokenizer(br.readLine());
int m = Integer.parseInt(st.nextToken());
long f[] = new long[21];
int[] s = new int[21];
boolean visit[] = new boolean[21];
f[0] = 1;
for(int i = 1; i <= n; i++) { // 팩토리얼 초기화 -> 각 자리수에서 만들 수 있는 경우의 수
f[i] = f[i - 1] * i;
}
if(m == 1) {
long k = Long.parseLong(st.nextToken());
for(int i = 1; i <= n; i++) {
for(int j = 1, cnt = 1; j <= n; j++) {
if(visit[j]) {
continue; // 이미 사용한 숫자는 사용할 수 없음
}
if(k <= cnt * f[n - i]) { // 주어진 k에 따라 각 자리에 들어갈 수 있는 수 찾기
k -= ((cnt - 1) * f[n - i]);
s[i] = j;
visit[j] = true;
break;
}
cnt++;
}
}
for(int i = 1; i <= n; i++) {
System.out.print(s[i] + " ");
}
}
else {
long k = 1;
for(int i = 1; i <= n; i++) {
s[i] = Integer.parseInt(st.nextToken());
long cnt = 0;
for(int j = 1; j < s[i]; j++) {
if(visit[j] == false) {
cnt++; // 미사용 숫자 개수 만큼 카운트
}
}
k += cnt * f[n - i]; // 자릿수에 따라 순서 더하기
visit[s[i]] = true;
}
System.out.println(k);
}
}
}
오늘의 회고
오늘은 조합 중에 좀 어려운 문제 2문제를 풀었습니다. 두 번째 푼 문제는 아이디어를 떠올리는데 안 떠올라서 풀지 못했습니다. 알고리즘 문제를 잘 풀고 싶습니다. 아직은 많이 부족한 것 같습니다. 열심히 나아가겠습니다.
각 건물을 노드라고 생각하면 그래프 형태에서 노드 순서를 정렬하는 알고리즘인 위상 정렬을 사용하는 문제이다. 건물 수가 최대 500, 시간 복잡도가 2초이므로 시간제한 부담은 거의 없다. 입력을 바탕으로 자료구조를 초기화한다 인접 리스트로 그래프를 표현할 때는 인접 노드, 건물 번호를 Node로 선언하여 연결한다. 진입 차수 배열은 [0, 1, 2, 1], 정답 배열은 모두 0으로 초기화한다. 위상 정렬을 실행하면서 각 건물을 짓는데 걸리는 최대 시간을 업데이트합니다. 업데이트 방법은 Math.max(현재 건물에 저장된 최대 시간, 이전 건물에 저장된 최대 시간 + 현재 건물의 생산 시간)이다. 정답 배열에 자기 건물을 짓는 데 걸리는 시간을 더한 후 정답 배열을 차례대로 출력한다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek1516 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
int[] indegree = new int[n + 1];
int[] selfBuild = new int[n + 1];
for(int i = 0; i <= n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
selfBuild[i] = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken());
while(true) {
if(r == -1) {
break;
}
list.get(r).add(i);
indegree[i]++;
}
}
Queue<Integer> que = new LinkedList<>();
for(int i = 1; i <= n; i++) {
if(indegree[i] == 0) {
que.offer(i);
}
}
int[] result = new int[n + 1];
while(!que.isEmpty()) {
int now = que.poll();
for(int i : list.get(now)) {
indegree[i]--;
result[i] = Math.max(result[now], result[now] + selfBuild[now]);
if(indegree[i] == 0) {
que.offer(i);
}
}
}
for(int i = 1; i <= n; i++) {
System.out.println(result[i] + selfBuild[i]);
}
}
}
56번 최단경로
내가 떠올린 풀이 해설
시작점과 다른 노드와 관련된 최단 거리를 구하는 문제이다. 다익스트라 알고리즘의 가장 기본적인 형태를 구현할 수 있는지를 묻는 문제이다. 인접 리스트에 노드를 저장하고 거리 배열을 초기화한다. 거리 배열은 0으로 초기화한다. 최초 시작점을 큐에 삽입하고, 다음 과정에 따라 다익스트라 알고리즘을 수행한다. 마지막으로 완성된 거리 배열의 값을 출력한다.
다익스트라 수행 과정
1. 거리 배열에서 아직 방문하지 않은 노드 중 현재 값이 가장 작은 노드를 선택한다.
2. 해당 노드와 연결된 노드들의 최단 거릿값을 다음 공식을 이용해 업데이트한다.
Min(선택 노드의 거리 배열의 값 + 에지의 가중치, 연결 노드의 거리 배열의 값이 업데이트된 경우 연결 노드를 큐에 삽입)
3. 큐가 빌 때까지 반복한다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek1753 {
static int n,m,k;
static boolean[] visit;
static int[] distance;
static ArrayList<Edge>[] list;
static PriorityQueue<Edge> que = new PriorityQueue<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(br.readLine());
distance = new int[n + 1];
list = new ArrayList[n + 1];
visit = new boolean[n + 1];
for(int i = 1; i <= n; i++) {
list[i] = new ArrayList<Edge>();
}
for(int i = 1; i <= n; i++) {
distance[i] = Integer.MAX_VALUE;
}
for(int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
list[s].add(new Edge(e, v));
}
que.add(new Edge(k, 0));
distance[k] = 0;
while(!que.isEmpty()) {
Edge current = que.poll();
int c_v = current.vertex;
if(visit[c_v]) {
continue;
}
visit[c_v] = true;
for(int i = 0; i < list[c_v].size(); i++) {
Edge tmp = list[c_v].get(i);
int next = tmp.vertex;
int value = tmp.value;
if(distance[next] > distance[c_v] + value) {
distance[next] = value + distance[c_v];
que.add(new Edge(next, distance[next]));
}
}
}
for(int i = 1; i <= m; i++) {
if(visit[i]) {
System.out.println(distance[i]);
}
else {
System.out.println("INF");
}
}
}
}
class Edge implements Comparable<Edge>{
int vertex, value;
Edge(int vertex, int value) {
this.vertex = vertex;
this.value = value;
}
@Override
public int compareTo(Edge o) {
if(this.value > o.value) {
return 1;
}
else {
return -1;
}
}
}
오늘의 회고
오늘은 위상 정렬과 다익스트라 개념 공부와 다익스트라 기본 문제를 풀었습니다. 기본 문제인데 풀기 힘들었습니다. 또한 Do it! 알고리즘 코딩 테스트 (26번 ~ 28번)까지 복습을 진행하였습니다. 처음 알고리즘을 공부할 때는 재미도 없고 알고리즘이 필요가 있을까라는 생각을 했었는데 알고리즘을 공부하면서 점점 재미가 있고 모르는 문제를 고민하면서 해결 능력을 길러나가는 점에서 많은 도움이 될 것이라고 생각합니다. 매일 똑같은 말이지만 오늘보다 나은 내일을 위해 다짐을 한다고 생각해 주시면 감사하겠습니다. 성장하는 저를 위해 꾸준히 천천히 한 발 한 발 나아가겠습니다.
