백준

백준 2343번 자바 ☆

문제 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 1. 접근방식 이전에 풀었던 문제와 마찬가지로 이분탐색으로 접근해야 한다. 다만 문제에 대한 이해도가 떨어져 이분탐색할 범위를 이상하게 잡아 문제 해결에 어려움을 겪었다. 먼저, 블루레이 최소크기가 9이고 최대크기가 45임을 이해해야한다. 최소크기가 9인 이유는 나열된 강의들 중 가장 긴 강의가 9길이의 영상이기 때문이다. 즉, 각 개별의 영상크기가 가장 마지막 영상의 길이인 9보다 작기 때문이다...

백준 1920번 자바

문제 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 1. 이진탐색? 이분탐색? 이진, 이분 탐색 둘다 의미는 비슷하기에 크게 구분하지 않아도 된다. 이진 탐색 : 찾으려는 값(a)가 배열(arr)에 존재하는지 찾을 때 arr의 중간값과 비교를 하면서 탐색하는 방법이다. 예를 들어 찾으려는 값(a)이 2라고 할때, 아래 배열(arr)의 중간값(mid)인 4와 비교를 한다. 1 2 3 4 5 6 7..

백준 1167번 자바☆

문제 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 1. DFS로 가능한가? 시간복잡도를 계산하면 V의 범위가 100,000까지기 때문에 최악복잡도는 O(N2) = 약 100억으로 예상된다. 그래서 일반적인 DFS방식으로 풀면 시간초과가 발생한다. 2. 어떻게 접근할 것인가? 한 줄로 요약하면 임의 노드에서 가장 긴경로로 연결돼 있는 노드는 가장 긴 경로(트리의 지름)의 두 노드 중 하나이다. 예제를 그림으로 보도록하자. 그림..

백준 1260번 자바

문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 1. BFS? 이 문제는 DFS, BFS에 대한 이해가 있어야 풀 수 있다. DFS에 대한 간략한 설명은 아래에 링크를 첨부했다. https://ahlight.tistory.com/82 백준 11724번 자바 문제 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 ..

백준 13023번 자바

문제 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 1. 그래프와 DFS 이 문제역시 그래프와 DFS에대한 개념을 알고있어야 풀수 있다. 해당 개념에 대한 간략한 설명을 아래에 링크를 추가했다. https://ahlight.tistory.com/82 2. 접근 방식 실제 문제를 푸는 시간보다 문제를 이해하는데 더 오랜 시간이 걸렸던 문제다. 예제의 친구관계를 그래프로 그려보다 문제에서 원하는 조건이 무엇인지 파악했다. - 문제에서 친구관계가 뜻하는 바는 무방향 그래프이다. - 간선으로 이어진 노드는 모두 인접노드라고 볼 수 있다. - 인접한 노드로..

백준 2023번 자바

문제 https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 1. 접근 방법 - 왼쪽부터 한자리씩 늘려가며 소수인지 아닌지 확인을 한다. - 해당 자리가 소수면 재귀를 통해 다음 자리수로 넘어간다. - 자리수가 N과 동일해지면 값을 출력 후 탐색을 종료한다. 2. 구현 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; publ..