본문 바로가기

728x90

Algorithm21

[BOJ] 2230번 - 수 고르기 (Java) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램 → 차이를 비교할 두 수가 같은 수일 수도 있고 조건을 만족하는 최솟값을 구해야 한다. 두 수의 차이를 구해야하는데 입력된 수열이 정렬되어 있지 않으면 모든 원소끼리 비교해야 한다. 예를 들어 5개의 원소가 있으면 하나의 원소와 나머지 4개의 원소를 모두 비교해보아야 한다. 총 반복되는 횟수는 4 X 3 X 2 X 1 = 24 이다. 하지만 이 문제에서 수열의 길이는 최대 100,000까지 가능하기에 시간초과가 뜬다. 그렇다면 시간을 줄이기 위해 원소를 비교하는 반복 횟수를 줄여야한다. 먼저, 수열을 정렬한다. 그러면 아래의 그림과 같이 두 수의 차이가 어떻게 변화할지 .. 2024. 3. 22.

[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] 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.

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

[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.

[BOJ] 1911번 - 흙길 보수하기 (Python) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 이 문제는 [물웅덩이들을 모두 덮으려고 한다.] 라는 조건이 있으므로 물웅덩이가 보이면 일단 덮으면 된다. 그러나 널빤지의 길이는 정해져 있으므로 덮다보면 입력받은 물웅덩이의 위치가 이미 덮여져 있을 수 있다. 어차피 모든 웅덩이는 덮어야하니 웅덩이의 [끝 위치 - 시작 위치]를 통해 웅덩이의 길이를 구하여 필요한 널빤지의 개수를 구했다. 단, 위에서 설명했듯이 이미 덮여져 있는 위치가 존재할 수 있으므로 이에 대한 처리로 current라는 변수를 두어 시작 위치를 덮여져 있지 않은 위치로 변경할 수 있도록 했다. 🍀 풀이 🍀 import sys n, l = map(int, sys.stdin.readline().split()) water = [list(map(int, sy.. 2023. 9. 7.

[BOJ] 13549번 - 숨바꼭질3 (Python) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 어제 공부한 다익스트라 알고리즘을 연습해보았다. 다익스트라 알고리즘과 BFS 2가지 방식으로 풀어보았다. (코드는 아래에) 1. 다익스트라 알고리즘을 이용한 풀이 1. 수빈이의 위치를 시작 정점으로 둔다. 2. 현재 위치 i에 +1, -1 *2 한 위치에 대해 저장되어 있는 시간 times[k]와 도달한 시간(times[i] + 1 또는 times[i])을 비교하여 도달한 시간이 더 작으면 times[k]를 갱신한다. 3. heap이 빌 때까지 2번 과정을 반복한다. 이때, 주의할 점은 가중치가 없지만 가중치로 생각한 값은 도달한 시간으로 times의 값이다. 만약 이를 times를 도착 정점의 개수만큼만 만들면 올바른 값을 도출하지 못할 것이다. 위의 문제에서 주어진 예.. 2023. 9. 5.

[BOJ] 1753번 - 최단경로(Python) + Dijkstra Algorithm 🗒️ 다익스트라 알고리즘 (Dijkstra Algorithm) 모서리 또는 정점에 가중치가 부여된 그래프에서 두 정점 사이의 최단 경로를 찾는 알고리즘 가중치가 없는 그래프에서의 최단경로는 BFS를 사용! 어떤 시작점 s가 주어졌을 때, 그 정점에서 시작하여 다른 모든 정점으로 가는 최단 경로를 찾는다. 단, 음수인 가중치가 없는 경우에만 쓸 수 있다. 실제 최단 경로는 우리집에서 옆집으로 이동하는 것이지만, 우리집에서 은행을 거쳐 가는 것이 비용상 이득이 되는 경우가 발생한다. 즉, 값이 음수인 모서리가 있으면 경로를 만들어가는 도중에 아주 작은 음수 값을 가지는 모서리가 있어서 이미 트리에 들어있는 최단 경로와 전혀 다른 경로를 만들어야 할 수 있다. 동작 과정(간선 완화 과정) 1. 모든 꼭짓점을 .. 2023. 9. 4.

이전 1 2 다음

728x90

티스토리툴바