본문 바로가기

분류 전체보기137

[백준 - Java] 1753번 : 최단경로 문제 www.acmicpc.net/problem/1504www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 설명 다익스트라 구현 시 인접 행렬을 사용하게 되면 2만 개의 정점에 대해 2만 개 정점으로 가는 간선들을 저장해야 하는데, 간선 하나당 1바이트에 저장한다고 하더라도 4억 바이트, 약 400MB의 메모리를 쓰게 될 뿐 아니라 시간 복잡도 역시 O(V^2)으로 좋지 못하게 된다. 최단 경로 (다익스트라 알고리즘) FAQ 따라서 인.. 2021. 3. 20.
[백준 - Java] 1504번 : 특정한 최단 경로 문제 www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 설명 백준 1753번 최단 경로 문제를 응용하면 되는 문제이다. 📌 다익스트라 알고리즘에 대해 더 알고싶다면 아래 포스팅을 참고해주세요! [Java] 다익스트라 (Dijkstra) 최단 경로 알고리즘 전체 코드 import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; .. 2021. 3. 20.
[백준 - Java] 1916번 : 최소비용 구하기 문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 설명 다익스트라 알고리즘을 이용하면 쉽게 풀 수 있는 문제다. 📌 다익스트라 알고리즘에 대해 알고 싶다면 아래 포스팅을 확인해주세요. [Java] 다익스트라 (Dijkstra) 최단 경로 알고리즘 전체 코드 * 무한대를 처음엔 Integer.MAX_VALUE로 했는데 오버플로우가 나는지 채점 중 런타임 에러가 났다ㅠㅠ 무한대 값을 Integer.MAX_VAL.. 2021. 3. 16.
[백준 - Java] 1261번 : 알고스팟 문제 www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 설명 처음엔 BFS로 최단 거리로 가면 되려나?라고도 생각했지만, 기존의 BFS로는 풀 수 없는 문제이다. 최단 거리도 필요 없고, (0, 0) 정점에서 부터 너비 우선 탐색을 해나가며 벽을 더 적게 부수는 방법으로 (M, N)까지 나아가야한다. 이를 위해서 기존의 Queue가 아니라 Deque를 사용했다. Deque는 Queue의 앞 뒤로 값을 삽입할 수 있다. Deque의 앞쪽을 .. 2021. 3. 16.
[백준 - Java] 6087번 : 레이저 통신 문제 www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 설명 2020 카카오 인턴십 문제로 나왔던 경주로 건설과 비슷한 문제이다. 자세한 설명은 경주로 건설 포스팅을 참고해주세요. [프로그래머스 - Java] 경주로 건설 (2020 카카오 인턴십) 경주로 건설은 직선, 코너 도로마다 비용이 부과되는데 둘을 적절히 사용해 가장 적은 비용으로 경주로를 건설해야 한다. 레이저 통신도 마찬가지이다. 레이저를 쏘는데 거울을 가장 적게 쓰는 방법으로 C에서 다른.. 2021. 3. 15.
[정보처리기사] 2021년 3월 7일 1회 정보처리기사 필기 시험 후기 우선 나는 컴퓨터학과를 졸업했기 때문에 정처기의 웬만한 내용은 학교에서 배웠다 이것을 감안하고 읽어주시길...! 1. 필기 공부 과정 2월 초에 시나공 정보처리기사 필기 책을 구입했다! 실제 공부한 기간은 약 2주인데 2주를 힘들게 공부한 게 아니라 시나공 책에 정리된 내용을 읽고 이해한 뒤에 책의 문제를 푸는 정도로? 2주지만 격일로 예를 들어 한두 시간 투자했다. 솔직히 제대로 공부한 기간은 필기시험 3일 전부터다. 3일 전, 일단 시나공 책 1 회독 (정독 아님 후루룩 보면서 관련 문제 풀 정도로) 후 문제 푸는 것 마무리. 이후 2020 기출 3회 및 시나공에서 만든 모의고사 2회를 풀고 틀린 문제에 대한 해설을 보고 이해하는 식으로 공부했다. * 2020 기출문제의 경우 시나공 책으로 안 풀고 .. 2021. 3. 12.
[Java] 다익스트라 (Dijkstra) 최단 경로 알고리즘 다익스트라 (Dijkstra) 알고리즘 하나의 시작 정점으로부터 모든 다른 정점까지의 음의 가중치가 없을 때 최단 경로를 찾는 알고리즘 다익스트라 알고리즘에서 음수 간선이 존재하면 안 되는 이유 다익스트라 알고리즘의 각 단계 먼저 집합 S를 시작 정점 v로부터의 최단경로가 이미 발견된 정점들의 집합이라고 하자. 다익스트라 알고리즘에서는 시작 정점에서 집합 S에 있는 정점만을 거쳐서 다른 정점으로 가는 최단거리를 기록하는 배열이 반드시 있어야 한다. 이 1차원 배열을 distance라고 한다. 시작 정점을 v라 한다면 distance[v] = 0이고, 다른 정점에 대한 distance값은 시작 정점과 해당 정점 간의 가중치 값이 된다. 가중치 인접 행렬을 weight라 하면 distance[w] = wei.. 2021. 3. 12.
[백준 - Java] 10836번 : 여왕벌 문제 www.acmicpc.net/problem/10836 설명 매일매일 애벌레를 키우면 무조건 시간 초과가 난다!! 1,000,000 최대 백만일까지 애벌레를 키울 수 있기 때문!! 잘 생각해보면 매일 애벌레를 키워할 필요가 없다! 제일 왼쪽 열과 제일 위쪽 행의 애벌레만 주어지는 N날 동안 주어지는 0, 1, 2로 키우고, 나머지 (1, 1) ~ (M, M) 애벌레들은 N날이 지난 후, 문제의 조건 2에 따라 자신의 왼쪽(L), 왼쪽 위(D), 위쪽(U)의 애벌레들 중 가장 큰 사이즈로 키워진 애벌레의 크기로 바꿔주면 됨! 매일매일 키워보는 거나 제일 왼쪽 위쪽 다 키우고 적용하는 거나 둘은 같다! 그러니 다 키우고 적용하는게 훨 시간을 줄일 수 있다. * Scanner써서 입력받거나 println으.. 2021. 3. 3.
[백준 - Java] 11967번 : 불켜기 문제 www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 설명 data-make.tistory.com/577 [BOJ] 11967.불켜기(완탐).java #. Problem https://www.acmicpc.net/problem/11967 * The copyright in this matter is in BOJ #. Resolution Process 1. Read and understand problem 2.. 2021. 3. 1.
[백준 - Java] 8972번 : 미친 아두이노 문제 www.acmicpc.net/problem/8972 8972번: 미친 아두이노 요즘 종수는 아두이노를 이용해 "Robots"이라는 게임을 만들었다. 종수는 아두이노 한대를 조정하며, 미친 아두이노를 피해다녀야 한다. 미친 아두이노는 종수의 아두이노를 향해 점점 다가온다. www.acmicpc.net 주절주절... 어떻게 하면 최적으로 문제를 풀 수 있을까 고민을 많이 했던 문제다. 미친 아두이노가 파괴되었나 안되었나 상태 변수를 만들어 관리하기도 했었고, 반례를 생각하지 못한 코드를 짠 경우도 있었고 (ex. 2개 이상의 미친 아두이노가 같은 칸으로 이동하는 경우) 같은 칸으로 이동할 경우 이전에 이동한 아두이노를 미리 움직여서 보드판이 뒤죽박죽으로 나오기도 하고... 맵을 지웠다. 다시 썼다. 복.. 2021. 3. 1.
반응형

티스토리툴바