본문 바로가기

전체 글69

[알고리즘] 다익스트라 알고리즘 다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘이다. 간단하게 DFS 혹은 BFS로 구현한 경우 출발 지점에서 도착 지점까지 하나의 경로에 대한 최단 경로를 확인할 수 있던 것에서 확장하여 출발 지점에서 이동할 수 있는 모든 지점에 대한 최단 경로를 알아낼 수 있다. 다익스트라 알고리즘을 적용할 수 있는 자료구조는 그래프이고 동작 단계는 다음과 같다. 1. 그래프 상의 모든 정점과 간선, 가중치에 대한 정보를 저장한다. 2. 최단 거리 테이블(dp)을 초기화 한다. 이때 dp에는 허용할 수 있는 가장 큰 수 + 1가 저장되어 있다. 3. 출발 노드에 대한 정보를 A에 저장한다(보통은 A = 우선순위 큐). 4. A에서 누적 가중치가 가장 작은 경로에서 (초기에는 출발노.. 2023. 6. 6.
[백준] 2470번 - 두 용액 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 문제 전체 N개의 용액 중 두 용액의 특성값의 합이 0에 가장 가까운 조합을 오름차순으로 출력하시오. 조건 2 2023. 6. 5.
[JAVA] Collections.sort vs Arrays.sort 차이 자바를 다루다보면 데이터를 오름차순, 또는 내림차순으로 가공해야 하는 경우가 생긴다. 이때에는 직접 정렬시키는 방법도 있겠으나, 보통은 자바 클래스 라이브러리에서 제공하는 메서드를 사용한다. 대표적으로 배열을 정렬해주는 Arrays.sort()와 객체를 정렬해주는 Collections.sort(). 표면적으로 보면 정렬 대상이 배열이면 Arrays을 사용하고, 정렬 대상이 그 외 리스트와 같은 객체이면 Collections을 사용하면 될 것 같지만, 백준 문제풀이와 같이 출제자가 의도적으로 산출 시간에 제한을 걸어둔 경우 두 경우의 시간 복잡도나 공간 복잡도를 고려하여 어떤 방법을 사용할지 선택해야 할 때가 있다. 따라서 이번 기회에 두 정렬 방법에 대한 차이점을 정리해둘까 한다. Arrays 와 Col.. 2023. 6. 5.
[JAVA] Array vs ArrayList vs LinkedList 데이터를 저장할 수 있는 자료구조에는 배열(Array), 리스트(List), 맵(Map), Set 등이 있다. 여기서 내가 자주 사용하는 배열과 리스트에 대한 차이점에 대해 간략하게 정리해두겠다. List Array ArrayList LinkedList 선형 vs 비선형 선형 선형 선형 순차 vs 연결 순차 순차 연결 크기 고정 가변 가변 접근 O(1) O(1) O(N) 삭제, 추가 중간 O(N) / 마지막 원소 O(1) 중간 O(N) / 마지막 원소 O(1) 접근하는 시간 O(N) / 삭제 및 추가 O(1) 빈 엘리먼트 허용 O O X 배열 배열의 특징은 다음과 같다. - 메모리상에 선형 순차적으로 저장되고 0 부터 순서에 해당하는 번호가 붙는다. - 한 번 생성된 배열의 길이는 변경할 수 없다. - .. 2023. 6. 5.
[백준] 11660번 - 구간 합 구하기 5 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 N x N 크기의 표가 있을 때, M번 주어지는 (x1, y1) 부터 (x2, y2)까지 합을 구하시오. 조건 1 2023. 5. 31.
[백준] 1018번 - 체스판 다시 칠하기 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제 1x1 정사각형 구획으로 나뉘어져 있는 MxN 크기의 보드에 한 구획마다 흰색 또는 검은색이 무작위로 칠해져 있을 때, 인접하는 구획끼리 서로 다른 색을 갖도록 하여 8x8 크기의 체스판을 만들기 위해 다시 칠해야 하는 정사각형 구획의 최소 개수를 구하여라. 조건 만들고자 하는 체스판의 크기는 8 x 8 8 2023. 5. 31.
[백준] 2559번 - 수열 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 문제 N일 동안 매일 아침 9시에 측정한 온도 데이터가 수열로 주어졌을 때, 연속 K일 동안의 온도 합 중에 가장 큰 값을 구하시오. 조건 2 2023. 5. 30.
[백준] 11659번 - 구간 합 구하기 4 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지의 합을 구해야 한다. 조건 1 2023. 5. 30.
[백준] 2447번 - 별 찍기 - 10 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 별 찍기 10이다. 재귀함수와 분할정복 알고리즘을 사용하여 해결할 수 있다. 분할정복에 익숙하지 않다면 아래 문제를 먼저 해결해보자. [백준] 2630번 - 색종이 만들기 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마 stonage.tistory.com 문제에서.. 2023. 5. 29.

티스토리툴바