본문 바로가기

알고리즘 문제/백준50

[백준 - Java] 1759번 : 암호 만들기 문제 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 설명 조합을 이용해 주어진 C개의 문자로 만들 수 있는 L개의 암호 조합을 구하면 된다. 조합을 구한 뒤에는 모음의 개수가 적어도 1개 이상, 자음의 개수가 2개 이상이 되는 경우만 정답 리스트에 추가하면 된다. 아래 조합 포스트를 참고하면 좋다. [Java] 조합 Combination 전체 코드 import java.util.ArrayList; import java.util.Arrays; imp.. 2021. 7. 27.
[백준 - Java] 4386번 : 별자리 만들기 문제 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 설명 주어진 각 별의 좌표를 이용해 모든 간선을 만들고 가중치(두 별 사이의 거리)를 저장한다. Kruskal 알고리즘을 이용해 최소 신장 트리를 구성해 최소 비용을 구한다. 크루스칼 알고리즘은 Union-Find를 이용해 구현할 수 있다. 전체 코드 import java.util.ArrayList; import java.util.Collections; import java.util.Scann.. 2021. 7. 27.
[백준 - Java] 1987번 : 알파벳 문제 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 설명 DFS, 백트래킹을 이용해 구현 (0, 0)부터 시작해서 상하좌우 이차원 배열 범위를 넘지 않고, 방문하지 않았던 곳으로 이동 이동할 곳에 있는 알파벳이 지금까지 DFS를 돌며 만들어진 문자열 str에 포함되지 않는 문자라면 str에 추가하고 길이도 +1 가장 최장 길이를 구해야 하기 때문에 매 DFS마다 길이 length와 최장 길이를 저장할 ans의 값을 비교해 업데이트 해주.. 2021. 7. 16.
[백준 - 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.
반응형

티스토리툴바