본문 바로가기
반응형

알고리즘113

백준 1922번 : 네트워크 연결 java 이 문제는 최소 비용 신장 트리를 만드는 방법입니다. 최소 비용 신장 트리를 만드는 방법에는 프림 알고리즘과 크루스칼 알고리즘이 있습니다. 저는 이 문제를 풀 때 프림 알고리즘을 선택해서 풀었습니다. 크루스칼 알고리즘을 이용하여 최소 비용 신장 트리를 만드는 방법은 아래의 링크에 있습니다. 백준 1197번 : 최소 스패닝 트리 java 이 문제는 최소 비용 신장 트리를 만드는 문제입니다. 최소 비용 신장 트리를 만들기 위한 알고리즘에는 크루스칼 알고리즘과 프림 알고리즘이 있습니다. 크루스칼 알고리즘은 간단히 말해서 dy-coding.tistory.com 프림 알고리즘이란 임의의 정점을 기준으로 그 정점의 경로와 연결된 다른 정점들의 경로 중에서 가장 가중치가 적은 경로를 선택하며 최소 비용 신장 트리를 .. 2022. 6. 18.
백준 3190번 : 뱀 java 이 문제는 사과가 있는 곳을 입력받아서 뱀이 사과가 있는 곳을 지나치면 뱀의 길이를 늘이고 아니면 유지하게 합니다. 그리고 시간이 경과함에 따라서 방향을 회전시키게 해서 뱀이 벽이나 자신의 몸에 머리를 박으면 게임이 끝나게 합니다. 이 문제를 예제 1번을 이용하여 설명드리겠습니다. 예제 1번의 초기 상태는 다음과 같습니다. 위에 spin 큐에 들어가 있는 것들은 X초 후에 어떤 방향으로 회전하는가를 나타냅니다. L이면 보고 있는 방향의 왼쪽으로 회전, D면 오른쪽으로 회전합니다. 사과를 먹으면 길이가 늘어나고 먹지 않으면 길이를 유지합니다. 이제 뱀을 이동시켜보겠습니다. 우선 문제의 조건에 맞게 뱀을 한 칸 앞으로 보냈습니다. 그러나 사과를 먹지 않았으므로 길이가 늘지 않아 빨간 화살표를 지워줍니다. 다.. 2022. 6. 18.
백준 1987번 : 알파벳 java 이 문제는 깊이 우선 탐색을 이용해서 칸을 이동하면서 같은 알파벳이 적힌 칸을 두 번 지나지 않고 최대 갈 수 있는 칸을 구하는 문제입니다. 이 문제에 대해서 그림을 통해 자세히 설명드리도록 하겠습니다. 예제 1번을 표에 나타내면 위의 그림과 같습니다. 저는 이 문제를 풀 때 이미 지나간 알파벳은 set에 저장하여 다시 지나가지 않도록 했습니다. ArrayList나 LinkedList는 contains 메소드에 대한 시간 복잡도가 O(n)입니다. 하지만 HashSet을 통해서 set을 구현하면 O(1)의 시간 복잡도로 contains 메소드를 사용 가능합니다. 따라서 set을 사용하지 않으면 시간 초과가 나므로 set을 사용하였습니다. 이 문제에서 시작점은 1행 1열이니 여기서 dfs를 시작합니다. 이제.. 2022. 6. 17.
백준 14891번 : 톱니바퀴 java 이 문제는 문제에서 주어진 조건에 따라서 문제를 해결할 수 있는 알고리즘을 구현하는 문제입니다. 이 문제에서 주어진 조건에 대해서 설명해드리겠습니다. 위의 그림을 보시면 2번 톱니바퀴를 시계방향으로 굴린다고 가정했을 때 1번 톱니바퀴는 2번 톱니바퀴와 맞닿은 톱니가 서로 반대의 극을 가지고 있기 때문에 2번 톱니바퀴의 반대 방향인 반시계 방향으로 돌아가게 됩니다. 그리고 3번 톱니바퀴는 2번 톱니바퀴와 맞닿은 부분이 같은 극을 가지고 있기 때문에 돌아가지 않습니다. 이 알고리즘을 기반으로 코드를 구현해보도록 하였습니다. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws .. 2022. 6. 17.
백준 1065번 : 한수 java 이 문제는 N보다 작거나 같은 한수의 개수를 출력하는 문제입니다. 한수란 어떤 양의 정수 X의 각 자리가 등차수열을 이루는 수입니다. 이러한 수의 예시는 123, 135, 159와 같은 수들이 있습니다. 문제에 대한 코드를 보시면 바로 이해하실 수 있으실 겁니다. import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int count = 0; for(int i = 1; i 2022. 6. 17.
백준 13335번 : 트럭 java 이 문제는 자료 구조 큐를 이용하여 위에서 주어진 조건에 맞게 최단시간을 구하는 알고리즘입니다. 저는 이 문제를 풀기 위해서 대기 중인 트럭들을 보관할 큐와 다리 위에 올라간 트럭들을 저장할 큐를 사용하였습니다. 각각의 큐에는 입력받은 자료의 무게와 인덱스를 저장하게 해서 문제를 해결하였습니다. 그림을 통해서 이를 자세히 설명드리도록 하겠습니다. 위의 그림은 예제 1번을 표현한 그림입니다. truck 큐에 들어가 있는 자료들은 다리에 올라가기 위해서 대기 중인 트럭들을 의미합니다. bridge 큐에 들어있는 자료들은 다리 위에 올라가 있는 트럭들을 의미합니다. location배열은 몇 시간 뒤면 트럭이 다리에서 빠져나오는지를 확인하기 위해서 만든 배열입니다. 트럭이 bridge 큐에 들어가면 해당 ind.. 2022. 6. 16.
백준 14503번 : 로봇 청소기 java 이 문제는 주어진 조건에 맞게 코드를 만드는 문제입니다. 그림을 통해서 이 문제에 대한 설명을 드리도록 하겠습니다. 위의 그림과 같이 자료가 주어졌다고 가정해보도록 하겠습니다. 또한 로봇 청소기가 있는 위치는(1, 2)로 주어졌고, 방향은 2인 남쪽이 주어졌다고 하겠습니다. 이를 지도 위에 나타내 보겠습니다. 그럼 위의 그림과 같은 모양이 됩니다. 이때 문제의 1번 작업을 해줍니다. 청소한 위치는 빨간색으로 표시하겠습니다. 1번 작업을 하였으니 이제 2번 작업을 실행시켜 줍니다. 로봇은 남쪽을 바라보고 있었으니 이 로봇의 왼쪽은 동쪽이 됩니다. 로봇의 동쪽에는 청소하지 않은 구역이 있고 벽이 아니니 이 방향으로 이동시켜줍니다. 위와 같은 그림이 됩니다. 1번 작업을 통해 현재 있는 칸을 청소해준 다음 2.. 2022. 6. 16.
백준 2294번 동전 2 java 이 문제는 다이나믹 프로그래밍을 이용하여 동전과 가치의 합이 주어질 때 동전의 개수가 최소가 될 때를 찾는 문제입니다. 이 문제는 아래의 문제와 비슷한 풀이로 풀 수 있으니 아래의 문제를 보고 오시는 것을 추천드립니다. 백준 2293번 : 동전 1 java 이 문제는 다이나믹 프로그래밍을 이용하여 N개의 동전을 이용하여 K원이 되게 하는 경우의 수를 구하는 문제입니다. 저는 이 문제를 N개의 동전의 가치들을 배열에 저장한 후 1원을 만들 때의 dy-coding.tistory.com 저는 이 문제를 N개의 동전의 가치들을 배열에 저장한 후 1원을 만들 때의 동전의 수부터 N원을 만들 때의 동전의 수를 저장해가며 해결하였습니다. 예제 1번을 이용하여 문제를 해결하는 과정을 설명드리겠습니다. cnt[i]는 동.. 2022. 6. 15.
반응형

티스토리툴바