본문 바로가기
728x90

Algorithm68

백준 2307번 도로검문 문제 문제링크 그림 1은 어떤 도시의 주요 지점과 그 지점들 간의 이동시간을 나타낸 그래프이다. 그래프의 노드는 주요 지점을 나타내고 두 지점을 연결한 도로(에지)에 표시된 수는 그 도로로 이동할 때 걸리는 분 단위의 시간을 나타낸다. 두 지점 a와 b를 연결하는 도로는 도로(a,b)로 표시한다. 예를 들어 도로(1,2)와 도로(2,3)를 통하여 지점1에서 지점3으로 갈 때 걸리는 시간은 3분이다. 도로는 모두 양방향이라고가정하므로 도로(a,b)와 도로(b,a)를 지날 때 걸리는 시간은 항상 같다고 한다. 어떤 범죄용의자가 입력 데이터에 표시된 도시로 진입하여 이 도시를 가장 빠른 시간 내에 빠져나가고자 한다. 그런데 이 사실을 알고 있는 경찰이 어떤 하나의 도로(에지)를 선택하여 이 도로에서 검문을 하.. 2023. 1. 26.
선택 정렬 과 시간 복잡도 선택 정렬 알고리즘은 가장 원시적인 방법이다. 데이터가 무작위로 여러 개 있다고 가정하자. 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다. 다음은 선택 정렬을 사용하여 데이터를 오름차순으로 정렬한 코드다. import java.util.Arrays; public class Main { public static void main(String[] args) { int []arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8}; int Index = 0; //가장 적은 원소의 인덱스 for(int i = 0; i < arr.length; i++){ for(int j = i + 1; j < arr.length;.. 2023. 1. 26.
백준 1486번 등산 1. 문제 설명 문제 링크 세준이는 등산광이다. 세준이는 높은 곳에서 도시를 내려다 보는 것을 좋아한다. 하지만, 겁이 많은 세준이는 어두워지기 전에 호텔로 내려오려고 한다. 세준이가 가려고하는 산의 지도가 입력으로 주어진다. 산의 지도를 M이라고 했을 때, M[i][j]는 (i,j)의 높이가 M[i][j]라는 것을 의미한다. 그 값이 'A'-'Z'일 때는 0-25를 뜻하는 것이고, 'a'-'z'일 때는, 26-51을 뜻한다. 세준이의 호텔은 (0,0)에 있다. 그리고, 세준이는 지금 위치에서 바로 인접한 정수 좌표 중 높이의 차이가 T보다 크지 않은 곳으로만 다닐 수 있다. 만약 세준이가 현재 위치에서 높이가 낮은 곳이나 같은 곳으로 이동한다면 시간은 1초가 걸린다. 하지만 높은 곳으로 이동한다면 두 .. 2023. 1. 24.
백준 22255번 호석사우루스 1. 문제 설명 문제 링크 호석사우루스는 융통성 없이 정해진 규칙을 활용해 움직인다. 규칙은 아래와 같다. 3K번째는 상, 하, 좌, 우 중 한 곳으로 이동한다. 3K+1번째는 상, 하 중 한 곳으로 이동한다 3K+2번째는 좌, 우 중 한 곳으로 이동한다. 이동하려는 곳에 벽이 있으면 이동할 수 없다. 첫번째로 이동하는 것은 1(3K+1)번째 이동이다 이 때 미궁의 각 칸마다 충격량이 주어질 것이며, 호석사우르스는 해당 칸에 들어가게 되면 충격량을 받게 된다. 호석사우르스가 받는 충격량의 총량을 최소한으로 하는 방법을 찾아 최소 충격량을 구하는 문제이다. 2. 코드 import sys from heapq import heappush, heappop INF = sys.maxsize input = sys.s.. 2023. 1. 24.
자바 [JAVA] - 삽입 정렬(Insertion Sort) Insertion Sort [삽입 정렬] 삽입 정렬은 현재 비교하고자 하는 target(타겟)과 그 이전의 원소들과 비교하며 자리를 교환(swap)하는 정렬 방법이다. 말로만 설명하기에는 어려울 수 있으나 그림으로 보면 이해하기 쉬우니 일단 삽입 정렬에 대한 특징만 짚고 넘어가보자. 삽입 정렬은 데이터를 '비교'하면서 찾기 때문에 '비교 정렬'이며 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않기 때문에 '제자리 정렬(in-place sort)'이기도 하다. 정확히는 데이터를 서로 교환하는 과정(swap)에서 임시 변수를 필요로 하나, 이는 충분히 무시할 만큼 적은 양이기 때문에 제자리 정렬로 보는 것이다. 이는 선택정렬과도 같은 부분이다. 정렬 방법 삽입 정렬의 경우 원리 자체는 간단하.. 2023. 1. 23.
백준 2751번 수 정렬하기2 1. 문제 설명 문제 링크 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. . 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 2. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.ArrayList; import java.util.Collections; class Main { public.. 2023. 1. 23.
728x90

티스토리툴바