본문 바로가기

728x90

java39

[BOJ] 2512번 - 예산 (Java) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 이 문제를 처음 봤을 때 당연히 이분탐색으로 풀어야 겠다고 생각했다. 구해야할 상한액을 [0 ~ 요청할 금액 중 가장 큰 값] 구간에서 이분탐색을 한다. 아래의 코드는 이를 구현한 것이다. 이때 solve(mid) 는 배정된 예산의 합을 반환한다. 이를 기준으로 start와 end를 변경해가며 최대 상한액을 찾는다. int start = 0; int end = max; while(start m) { end = mid - 1; } else { start = mid + 1; } } bw.write(end + ""); 하지만 두번째 방법이 생각나서 이 글을 작성해본다. 일반적으로 공평하게 받을 수 있는 상한액 = 총 예산 / 지방의 수 = m / n 만약에 총 예산이 요청한 예.. 2024. 1. 15.

[BOJ] 13904번 - 과제 (Java) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 이 문제에서 핵심은 마감기한이다. 우선 당연히 점수가 최대로 되려면 과제에 부여된 점수가 큰 것을 해야한다. 하지만 마감기한이 지나면 아무리 높아도 쓸 수 없다. 위의 그림과 같이 예제를 2가지 방법으로 정렬해보았다 마감기한을 오름차순으로 정렬, 마감기한이 같으면 점수는 내림차순으로 정렬 마감기한을 내림차순으로 정렬, 마감기한이 같으면 점수는 내림차순으로 정렬 1. 마감기한을 오름차순으로 정렬한 후 1일부터 확인하기 1일째 : 1, 2, 3, 4, 4, 4, 6 2일째 : 2, 3, 4, 4, 4, 6 3일째 : 3, 4, 4, 4, 6 4일째 : 4, 4, 4, 6 5일째 : 6 6일째 : 6 수행할 수 있는 과제는 과제를 수행하는 날짜에 따라 다르다. 1일째에 어느 문.. 2024. 1. 5.

[BOJ] 31066번 - 비 오는 날 (Java) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 2023.12.30일에 처음으로 SciOI 2023 Open Contest · Arena #16 에 참가했다. 코딩테스트를 본다는 생각으로 긴장감을 가지고 시작했다. 이 문제가 첫 문제였다. 당시에 너무 복잡하게 생각했는지 꼬여버렸던 문제를 오늘 다시 정리해서 풀어보았다. 풀이 과정에서 2가지 문제를 알게되어 이를 정리하려고 한다. 1. 틀린 예외처리 if(m == 1 && k == 1) return -1; 처음에는 위와 같이 우산이 1개이고 우산을 쓸 수 있는 사람 수가 1명일 경우에는 무조건 불가능하다고 했다. 하지만 만약에 사람이 건너야 하는 사람이 1명이면 이 경우에도 불가능할까? 내가 생각하지 못했던 부분 첫번째였다. 사람이 1명일 경우에는 1회로 가능하다는 것을.. 2024. 1. 2.

[BOJ] 12919번 - A와 B 2 (Java) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 입력으로 주어지는 문자열의 길이도 크지 않고 연산도 간단해서 아래와 같이 코드를 작성했다. public static int solve(String s, String t) { if(s.length() == t.length()) { if(s.equals(t)) return 1; return 0; } String s1 = s + "A"; String s2 = new StringBuffer(s + "B").reverse().toString(); if(solve(s1, t) == 1 || solve(s2, t) == 1) return 1; return 0; } 문자열 s에 연산을 해나아가며 문자열 t와 같아지는지 확인했다. 하지만 결과는 시간초과가 떴다. 위와 같이 풀이를 할 경우.. 2023. 12. 24.

[BOJ] 10942번 - 팰린드롬? (Java) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 팰린드롬이란? 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열(sequence of characters) 등 즉, 앞뒤로 읽어도 똑같다! (ex. 토마토) [위키] https://ko.wikipedia.org/wiki/%ED%9A%8C%EB%AC%B8 이는 3가지 경우로 나누어 볼 수 있다. 길이가 1인 경우 1, 2, 3, a, b, c 무조건 팰린드롬이다. 길이가 2인 경우 11, 22, 33, aa, bb, cc 두 문자가 같을 경우에만 팰린드롬이다. 길이가 3이상인 경우 121, aba 맨 앞의 문자와 맨 끝의 문자가 같고 중간의 문자열이 팰린드롬일 경우에만 팰린드롬이다. 위의 성질을 이용해서 문자열에서 어느 부분이 팰린드롬인지 알아낼 수 있다.. 2023. 12. 22.

[BOJ] 17609번 - 회문 (Java) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 이 문제는 회문을 알아내는 것이다. 단, 1개를 제거하면 회문이 되는 것도 알아내야 한다. 이 부분에서 반례를 확인하고 고치는 과정을 정리한다. 회문의 특성으로 가운데를 기점으로 양쪽이 같아야 하므로 start, end를 두어 비교했다. 처음에 내가 회문인지 알아내는 함수를 작성한 코드는 아래와 같다. public static int isPalindrome(String s) { int start = 0; int end = s.length() - 1; int count = 0; while(start 1) { break; } } if(count > 1) { return 2; } return count; } 그냥 단순하게 생각하여 start와 end 위치에 있는 문자가 같지 않.. 2023. 12. 13.

[BOJ] 1806번 - 부분합 (Java) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ start : 현재 누적합의 시작 인덱스 end : 현재 누적합의 끝 인덱스 sum : nums[start] + .... + nums[end] 의 합 sum 이 s 이상이면 (end - start + 1) 수열의 길이 비교 sum이 s 초과이면 start++ 하여 sum 감소시키기 아니면 end++ 하여 sum 증가시키기 단, end == n이 되는 순간 배열의 범위를 넘어갔기 때문에 중단해주기! 위의 설명을 나의 풀이이다. 이 문제를 풀면서 end가 n이 되는 순간의 예외처리를 잘못해서 계속 틀렸었다. 그래서 다른 사람의 풀이를 참고하다 보니 나와 다른 점이 있어서 이를 기록하다. 다른 사람의 풀이에서는 start부터 end-1 인덱스까지의 합을 누적합으로 보았다. 그래.. 2023. 12. 12.

[BOJ] 11779번 - 최소비용 구하기2 (Java) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 우선 오늘 이 문제를 푸는데 가장 많이 삽질한 시간은 예제를 맞추려고 노력한 시간이다. 이와 비슷한 문제를 풀어본 경험이 있어 원리를 알고 있었고 예제를 믿고 바로 풀이에 들어갔다. 그러나 계속해서 경로가 예제 정답과 다르게 [1, 4, 5]로 출력이 되었다. 초반에는 문제가 틀릴 것이라고 생각하지 않고 내 코드만 계속해서 확인했다. 하지만 아무리 오류를 찾아보려고 해도 발견되지 않았고 예제를 직접 손으로 풀어보니 실제 경로가 [1, 4, 5]가 맞았다. 이번에 느낀 것은 아무리 원리를 알고 있더라도 직접 답을 구해보며 문제 풀이에 접근해야겠다!!!! 삽질한 시간은 아깝고 허무했지만.. 다음부터 실수를 반복하지 않으면 된다..! ※ Comparable public stat.. 2023. 12. 8.

[BOJ] 13270번 - 피보나치 치킨 (Java) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 계속 풀어보았지만 실패해서 다른 사람의 풀이를 참고한 내용을 바탕으로 내가 이해한 내용을 정리한다. 처음에는 사람 수, 치킨 수의 피보나치 수열을 분리해서 생각하여 이에 대한 연관성을 생각하지 못했다. 그러나 위의 그림과 같이 두 변수 a와 b가 있다고 생각해보자. 처음 a와 b가 1닭 2인을 나타내고 있으면 다음 a와 b의 값은 2닭 3인이 되어야한다. 즉, a = b, b = a+b 로 값이 변한다는 것이다. 여기서 우리가 구해야할 것은 최소 치킨 수와 최대 치킨 수이다. min 배열 : min[i] 는 i인분 시켰을 때 최소 치킨 수 max 배열 : max[i] 는 i인분 시켰을 때 최대 치킨 수 단, 이 배열은 항상 길이가 3이상일 것이다. 또한 [0, 1번 인덱스.. 2023. 12. 6.

[BOJ] 12851번 - 숨바꼭질2 (Java) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 이번 문제에서 내가 잘못 생각했던 부분에 대해 기록해두려고 한다. 우선 기억해야할 것은 BFS는 무방향 그래프에서 최단경로를 구할 수 있다. 즉, 처음 동생의 위치에 도착하면(answer = 0) 그 때 시간이 최소시간이 된다. 여기까지만 생각하고 작성한 코드 중 queue 삽입과 관련된 코드이다. 위와 같이 단지 next위치에서 도달한 시간이 최소 시간보다 작으면 무조건 queue에 넣도록 했다. 하지만 메모리 초과가 발생했고 그 이유에 대해 생각해보았다. 현재 코드로는 도착지점과 현재 지점의 거리와 상관없이 현재 시간이 최소 시간보다 작으면 무조건 큐에 삽입했다. 그러면 절대 최소시간에 도착할 수 없는 경우도 큐에 존재하며 메모리 초과가 발생할 수 있다. 최악의 경우를.. 2023. 12. 4.

[Java] MacOS JDK 삭제 ※ 기존에 설치된 jdk11을 삭제하고 jdk17을 설치하던 중 어려움 기록 ※ 1. jdk 11 을 삭제하지 않고 jdk 17을 설치한 후 java -version을 입력하면 아래와 같은 오류 발생 java - version Unrecognized option: - Error: Could not create the Java Virtual Machine. Error: A fatal exception has occurred. Program will exit. 다른 블로그의 글을 참고하여 brew로 설치하고 환경 변수(~/.zshrc) 설정까지 완료 그러나 2개의 jdk가 존재하여 위의 오류가 발생 2. jdk 11 경로 찾기 terminal에서 경로를 찾아가려 했지만 존재하지 않는 Java 디렉토리라는 문.. 2023. 11. 27.

[Programmers] 택배 배달과 수거하기 (Java) 🛠️ 문제 🛠️ 당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. → deliveries 의 길이 = pickups의 길이 = n 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다. 배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n) 트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. → 배달하거나 수거할.. 2023. 11. 9.

[Java] Type & BigInteger 한동안 python으로만 코테를 준비했다. 그러나 취업을 준비해보니 Java가 필요하다는 것을 느꼈다. 너무 오랜만에 Java로 문제를 풀다보니 Number format 오류가 발생했다. 그래서 원시 타입을 정리하고 문제 풀이에 사용한 BigInteger를 정리해보려고 한다. 1. Primitive type 원시 타입(Primitive type) 이란? : 정수, 실수, 문자, 논리 리터럴을 직접 저장하는 타입 종류 기본 타입 메모리 사용량 값의 범위 정수 byte 1byte 8bit -2^7 ~ 2^7-1 (-128 ~ 127) short 2byte 16bit -2^15 ~ 2^15-1 (-32768 ~ 32767) int 4byte 32bit -2^31 ~ 2^31-1 (-2147483648 ~ 21.. 2023. 11. 2.

[BOJ] 6064번 - 카잉 달력(JAVA) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 중국인의 나머지 정리 참고 블로그 https://blog.joonas.io/23 중국인의 나머지 정리 - 이해하기 쉬운 설명 중국인의 나머지 정리(CRT; Chinese Remainder Theorem)연립 합동식의 유일한 해를 찾는 정리이다. 예를 들면서 설명과 함께 전개하는 게 가장 이해하기 쉽다. 개념 이해를 위해 연립 합동식이 2개일 때 blog.joonas.io 나머지 연산을 사용해보려고 했지만 어려워서 구현 실패 그래서 문제 풀이 블로그를 참고했는데 여기서 내가 이해한 부분을 정리하기 위해 글을 작성 문제풀이 참고 블로그 https://girawhale.tistory.com/10 [백준] 6064번: 카잉 달력 - JAVA 문제 링크 BOJ 6064번: 카잉 .. 2023. 3. 27.

[BOJ] 2667번 - 단지번호붙이기(JAVA) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 시작 정점 찾기 이미지 상으로 확인했을 때 왼쪽 위 > 오른쪽 위 > 왼쪽 아래 > 오른쪽 아래 와 같이 Z 모양으로 시작 정점을 찾는다. 현재 위치의 값이 1이면서 방문하지 않으면 시작 정점이다. 시작 정점을 기준으로 그래프 탐색 BFS 그래프 탐색 사용 대각선을 제외한 상하좌우 위치에 아파트가 있으면 현재 단지에 있는 아파트 수 증가 BFS 탐색이 끝나면 탐색한 아파트 수 반환 탐색이 끝나고 아직 남은 정점이 있으면 ①,②번 과정 반복 모든 정점의 탐색이 끝나면 올바른 형식으로 출력 후 프로그램 종료 ★ 아파트 단지내에 있는 아파트 수를 저장하는 배열(aparts[]) 초기화 ★ 🍀 풀이 코드 🍀 import java.io.BufferedReader; import ja.. 2023. 3. 23.

[graph] 너비 우선 탐색(BFS, Breadth First Search) 너비 우선 탐색(BFS, Breadth First Search) 시작 정점으로부터 인접한 정점들을 모두 차례로 방문한 후 방문했던 정점을 다시 시작점으로 하여 인접한 정점들을 차례로 방문하는 방법 가까운 정점들을 먼저 방문하고 멀리 있는 정점들은 나중에 방문하는 순회 방법 인접한 정점들에 대해 차례로 다시 너비 우선 탐색을 반복해야 하므로 선입선출(First-IN First-Out) 구조인 큐(Queue) 사용 BFS 수행순서 큐가 공백이 될 때까지 빨간 상자 부분을 반복한다. BFS 과정 표현 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ Queue가 비었으므로 탐색 종료 결과 : 1 → 2 → 4 → 3 → 5 인접 행렬로 구현한 그래프 BFS static void BFS(int[][] graph, int v) { /.. 2023. 3. 7.

[graph] 깊이 우선 탐색(DFS, Depth First Search) 그래프 순회(Graph Traversal) 또는 그래프 탐색(Graph Search) 란? 하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한번씩 방문하는 것 깊이 우선 탐색(DFS, Depth First Search) 시작 정점에서 한 방향으로 갈 수 있는 가장 먼 경로까지 깊이 탐색해가다가 더 이상 갈 곳이 없으면 가장 마지막에 만났던 간선이 있는 정점으로 되돌아와서 다른 방향의 간선으로 탐색을 계속함으로써 모든 정점을 방문하는 순회방법 마지막 갈림길로 되돌아가야하므로 후입선출(Last-IN-First-Out) 구조인 스택(Stack) 사용 사실상 백트래킹과 똑같은 개념을 사용한다. DFS 수행 순서 스택이 공백이 될 때까지 빨간 상자 부분을 반복한다. DFS 과정 표현 ↓ ↓ ↓ ↓ ↓ ↓ ↓ .. 2023. 3. 6.

[graph] 인접 리스트로 방향 그래프 구현하기 ★ 정점의 개수 n개 , 모서리의 개수 m개 ★ 앞선 무방향 그래프 구현한 게시글과 마찬가지로 리스트의 각 노드는 정점을 저장하는 필드와 다음 인접 정점을 연결하는 링크 필드로 구성된다. 정점 i의 진출 차수 = i의 노드의 수 ex) 정점 2의 진출 차수 = 2 JAVA 자료구조 구현 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; import java.util.StringTokenizer; class Node { int vertex; //정점 Node link; //다음 연결되어 있는.. 2023. 3. 4.

이전 1 2 3 다음

728x90

티스토리툴바