본문 바로가기

분류 전체보기51

[백준] 6087 : 레이저 통신(JAVA), 다익스트라 https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 방향을 회전시킨다기에 시뮬레이션 문제인가 싶어서 삽질을 했다. 결론적으로 C에서 C까지 최소 개수의 거울(최소비용)을 사용하는 경로를 찾는 다익스트라 문제였다. 기본적으로 다익스트라를 적용시키되, 주의해야할 점은 (x,y) 지점에 오기 까지 사용한 비용(거울의 수)가 같더라도 직전 방향에 따라 다음 지점에서의 비용이 달라지기 때문에 같은 비용까지는 우선순위 큐에 넣어주어야 한다는 점이다... 2023. 1. 25.
[백준] 2749 : 피보나치의 수 3 (JAVA) / 피보나치 수 구하는 방법, 재귀, 메모이제이션, 행렬) https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 전형적인 피보나치 문제인데, 골2길래 뭔가 싶어 풀어봤다. 이 문제의 주의할 점을 몇가지 뽑자면 입력값 n의 크기가 10^18 로 매우 크다. int 형이 아닌 long 으로 입력을 받아야한다. n번째 피보나치 수를 구하기에, n이 매우 크므로 재귀방식이 아닌 행렬을 사용해풀어야 하지만 이 또한 n이 크기 때문에 O(n) 으로는 해결하기 애매하다. 1,000,000 으로 나눈 나머지를 출력한다는 부분이 힌트. 결론적으로 피사노 주기(Pisano Period)를 이용하여 풀어야하.. 2023. 1. 19.
[백준] 1956 : 운동 (JAVA), 플로이드-와샬(Floyd-Warshall) https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net Solution 사이클을 이루는 도로의 길이의 합이 최소가 되는 것을 찾기 위해서는 모든 정점으로 부터 모든 정점까지의 최단 거리를 구해야한다. 이 때, 가중치 c의 범위가 10,000 이하의 자연수 이므로 음의 가중치를 갖지 않는다. 또한, V가 400이하로 범위가 작다. 다익스트라, 플로이드-와샬 둘 다 가능하다. 나는 플로이드-와샬을 사용했다. 플로이드 와샬.. 2023. 1. 18.
[알고리즘] 플로이드-와샬, Floyd-Warshall 백준 문제를 풀다가 플로이드-와샬 문제를 또 마주쳤다. 몇 번 풀어본적 있는 유형임에도 플로이드 와샬이 뭐더라... 싶더라. 인간은 망각의 동물이구나... 플로이드-와샬 알고리즘 모든 정점에서 모든 정점으로 최단 경로를 구하는 알고리즘 시간 복잡도 O(v^3) 음수 사이클이 없는 그래프에 적용됨 음의 가중치 허용 플로이드-와샬(Floyd Warshall) vs. 다익스트라(Dijkstra) 다익스트라 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘 (S.S.S.P - Single Source Shortest Path) 매번 가장 적은 비용을 가진 노드를 하나씩 꺼낸 다음 그 노드를 거쳐가는 비용, 즉 가장 적은 비용을 하나씩 선택하는 로직 우선순위 큐 + BFS의 형태 시간 복잡도 O(.. 2023. 1. 18.
[JAVA] LocalDateTime vs. Instant (feat. ZonedDateTime, OffsetDateTime) java.time 패키지를 공부하는 중, Instant 클래스에 대해 처음 알게되었다. 평소 프로젝트를 할 때는 LocalDateTime 을 사용했는데, Instant를 사용해야 좋은 경우는 무엇이 있는지 궁금증이 생겼다. 살펴보던 와중 LocalDateTime 을 엔티티 칼럼으로 지정한 필드는 DB에 무슨 형식으로 저장했더라... 하고 살펴보니 냅다 문자열로 저장했거나 datetime 형식이다. datetime 형식은 SQL 표준에 맞지않고 정확도가 떨어져 공식문서에서는 권장하지 않는다고 하니 다음번에 프로젝트를 할 땐 DB쪽 형식도 제대로 찾아보고 설정해야겠다 😅ㅎ java.time 패키지의 핵심 클래스 날짜와 시간을 하나로 표현하는 Calendar 클래스와 달리, java.time 패키지에서는 날짜.. 2023. 1. 17.
[JAVA] 다형성과 형변환 (상속과 참조변수, Up-casting, Down-casting) 다형성이란? 객체지향개념에서 다형성이란 '여러 가지 형태를 가질 수 있는 능력'을 의미하며, 자바에서는 한 타입의 참조변수로 여러 타입의 객체를 참조할 수 있도록 함으로써 다형성을 프로그램적으로 구현하였다. 구체적으로, 조상클래스 타입의 참조변수로 자손클래스의 인스턴스를 참조할 수 있도록 하였다 는 것이다. class Tv { boolean power; int channel; void power() { power = !power; } void channelUp() { ++channel; } void channelDown() { --channel; } } class CaptionTv extends Tv{ String text; void caption(){...} } 위와 같은 상속 관계의 클래스가 정의되어.. 2023. 1. 3.

티스토리툴바