Algorithm/BOJ
-
https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 11724, 연결 요소의 개수 이번 문제는 그래프 이론 과 DFS 를 사용해서 풀어보겠다. # Process main : 정점의 개수와 간선의 개수가 주어진다. 정점의 개수만큼 ArrayList 를 만들어주고 양방향 간선을 표시해주면 된다. N = scan.nextInt(); M = scan.nextInt(); adj = new Arr..
(JAVA) [BOJ]백준 11724번, 연결 요소의 개수https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 11724, 연결 요소의 개수 이번 문제는 그래프 이론 과 DFS 를 사용해서 풀어보겠다. # Process main : 정점의 개수와 간선의 개수가 주어진다. 정점의 개수만큼 ArrayList 를 만들어주고 양방향 간선을 표시해주면 된다. N = scan.nextInt(); M = scan.nextInt(); adj = new Arr..
2023.05.03 -
https://www.acmicpc.net/problem/2583 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 2583, 영역 구하기 [ 난이도 : 실버 1 ] 이번 문제는 그래프 이론과 DFS 를 사용해서 풀이해보겠다. 눈금이 그어진 영역을 제외한 모든 영역의 사이즈 (영역 하나의 넓이가 1) 를 구하면 쉽게 풀이할 수 있는 문제이다. # Process main : 입력받은 값의 영역을 모두 true 로 표기해서 눈금이 그어진 영역을 표시해준다. M = scan.nextInt(); N = ..
(JAVA) [BOJ]백준 2583번, 영역 구하기https://www.acmicpc.net/problem/2583 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 2583, 영역 구하기 [ 난이도 : 실버 1 ] 이번 문제는 그래프 이론과 DFS 를 사용해서 풀이해보겠다. 눈금이 그어진 영역을 제외한 모든 영역의 사이즈 (영역 하나의 넓이가 1) 를 구하면 쉽게 풀이할 수 있는 문제이다. # Process main : 입력받은 값의 영역을 모두 true 로 표기해서 눈금이 그어진 영역을 표시해준다. M = scan.nextInt(); N = ..
2023.05.02 -
https://www.acmicpc.net/problem/1012 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 1012, 유기농배추 [ 난이도 : 실버 2 ] 이번 문제는 그래프 탐색 & DFS 를 사용하여 풀어보겠다. # Process main : 이번 문제에서 주의해야 할 것은 좌표를 (0,1) (1,3) 과 같이 주는데 가로&세로의 범위를 잘 생각해야 한다. 지역을 나타내는 area 와 방문 여부를 확인하는 visit 배열을 먼저 생성해주고 배추의 위치는 area 에 값을 1로 설정해준..
(JAVA) [BOJ]백준 1012번, 유기농배추https://www.acmicpc.net/problem/1012 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 1012, 유기농배추 [ 난이도 : 실버 2 ] 이번 문제는 그래프 탐색 & DFS 를 사용하여 풀어보겠다. # Process main : 이번 문제에서 주의해야 할 것은 좌표를 (0,1) (1,3) 과 같이 주는데 가로&세로의 범위를 잘 생각해야 한다. 지역을 나타내는 area 와 방문 여부를 확인하는 visit 배열을 먼저 생성해주고 배추의 위치는 area 에 값을 1로 설정해준..
2023.04.28 -
https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 1439, 뒤집기 [ 난이도 : 실버 1 ] 이번 문제는 브루트 포스 알고리즘 분야지만 그래프 탐색과 dfs 를 사용해서 풀어보겠다. # Process main : 안전영역을 구하는 문제이다. 2차원 배열의 형태가 주어졌을 때, 특정 수 이상의 범위로 안전범위를 지정하여 그 최대 갯수를 구하는 문제이다. 제일 먼저 입력을 받으면서 모든 원소의 값을 list 로 저장해주어야 한다. (중복을 허용하지 않기 ..
(JAVA) [BOJ]백준 2468번, 안전영역https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 1439, 뒤집기 [ 난이도 : 실버 1 ] 이번 문제는 브루트 포스 알고리즘 분야지만 그래프 탐색과 dfs 를 사용해서 풀어보겠다. # Process main : 안전영역을 구하는 문제이다. 2차원 배열의 형태가 주어졌을 때, 특정 수 이상의 범위로 안전범위를 지정하여 그 최대 갯수를 구하는 문제이다. 제일 먼저 입력을 받으면서 모든 원소의 값을 list 로 저장해주어야 한다. (중복을 허용하지 않기 ..
2023.04.24 -
https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 1806, 부분합 [ 난이도: 골드4 ] 이번 문제는 투포인터를 사용한 문제이다. # Process Main : 10,00 이하의 자연수로 이루어진 길이 N짜리 수열과, N개의 숫자 그리고 합인 S가 주어진다. 가장 짧은 것의 길이를 구하는 문제이기 때문에 출력할 값인 ans 는 배열의 크기 +1 로 초기화 해주겠다. 1부터 N까지 왼쪽 포인터를 순회하면서, 오른쪽 포인터로는 N을 ..
(JAVA) [BOJ]백준 1806번, 부분합https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 1806, 부분합 [ 난이도: 골드4 ] 이번 문제는 투포인터를 사용한 문제이다. # Process Main : 10,00 이하의 자연수로 이루어진 길이 N짜리 수열과, N개의 숫자 그리고 합인 S가 주어진다. 가장 짧은 것의 길이를 구하는 문제이기 때문에 출력할 값인 ans 는 배열의 크기 +1 로 초기화 해주겠다. 1부터 N까지 왼쪽 포인터를 순회하면서, 오른쪽 포인터로는 N을 ..
2023.04.24 -
https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 1439, 뒤집기 이번 문제는 StringTokenizer 을 사용하면 너무나도 쉽게 풀 수 있다. # Process main : 예제 입력 4번을 예시로 들어보자. 11001100110011000001 이 입력을 1과 0 으로 쪼개보면 11 00 11 00 11 00 11 00000 1 이렇게 표기할 수 있다. 1 은 {11, 11, 11, 11, 1} , 0은 {00, 00, 00. 00000..
(JAVA) [BOJ]백준 1439번, 뒤집기https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 1439, 뒤집기 이번 문제는 StringTokenizer 을 사용하면 너무나도 쉽게 풀 수 있다. # Process main : 예제 입력 4번을 예시로 들어보자. 11001100110011000001 이 입력을 1과 0 으로 쪼개보면 11 00 11 00 11 00 11 00000 1 이렇게 표기할 수 있다. 1 은 {11, 11, 11, 11, 1} , 0은 {00, 00, 00. 00000..
2023.04.22 -
https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 1715, 카드 정렬하기 이번 문제는 우선순위 큐를 사용해서 풀어보겠다. N의 범위가 1 - 100,000 이고, 카드의 최대 값은 1,000이지만 카드를 합쳐가는 과정에서 모든 카드의 수를 계산한다면 int 의 범위를 넘을 수 있기 때문에 Long 을 사용해주겠다. # Process main : 입력받은 값들을 큐에 넣어주고 가장 작은 2장의 카드를 뽑아 더한 후에 다시 큐에 넣어..
(JAVA) [BOJ]백준 1715번, 카드 정렬하기https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 1715, 카드 정렬하기 이번 문제는 우선순위 큐를 사용해서 풀어보겠다. N의 범위가 1 - 100,000 이고, 카드의 최대 값은 1,000이지만 카드를 합쳐가는 과정에서 모든 카드의 수를 계산한다면 int 의 범위를 넘을 수 있기 때문에 Long 을 사용해주겠다. # Process main : 입력받은 값들을 큐에 넣어주고 가장 작은 2장의 카드를 뽑아 더한 후에 다시 큐에 넣어..
2023.04.20 -
https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 12904, A와 B 이번 문제는 역으로 해결해 나가면 쉽게 풀 수 있다. # Process main : 조건이 2개가 있다. 1. 문자열의 뒤에 A를 추가한다. 2. 문자열을 뒤집고 뒤에 B를 추가한다. 주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지를 판단하는 문제이다. 이 조건을 반대로 생각해보자. 주어진 B의 텍스트에1. 문자열의 뒤에 A가 있..
(JAVA) [BOJ]백준 12904번, A와 Bhttps://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 12904, A와 B 이번 문제는 역으로 해결해 나가면 쉽게 풀 수 있다. # Process main : 조건이 2개가 있다. 1. 문자열의 뒤에 A를 추가한다. 2. 문자열을 뒤집고 뒤에 B를 추가한다. 주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지를 판단하는 문제이다. 이 조건을 반대로 생각해보자. 주어진 B의 텍스트에1. 문자열의 뒤에 A가 있..
2023.04.19