본문 바로가기

전체 글122

[알고리즘] 다익스트라 최단 경로 알고리즘 (Dijkstra Algorithm) [알고리즘] 다익스트라 최단 경로 알고리즘 (Dijkstra Algorithm) 다익스트라 알고리즘은 출발지 -> 경유지 -> 목적지를 이용하여 최단 경로를 구하게 된다. 이 과정을 반복하게 되면 고정된 출발지에서 모든 edge의 최단 경로를 구할 수 있다. 필요 사항 우선 순위 큐 (순서대로 확인하는 것이 아닌, 거리가 가장 짧은 것부터 수행하기 때문에 수행 시간을 단축) 고정된 출발지에서 목적지까지의 경로 값 저장 배열 최소 비용을 만들기 위해 필요한 Node의 개수는 항상 3개라고 생각해야 한다. [출발, 경유, 목적] 출발지 -> 경유지, 경유지 -> 목적지로 따로 생각해야 한다. 경유지를 반복문을 돌리므로 목적지는 복수개다. 주목할 부분은 경유지 -> 목적지 인 부분이다. 목적지였던 부분이 다음.. 2022. 4. 20.
[백준] 1253번 좋다 (JAVA) 투 포인터를 이용한 문제다. 투 포인터를 둘다 시작 지점으로 놨더니 생각할게 너무 많아지고, 시간복잡도도 증가했다. 투포인터를 시작지점, 끝점으로 양쪽으로 옮겨서 구현했더니 간단하게 풀렸다. 구간합이 아니면 투포인터를 시작지점에 두지 말아야 겠다. 코드구현 import java.io.*; import java.util.*; import java.util.function.*; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); public static void main(String[] args) throws IOException { int count = Integer.parseI.. 2022. 4. 19.
[알고리즘] 플로이드 워셜 알고리즘 (Floyd Warshall Algorithm) [알고리즘] 플로이드 워셜 알고리즘 (Floyd Warshall Algorithm) 플로이드 워셜 알고리즘은 edge에서 edge로 이동할 때 최소비용을 구하는 알고리즘이다. 모든 경로의 최소비용을 구할 수 있다. 구현 플로이드 워셜 알고리즘의 구현은 간단하다. k, i, j를 사용하는 3중 for문이 있을 때 3중 for문으로 가장 바깥 k를 사용하는 for문은 edge의 총개수만큼 반복한다. k는 중간에 거쳐가는 edge이다. i는 시작 edge, j는 도착 egde로 사용한다. 현재 비용보다 거쳐가는 비용이 더 적다면 거쳐가는 비용을 사용한다. 자기 자신으로 가는 경로는 0, 도착이 불가능한 경로는 INF(충분히 큰 값)로 표시한다. 이해 구현은 간단하지만 이해는 쉽지 않았다. 플로이드 워셜 알고리.. 2022. 4. 17.
[백준] 13418 학교 탐방하기 (JAVA) https://www.acmicpc.net/problem/13418 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1 ≤ N ≤ 1,000)과 도로의 개수 M(1 ≤ M ≤ N(N-1)/2) 이 주어진다. 입력의 두 번 www.acmicpc.net 최소 신장 트리 (MST)를 알아야 풀 수 있는 문제다. 문제는 (최대 신장 트리 - 최소 신장 트리)의 값을 요구한다. 제곱을 해줘야 하긴 하지만 사소하기 때문에 MST를 적용하면 풀 수 있는 문제다. 크루스칼, 프림 모두 적용 가능하며 크루스칼을 이용해서 해결했다. 우선순위 큐에서 최대 신장 트리, 최소 신장 트리로 정렬할 수 있도록 두 가지 방식으로 정렬하.. 2022. 4. 15.
[백준] 2252번 줄세우기 (JAVA) https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 위상정렬을 이용한 문제다. 정점 1의 간선이 정점 3에 방향그래프로 연결되어있다면 1을 처리해준 후 3을 정렬시켜 주면된다. 만약 정점 3을 향해 연결된 정점 2가 하나 더 있다면 정점 3은 정점 2 이후에 나열될 수 있다. 정점1과 정점2는 순서가 없으므로 1 -> 2 -> 3 2 -> 1 -> 3 둘다 가능하므로 나열하는 순서는 뒤바뀔 수 있다. "자.. 2022. 4. 15.
[애드센스] AdSense 본문 페이지 중간 광고 없애기 [애드센스] AdSense 본문 페이지 중간 광고 없애기 공부한 내용을 정리할 겸 블로그를 운영 중인데, 작성한 글을 다시 보려고 할 때마다 페이지 내 중간 광고가 가독성을 굉장히 방해했다. 방문자도 마찬가지로 가독성이 좋지 않을 것이라 판단했고, 광고 노출은 줄겠지만 가독성을 위해 중간광고는 포기하려고 한다. 노출 RPM과 관련 있는지는 모르겠다. 애드센스 페이지 내 광고 - 개요 수정 클릭 인 페이지 광고 OFF 이렇게 설정하면 더 이상 본문 페이지 내에서 중간에 광고가 삽입되지 않는다. 2022. 4. 13.

티스토리툴바