728x90 반응형 코딩테스트/백준104 [백준/java] 2606번: 바이러스 - 인접행렬을 이용한 bfs 풀이 문제 이번 포스팅은 오랜 만에 알고리즘 문제를 올려봅니다. 그동안 할줄 몰라서 안풀었던 인접행렬을 이용하는 문제인 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 백준 2606번 바이러스 문제를 풀어보도록 하겠습니다. 이 문제를 이해하고 풀기 위해서는 인접행렬을 이용해야 합니다. 인접행렬이란? 인접행렬 위키백과, 우리 모두의 백과사전. 그래프 이론에서, 인접 행렬(adjacency matrix)은 그래프에서 어느 꼭짓점들이 변으로 연결되었는지 나타내는 정.. 2021. 11. 12. [백준/java] 1644번: 소수의 연속합 - 투 포인터 + 에라스토테네스의 체 에라스토테네스의 체를 이용하여 소수를 먼저 구하고, 투 포인터로 소수의 합이 N과 일치할 때 정답의 개수를 구하는 문제이다. 예외처리를 잘해주지 않으면 틀리는 문제이다. 단순히 투포인터 문제라 두개의 점으로 시작하는 방식으로 구현했었다. 소수가 2, 3, 5, 7... 소수를 두개로 시작하면 2, 3부터이니 solution 메서드의 두번째 for문의 rt를 1부터 순회하였다. 그렇게되면 N이 2일 때, for문은 answer를 증가하지 않는다. 그리고 N이 1이면 0을 리턴해줘야하는데, int lt = 0, sum = list.get(lt);를 하게 되면 소수가 2부터 시작하므로 1 이하로 존재하는 소수가 없다. 그러므로 n = 1일때, lt = list.get(lt); 를 하게 되면 IndexOutOf.. 2021. 9. 24. [백준/java] 2470번: 두 용액 - 투 포인터 값을 입력받을 때, 처음에 Scanner를 이용했었다가 시간초과가 4번정도 떴었다. BufferedReader로 바꾼 후에도 시간초과가 뜨길래 정렬 방식에서 문제가 있나 싶었다. 입력되는 값이 너무 크다보니 범위가 커져서 Arrays.sort()의 경우 최악의 경우는 O(N^2)까지 가는 경우도 있으니 ArrayList로 입력을 받아서 Collections.sort()로 정렬하면 수행시간이 O(N log N)이 보장되기 때문에 리스트로 입력받는 방법을 선택했다. 그리고 두 포인터 인덱스의 값의 합이 0일 때는 해당 인덱스들을 출력해야하기 때문에 두 포인터를 좁혀나가는 로직에서 break를 걸어주어야 한다. package twoPointer; import java.io.BufferedReader; impo.. 2021. 9. 24. [백준/java] 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 이번 문제는 이분 탐색을 이용해서 풀어야한다. 먼저 lt와 rt를 사용해서 중간을 구해야하는데, m 배열과 비교할 때 N의 배열과 비교할 것이므로 끝점의 기준을 N-1으로 한다. int lt = 0; int rt = n - 1; 0부터 n-1까지 기준을 잡으면 된다. 이분탐색은 lt의 위치가 rt의 위치보다 커지면 탐색이 종료가 된다. mid의 위치.. 2021. 9. 23. [백준/java] 1806번: 부분합 - 투 포인터 활용 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 코딩테스트 강의를 들으며 투 포인터를 익혔다. 강의에서도 부분수열의 합에 대해서 다뤘었는데 확실히 개념을 익히고 나니까 이번 문제를 풀 수있었다. https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%9.. 2021. 9. 10. [백준/java] 10026번: 적록색약 - DFS 골드 5티어 치고 어렵지 않았던 문제이다. 탐색하고자 하는 범위가 제대로 된 범위인지, 그리고 기존에 방문했었는지를 조사하면 되는데, 여기에 추가적으로 초록색과 빨간색이 구분이 가는지에 따라 조건을 다르게 해주면 된다. 초록색과 빨간색이 구분이 간다면, 탐색하는 영역의 색이 현재와 같은색인지 비교해주면 된다. 하지만 초록색과 빨간색이 구분이 가지 않는 경우, 탐색하는 영역의 색이 파란색인지 아닌지만 비교해주면 된다. package dfs; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStrea.. 2021. 9. 10. 이전 1 2 3 4 5 ··· 18 다음 728x90 반응형
