전체글397

• [백준/BOJ] 4485번: 녹색 옷 입은 애가 젤다지? 문제 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 해설 bfs로도 풀 수 있을 것 같았지만, 다익스트라를 사용해서 문제를 풀었다. 각 칸의 소지금을 우선순위 큐에 오름차순으로 기준을 잡아준다. 기본적인 다익스트라 알고리즘 문제이다. 소스 코드 import java.lang.StringBuilder import java.util.* private lateinit var map: Array private val dx = int.. PS(Problem Solving)/BOJ 2022. 8. 7.

• [백준/BOJ] 1261번: 알고스팟 문제 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 해설 상하좌우로 움직이며 목표지까지 최소 몇개의 벽을 부수어야 하는지 구하는 문제이다. bfs를 이용해서 문제를 풀었는데, 보통 bfs라면 Queue를 이용하지만 이 문제에서는 우선순위 큐(Priority Queue)를 사용하였다. 우선순위 큐를 사용한 이유는 최단거리로 가는 문제가 아닌, 최소의 벽을 부수는 문제이기 때문이다. 우선순위의 기준을 벽을 부순 개수로 오름차.. PS(Problem Solving)/BOJ 2022. 8. 6.

• 

  [Android] 안드로이드 컴포넌트(구성 요소) 안드로이드 앱 개발의 핵심은 컴포넌트이다. 종종 "액티비티 컴포넌트", "서비스 컴포넌트" 등 컴포넌트라는 용어가 자주 등장한다. 그렇다면 컴포넌트란 무엇일까? 컴포넌트란? 컴포넌트는 안드로이드뿐만 아니라 여러 애플리캐이션을 개발할 때 사용되는 개념이다. 쉽게 말하면, 애플리케이션의 구성 요소라고 할 수 있다. 이처럼 하나의 애플리케이션은 여러 개의 컴포넌트로 구성된다. 안드로이드에서는 클래스로 컴포넌트를 개발한다. 즉, 하나의 클래스 = 하나의 컴포넌트가 된다, 그렇다고 모든 클래스가 컴포넌트인 것 또한 아니다. 앱은 컴포넌트 클래스와 일반 클래스로 구분되는데, 이는 생명주기를 누가 관리하느냐에 따라 구분된다. 클래스의 객체 생성부터 소멸까지의 생명주기 관리를 개발자 코드에서 한다 -> 일반 클래스 (.. Android 2022. 8. 5.

• [백준/BOJ] 1504번: 특정한 최단 경로 문제 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 해설 다익스트라 알고리즘을 응용하는 문제이다. 문제에는 다음과 같은 조건이 있다. 임의로 주어진 두 정점은 반드시 통과해야 한다. 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 주어진 두 정점을 거쳐야 하는 최단 경로를 구해야 한다. 간단히 생각해보면, 다음과 같다. 1 -> v1 -> v2 -> n 1 -> v2 -> .. PS(Problem Solving)/BOJ 2022. 8. 5.

• [백준/BOJ] 2887번: 행성 터널 문제 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 해설 모든 행성을 연결했을 때, 필요한 최소 비용을 구하는 문제이므로 크루스칼 알고리즘을 사용하였다. 처음 도전했을 때는 행성 간의 거리를 이중 반복문을 이용해 모두 계산하여 풀었다. 하지만 이렇게 할 시 이중 반복문에서 O(n2)이고, n의 범위가 10만이기 때문에 메모리 초과가 발생하였다. 이를 해결하기 위해 모든 행성을 비교하지 않고 두 행성간 가장 작은.. PS(Problem Solving)/BOJ 2022. 8. 4.

• [백준/BOJ] 1238번: 파티 문제 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 해설 문제의 핵심을 찾아보면 다음과 같다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 최단 시간에 오고 가기를 원한다. 단방향이기 때문에 오고 가는 길이 다를지도 모른다. 최단 시간을 구하는 문제이기에 다익스트라 알고리즘을 이용하면 된다. 파티를 갔다가, 다시 집에 돌아오는 시간까지 계산해야 하기 때문에, 각 노드 당 2번.. PS(Problem Solving)/BOJ 2022. 8. 4.

• [백준/BOJ] 1854번: K번째 최단경로 찾기 문제 https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 해설 다익스트라 알고리즘을 이용해서 풀 수 있는 문제이다. 이 문제에서는 각 노드마다 우선순위 큐를 두어 이 노드를 방문할 때마다의 시간을 저장할 것이다. val time = Array(cityCnt + 1) { PriorityQueue(reverseOrder()) } 이 때, 큰 수가 top에 오도록 해야 한다. 즉 내림차순이어야 한.. PS(Problem Solving)/BOJ 2022. 8. 3.

• [백준/BOJ] 1916번: 최소비용 구하기 문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 해설 A번째 도시에서 B번째 도시로 가는데 필요한 최소 비용을 구하는 문제이다. 따라서 다익스트라 알고리즘을 사용하면 된다. 한 도시에서 다른 도시로 가는 버스는 다시 돌아오지 않으므로 단방향이다. 따라서 다익스트라를 진행하기 위한 그래프를 설정할 때 양방향이 아닌 단방향으로 비용을 저장해주면 된다. 다익스트라를 다 수행하고 특정 도시까지 최소 비용을 출력해.. PS(Problem Solving)/BOJ 2022. 8. 3.

• [백준/BOJ] 1753번: 최단경로 문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 해설 다익스트라 알고리즘을 사용하여 해결할 수 있는 문제이다. 문제에서 방향그래프가 주어진다고 되어있다. 따라서 단방향으로만 그래프를 설정해주면 된다. 다익스트라 알고리즘을 잘 모른다면 다익스트라 알고리즘 글을 읽어보면 이 문제를 쉽게 풀 수 있을 것이다. 소스 코드 import java.util.* import kotlin.collections.Arra.. PS(Problem Solving)/BOJ 2022. 8. 3.

• 

  [알고리즘] 다익스트라 알고리즘(Dijkstra Algorithm) 다익스트라 알고리즘(Dijkstra Algorithm)은 다이나믹 프로그래밍을 활용하는 대표적인 최단 경로를 찾는 알고리즘이다. 다만 다익스트라 알고리즘은 음의 간선을 포함할 수 없다. 즉, 음의 간선이 하나라도 포함되어 있다면, 다익스트라 알고리즘을 사용할 수 없다. 원래 다익스트라 알고리즘은 두 꼭짓점 간의 가장 짧은 경로를 찾는 알고리즘이다. 하지만, 일반적으로 한 꼭짓점을 루트(root) 꼭짓점으로 고정하고, 그래프의 다른 모든 꼭짓점까지의 최단 경로를 찾는 알고리즘으로 최단 경로 트리를 만든다. 동작 단계 출발 노드를 설정한다. 최단 거리를 저장할 테이블을 초기화해준다.(보통 무한대(아주 큰 값)로 초기화한다.) 현재 위치하고 있는 노드의 인접 노드 중 비용이 가장 적은 노드를 선택한다. 해당 .. Algorithm 2022. 8. 3.

• 

  파이썬: 리스트 내포(List Comprehension) 리스트 내포(List Comprehension) 파이썬에서는 for문과 if문을 한 라인에 작성하여 코드를 간결하고 직관적으로 만들며, 실행속도를 높혀주는 기법인 리스트 내포 기법이 존재한다. 형태는 다음과 같다. 리스트 명 = [표현식 for 변수 in 반복 가능한 대상] 예를 들면 다음과 같다. list = [i for i in range(20)] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] 이렇게 하면, 0부터 19까지의 수가 리스트로 변환되게 된다. 처음에도 말했듯, 리스트 내포는 for문과 if문을 한 라인에 작성할 수 있다. 조건을 추가했을 떄의 형태는 다음과 같다. 리스트 명 = [표현식 for 변수 in 반복.. Programming/Pyhton 2022. 8. 2.

• [백준/BOJ] 15686번: 치킨 배달 문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 해설 브루트 포스(Brute Force) 문제이다. 문제에서 원하는 것은 결국, 모든 집에 대해 가장 가까운 치킨집까지의 거리의 합이다. 내가 푼 문제 해결 과정(알고리즘)은 다음과 같다. 맵을 입력받으면서, 집과 치킨집의 좌표를 저장해둔다. 모두 저장했다면, dfs를 수행하며 남길 치킨집을 선택한다. visited 배열을 방문처리를 해준 후의 갯수를 세고, 이를 다시 .. PS(Problem Solving)/BOJ 2022. 8. 2.