본문 바로가기

알고리즘 문제77

[프로그래머스 - Java] 다리를 지나는 트럭 문제 https://programmers.co.kr/learn/courses/30/lessons/42583 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 programmers.co.kr 설명 처음엔 이걸 어떻게 풀어야 하지? 다리만큼 배열을 써서 트럭이 지나가는 것처럼 해야 하나...? 별별 생각이 다 들었다. 하지만 이 문제가 스택 / 큐 문제로 분류된 만큼 생각을 해보니 큐로 간단히 풀 수 있다! 큐를 다리라고 생각하고, 조건에 맞게 트럭을 큐에 넣고 빼면서 다리에 오르고 건너는 것을 구현하면 된다. 고려해야.. 2021. 6. 10.
[프로그래머스 - Java] N진수 게임 (2018 KAKAO BLIND RECRUITMENT) 문제 programmers.co.kr/learn/courses/30/lessons/17687 코딩테스트 연습 - [3차] n진수 게임 N진수 게임 튜브가 활동하는 코딩 동아리에서는 전통적으로 해오는 게임이 있다. 이 게임은 여러 사람이 둥글게 앉아서 숫자를 하나씩 차례대로 말하는 게임인데, 규칙은 다음과 같다. 숫자를 0 programmers.co.kr 설명 우선 10진수로 표현된 수를 n진법으로 변환시켜야 한다. (10진수 n진수 변환은 아래에서 설명) 변환된 수를 ArrayList에 차곡차곡 저장한다. 튜브 순서에 말할 수가 List에 없다면 현재 튜브 순서의 숫자를 진수 변환시켜 List에 저장하는 것을 반복하며 게임을 진행한다. 10진수로 N진수 구하기 1. List, Stack과 같은 자료구조 .. 2021. 5. 8.
[백준 - Java] 17142번 : 연구소3 문제 www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 설명 연구소1 문제와 비슷한 문제지만 조금은 다름. 기존 연구소 문제는 아래 포스트를 참고 [백준 - Java] 14502번 : 연구소 (삼성 SW 역량 테스트 기출 문제) 백트래킹으로 바이러스를 퍼뜨릴 수 있는 공간에 M개의 바이러스를 놓아 활성화시켜봄. M개의 바이러스를 활성화시켰다면 BFS로 바이러스를 퍼뜨림. 모든 빈칸에 바이러스를 퍼뜨렸다면 그때까지 걸린 시간 Math.min()으로 min 변수에 저장. .. 2021. 4. 21.
[백준 - Java] 15684번 : 사다리 타기 문제 www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 설명 자잘한 실수도 많이 하고, 필요 없는 map을 만든다 거나, class로 좌표를 저장하고 ArrayList에 넣었다 뺐다, ArrayList를 복사하던가 삽질을 겁나 많이 했음. 막상 풀고나니 별거 없었고, 나는 4차원 배열까지 써서 해결했는데, 2차원 배열만 썼어도 됨... 삼성 SW역량테스트 기출문제인데, 나는 아마 주어진 3시간 동안 이 문제 계속 쩔쩔매다가 왔을 듯;;;;ㅜㅜ아웅ㅇ 열 받아!.. 2021. 4. 18.
[백준 - Java] 14890번 : 경사로 문제 www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 설명 문제의 조건대로 구현하면 되는 문제이다. 하지만 조건을 이것저것 맞추다 보니 빼먹기도 하고, 경사로가 꼬이기도 해서 시간이 꽤나 걸렸던 문제다ㅠㅠ * 경사로를 놓는 조건 길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다. 또는, 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다. 경사로는 높이가 항상 1이며, 길이는 L이다. 또, 개수는 매우 많아 부족할 일이 없다. 경사로는 낮은 칸과 높은 칸을 연.. 2021. 4. 16.
[백준 - Java] 1238번 : 파티 문제 www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 설명 다익스트라 알고리즘을 이용해 구현하면 된다. 📌 더 자세히 알고 싶다면 아래 포스팅을 참고해주세요 [Java] 다익스트라 (Dijkstra) 최단 경로 알고리즘 하지만 각 구현 방식에 따라 걸리는 시간과 메모리가 천차만별이다. 1. 인접 행렬로 정점과 간선을 표현하고, 기본 다익스트라 알고리즘을 이용해 구현 (2992, 2360 ms) N개의 마을에서 X까지 N번, X에.. 2021. 4. 13.
[백준 - Java] 13460번 : 구슬 탈출 2 (삼성SW역량테스트 기출 문제) 문제 www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 설명 엄청나게 시간이 오래 걸렸던 문제... 막상 풀고 나니 왜 진즉에 생각 못했을까 싶고... 아무튼 이 문제는 빨간 구슬과 파란 구슬이 동시에 움직이기 때문에 따로 생각하면 안 되고 같이 생각해야 한다. 따라서 구슬의 위치를 담는 클래스도 빨간, 파랑 구슬의 위치 둘 다 가지게 만들었다. 또한 BFS를 수행하며 최단 거리로 탈출해야 하는데, 이때 방문 .. 2021. 4. 11.
[백준 - 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.
반응형

티스토리툴바