본문 바로가기

Problem Solving1216

[백준] 1766 문제집 - Graph Theory / Java • 문제 링크 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net • 풀이 과정 [백준] 2252 줄 세우기 - Graph Theory / Java • 문제 링크 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A graycode.tistory.com 위의 문제와 같은 구조로 어떤 문제를 풀기 위하여 선행되어야.. 2022. 8. 13.
[백준] 2252 줄 세우기 - Graph Theory / Java • 문제 링크 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net • 풀이 과정 어떤 학생보다 키가 크므로 먼저 줄을 서야하는 학생의 수, 즉 외부 노드에서 들어오는 간선의 개수(진입 차수) 를 inDegree 배열에 저장하여 위상 정렬로 풀이한다. 예시로 학생 2 보다 큰 키의 학생 3, 4가 주어질 경우, (4, 2), (3, 2) 의 입력이 주어지고 inDegree[2]++ 가 총 두번 수행되어 inDegree[2] = 2 로 초기화된다. 이 후 학생 i 에 대하여.. 2022. 8. 12.
[백준] 17089 세 친구 - Brute Force / Java • 문제 링크 17089번: 세 친구 첫째 줄에 사람의 수 N(3 ≤ N ≤ 4,000), 친구 관계의 수 M(0 ≤ M ≤ 4,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계를 의미하는 두 정수 A, B가 주어진다. 친구 관계는 A와 B, 그리고 B와 A가 친 www.acmicpc.net • 풀이 과정 각각의 인원을 노드로 정의하고 각 노드간 무향 그래프 정보를 boolean 배열 map 에 저장하고, 각 노드의 연결 노드의 수, 즉 친구의 수를 저장할 int 배열 cnt 에 입력받은 노드를 인덱스로써 해당 위치에 +1 을 수행한다. 인원 중 세 사람을 선택하므로 3중 for 문으로 조합을 구할 수 있으며, 선택된 세 사람이 모두 친구일 경우, 해당 인원의 친구 수를 모두 더하고 선택된 나머.. 2022. 8. 11.
[백준] 17088 등차수열 변환 - Brute Force / Java • 문제 링크 17088번: 등차수열 변환 크기가 N인 수열 A = [A1, A2, ..., AN]이 있을 때, 모든 1 ≤ i < N에 대해서, Ai+1-Ai가 모두 일치하면 등차수열이라고 한다. 예를 들어, [3], [6, 6, 6], [2, 8, 14, 20], [6, 4, 2]는 등차수열이고, [4, 5, 4], [6, 3, 1] www.acmicpc.net • 풀이 과정 등차수열의 공차는 모든 항에 대해서 일치하므로, 수열의 첫째, 둘째 항의 공차의 값에 따라 다른 모든 항의 공차를 일치하게 연산할 수 있는지 확인한다. 첫째, 둘째 항 각각에 -1, 0, 1 를 더하는 경우, 즉 3 * 3 = 9가지의 경우를 가지므로 2중 for문 내부에 clone() 함수를 통해 배열을 초기화하여 각각의 경우.. 2022. 8. 10.
[백준] 15683 감시 - Brute Force / Java • 문제 링크 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net • 풀이 과정 크기가 n * m 인 2차원 배열 map 에 cctv 및 벽의 정보를 입력받고, cctv 의 좌표(y, x) 와 해당 cctv 의 종류(type) 및 감시 가능 방향(dir)을 제네릭이 Node 클래스인 List 객체 list 에 저장한다. 이때 n * m 에 cctv 의 개수와 벽의 개수를 뺀 값이 사각지대의 개수의 초기값이 되며, 해당 값을 cnt, list 에서 cctv 정보를 가져올 인덱스 값을 idx, 탐색할 2차원.. 2022. 8. 9.
[백준] 16637 괄호 추가하기 - Brute Force / Java • 문제 링크 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net • 풀이 과정 재귀 호출 함수를 통해 다음 연산에 괄호를 사용해 연산할 지, 그대로 연산할 지 두가지 경우를 모두 계산한다. 크기가 수식의 길이 n 인 char 배열 input 을 생성해 입력받은 수식을 저장한 후, 인덱스 변수를 idx 로 정의하고 정수의 경우 input[idx] - '0' 로 호출, 연산자는 input[idx] 로 호출한다. 호출한 정수와 연산자에 맞게 연산값을 반환할 cal 함수를 생성하고, 연산의 결과가 누적될.. 2022. 8. 8.

티스토리툴바