코딩 테스트
백준 1766 자바 - 문제집 문제
www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 그래프이론, 위상정렬, 우선순위 큐 개념이 들어있는 문제로 문제 풀이방식은 다음과 같다. 1. 입력받은 문제들의 index를 graph로 만들고 2. 각 문제들의 선행되어야하는 문제의 수 즉 진입차수(inDegree)를 배열로 셋팅한다. 3. 우선순위 큐를 index값이 작은 것이 우선되도록 만들고 4. 진입차수가 0인 문제들을 해당 큐에 넣는다. 5. 큐를 돌면서 해당 문제의 i..
백준 14003 자바 - 가장 긴 증가하는 부분 수열 5 문제
앞서 풀었던 가장 긴 증가하는 부분 수열 2번에 수열 index를 같이 셋팅한 뒤 계산한다고 보면 된다. 가장 긴 증가하는 부분 수열 2번에 수열에서는 i 0 1 2 3 4 5 arr 1 5 6 2 3 4 listForSize 0 1 2 3 이렇게 까지만 구한뒤 listForSize의 값을 이용해서 길이를 구했다. 여기에 자신 증가하는 수열의 몇번째를 차지하고 있는지에 대한 리스트를 추가한다. 위에 예에 추가하면 아래와 같다. i 0 1 2 3 4 5 arr 1 5 6 2 3 4 listForSize 0 1 2 3 indexs 0 1 2 1 2 3 이부분에서 입력받은 수열 arr(A)를 뒤에서 부터 순회하면서 값을 체크한다. int index = listForSize.size() - 1; Stack st..
백준 12015 자바 - 가장 긴 증가하는 부분 수열 2 문제
www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 가장 긴 부분 수열의 길이를 구하는 문제로 전체 리스트를 한번만 돌아서 임으로 만든 listFroSize 배열을 변경해나면서 사이즈를 구함. 1. listFroSize에 0을 추가 2. 입력받는 arr를 순회 - 1) arr의 인자 값이 listFroSize의 마지막 값보다 큰 경우 추가 - 2) arr의 인자 값이 listFroSize의 마지막 값보다 작은 경우 이진 탐색 - 이진탐색을 통해서 right 값을..
백준 13460 자바 - 구슬 탈출 2 문제
구현은 bfs를 통해서 모든 방향으로 기울여가면서 답을 구하면된다. 첫 위치서 부터 bfs를 통해 상하좌우로 기울여보면서 각각의 위치와 기울인 횟수를 체크 기울여서 구슬을 이동시킬때 서로에 대한 고려를 하지않고 이동시킨 뒤 서로의 위치가 동일한 경우만 더 많이 이동한쪽을 덜이동시키도록 함 이렇게 bfs를 진행하다가 빨간 구슬만 빠져나간 경우 해당 count를 print함. import java.io.*; import java.util.*; class Ball { int x; int y; int count; public Ball(int x,int y, int count) { this.x = x; this.y = y; this.count = count; } } // 구슬 탈출 2 문제 - 13460번 pub..
코딩 테스트 문제 풀이 카테고리
백준, 프로그래머스 등의 사이트에서 코딩 테스트 문제를 풀고 정리하는 카테고리입니다. 코드만 보고싶으시다면 아래 링크에서 보실수 있습니다. github.com/whdals7337/coding-test-study