백준

백준 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 1. DFS? 그래프? 노드? 간선? 이 문제를 풀기위해선 먼저 DFS알고리즘의 개념과 노드,간선의 개념들에 대한 이해가 선행되어야 한다. - 그래프 : 노드(Node)와 그것을 연결하는 간선(Edge)으로 원소간의 관계를 표현한 자료구조이다. 정점(Vertex) : 노드, 정점엔 데이터가 저장된다. 간선(Edge) : 정점과 정..

백준 10989번 자바

문제 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 1.기수정렬? 계수정렬? - 기수정렬(Radix Sort) : 낮은 자리수부터 정렬을 하고 그 배열을 이용해 다음 자리수를 정렬하는 값비교 없이 수행되는 정렬 방법이다. - 계수정렬(Counting Sort) : 입력 배열의 원소값을 계수하여 새 배열에 누적합으로 담아 정렬하며 기수 정렬과 마찬가지로 값비교없이 수행하는 정렬방법이다. 더 큰 키들을 더 효율적으로 처리할 수 있는 다른 정렬 알고리즘인 기수 정렬의..

백준 1517번 자바 ☆

문제 https://www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다. www.acmicpc.net 1. 버블소트를 가장한 머지소트 문제 문제 제목이 버블소트라고 버블소트로 풀었다 당연스럽게 시간초과로 틀렸다. 머지 소트로 풀어야 통과가 된다. https://ahlight.tistory.com/79 백준 2751번 자바 문제 https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000..

백준 2751번 자바

문제 https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 1. 병합정렬이란? - 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘 - 평균 시간 복잡도는 O(nlogn)이다. - 예시 아래와 같이 정렬되지 않은 배열 A가 있다. 6 4 3 1 5 2 배열을 최소단위로 나눠준다.(값의 색은 구분단위) 6 4 3 1 5 2 인접 단위끼리 병합을 진행하며 정렬 4 6 1 3 2 5 4 6 1 2 3 5 1 2 ..

백준 11004번 자바 ☆

문제 https://www.acmicpc.net/problem/11004 11004번: K번째 수 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 처음엔 Arrays.sort를 이용해 쉽게 풀었다. Arrays.sort 의 정렬 방식이 dual pivot quick sort를 사용하기 때문에 가능하다고 판단했고 정답을 맞추긴 했다. 하지만 이번 문제에선 퀵정렬을 사용해 해결하는것이 핵심이었다. 2. 퀵정렬 개념자체는 어렵지 않다. pivot을 설정하고 pivot기준 이하 그룹, 이상 그룹으로 나누어 재귀로 배열을 정렬하면 된다. 단순 구현이라면 크게 어렵지 않았지만 해당 문제를 충족..

백준 11399번 자바

문제 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 1. 삽입정렬을 이용해 문제를 해결했다. 삽입정렬이란 예를들어 아래 파란식 글씨 부분들이 정렬된 부분이고, 빨간색 글씨부분이 현재 인덱스일때 현재 인덱스의 값을 정렬된부분에 삽입을 하는 것이다. 1 2 3 4 5 13 15 12 17 16 12는 13보다 작은 수이기때문에 가장 앞에 삽입되고 나머지 값들은 한칸씩 뒤로 이동이 된다. 3 1 2 4 5 12 13 15 17 16 값이 한칸씩 뒤로 밀려 저장되는 것만 주의하면..