본문 바로가기
728x90

ProgramSolve/Baekjoon23

[BOJ] 2230번 - 수 고르기 (Java) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램 → 차이를 비교할 두 수가 같은 수일 수도 있고 조건을 만족하는 최솟값을 구해야 한다. 두 수의 차이를 구해야하는데 입력된 수열이 정렬되어 있지 않으면 모든 원소끼리 비교해야 한다. 예를 들어 5개의 원소가 있으면 하나의 원소와 나머지 4개의 원소를 모두 비교해보아야 한다. 총 반복되는 횟수는 4 X 3 X 2 X 1 = 24 이다. 하지만 이 문제에서 수열의 길이는 최대 100,000까지 가능하기에 시간초과가 뜬다. 그렇다면 시간을 줄이기 위해 원소를 비교하는 반복 횟수를 줄여야한다. 먼저, 수열을 정렬한다. 그러면 아래의 그림과 같이 두 수의 차이가 어떻게 변화할지 .. 2024. 3. 22.
[BOJ] 2529번 - 부등호 (Java) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족하는 수열을 구해야한다. → 이 수열을 구하기 위해 백트래킹 방식을 사용한다. 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다. → 백트래킹을 할 때 사용할 배열은 위와 같고 중복되지 않는 값들로 이뤄지도록 visited 배열을 사용한다. 이제 여기서 모든 부등호 관계를 만족하는 수열 중 가장 큰 값과 가장 작은 값을 구해야한다. 이때 주의할 점은 첫 자리가 0인 경우도 정수에 포함해야한다. 즉, 0123과 같이 출력해야한다. 나는 이를 쉽게 다루기 위해 문자열로 답을 구하기로 했다. 그러나 최솟값.. 2024. 3. 11.
[BOJ] 13023번 - ABCDE (Java) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다. - A는 B와 친구다. - B는 C와 친구다. - C는 D와 친구다. - D는 E와 친구다. 우선 여기서 알 수 있는 것은 N명 중 5명이 이와 같은 관계를 가지고 있으면 된다. 이러한 친구 관계를 구하기 위해서는 깊이 우선 탐색을 하여 구할 수 있다. 그래프의 깊이가 5이상일 경우 위와 같은 관계가 존재한다는 것을 알 수 있다. 단, 이는 판별만 하면 되기 때문에 관계를 발견하면 모든 탐색을 멈출 수 있도록 했다. 🍀 풀이 🍀 package Baekjoon; import java.io.*; import java.util.*; public class DFS13023 { sta.. 2024. 3. 1.
[BOJ] 2477번 - 참외밭 (Java) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 참외밭은 ㄱ자 모양이거나 ㄱ자를 90도, 180도, 270도 회전한 모양(┏, ┗, ┛ 모양)의 육각형 밭의 경계(육각형의 변)는 모두 동서 방향이거나 남북 방향 → 밭의 모양은 항상 그림과 같은 육각형이다.(회전할 수 있다.) 그러므로 밭의 넓이는 [전체적인 사각형의 넓이 - 빠져야할 작은 사각형의 넓이] 이다. 우리는 가장 긴 가로의 길이와 세로의 길이, 빼야할 가로의 길이와 세로의 길이를 구해야한다. 1. 가장 긴 가로와 세로 구하기 입력받을 때 동쪽은 1, 서쪽은 2, 남쪽은 3, 북쪽은 4 이므로 1, 2일 경우 가로 확인, 3,4일 경우 세로 확인 2. 빼야할 가로와 세로 구하기 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 입력을 받는다... 2024. 2. 19.
[BOJ] 1068번 - 트리 (Java) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 트리의 구조는 부모와 자식의 관계를 가진다. 이 문제에서 입력으로 각 노드의 부모를 입력받기 때문에 부모 노드에 자식 노드를 추가해주었다. for(int i = 0; i < n; i++) { int p = Integer.parseInt(st.nextToken()); if(p == -1) { //루트노드 저장하기 root = i; } else { tree[p].add(i); //부모노드에게 자식노드 추가 } } 이와 같이 저장한 후 전체적으로 DFS를 이용하여 리프노드를 탐색했다. 그러나 여기서 내가 생각하지 못했던 경우가 존재해서 이를 정리해보려고 한다. 1. 루트 노드가 리프노드가 되는 경우 루트노드가 하나의 자식노드를 가지는데 그 자식 노드를 삭제 루트 노드는 리프 노.. 2024. 2. 1.
[BOJ] 5397번 - 키로거 (Java) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ Cursor를 기준으로 왼쪽과 오른쪽을 구분하여 저장한다. 커서가 이동할 때마다 왼쪽과 오른쪽에 저장될 문자들이 변하기 때문에 이를 얼마나 효율적으로 관리할 수 있는지가 중요하다. 그러므로 커서를 기준으로 바로 왼쪽 문자와 오른쪽 문자가 가장 위에 있어 옮기기 쉽다. 이 문제에서 나는 스택을 사용하여 저장했다. 아래의 그림은 커서의 이동방향에 따라 동작 과정을 나타낸 것이다. 마지막으로 결과를 출력할 때 주의할 점! 왼쪽 스택에서 값을 꺼내면 뒤쪽의 비밀번호가 먼저 나오므로 꺼낸 후 뒤집어준다. 오른쪽 스택은 앞쪽의 비밀번호가 먼저 나오므로 그대로 해주면 된다. 🍀 풀이 🍀 package Baekjoon; import java.io.*; import java.util.St.. 2024. 1. 28.
[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.
[BOJ] 2437번 - 저울 (Python) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 우선 예시 중에서 추 [1, 1, 2]만 가지고 있다고 생각해보자. 그러면 측정할 수 있는 무게는 위의 그림과 같다. 다른 예시로 [1, 2, 3]으로 생각해보면, 1 = 1 2 = 2 3 = 3 4 = 1+3 5 = 2+3 6 = 1+2+3 위와 같이 측정할 수 있다. 즉, 가지고 있는 추들의 무게를 합한 값 이하의 값들은 측정할 수 있다는 것을 알 수 있다. 단, 추의 무게들이 정렬이 되어있어야 하며 추와 추 사이의 무게 차이가 크게 나면 안된다. 여기서 추 사이의 무게 차이가 얼마만큼 차이가 나면 안되는지를 생각해봐야한다. 문제에서 주어진 예시로 현재 [1, 1, 2, 3]의 추를 가지고 있어 7까지 측정할 수 있다고 하자. 다음 추가 현재 측정할 수 없는 8보다 작.. 2023. 10. 27.
[BOJ] 15657번 - N과M(8) (Python) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 백트래킹 연습하기 편한 문제라고 생각한다. 오늘 풀면서 틀렸던 이유에 대해 간단하게 남겨놓으려고 한다. 내가 잘못 생각했던 부분은 타입을 생각하지 않고 정렬한 것이다. 처음에는 결과를 쉽게 저장하기 위해 문자형 그대로 사용하여 주어진 예제는 전부 통과해 제출했지만 틀렸다. 다른 동작의 오류가 있나 고민해보았지만 없었고 다른 사람의 풀이를 참고해봐도 동작은 완벽했다. 단 하나 다른 점이 입력받은 데이터 타입이었는데 생각해보니 [입력으로 주어지는 수는 10,000보다 작거나 같은 자연수]이므로 이는 정수로 정렬해야 올바르게 정렬된다는 것을 깨달았다. 🍀 풀이 🍀 import sys n, m = map(int, sys.stdin.readline().split()) nums = .. 2023. 10. 5.
728x90

티스토리툴바