본문 바로가기

전체 글

 (45)
[백준 17404: JAVA] RGB거리 2 / 동적 프로그래밍 개요 dp로 문제를 풀 수 있다. 이 문제는 dp를 생각하면 금방 풀이할 수 있지만, 약간의 조건이 추가되어 있기 때문에 생각을 좀 해야 했다. 첫 집과 마지막 집도 색이 같으면 안 된다는 조건이 있기 때문에 첫 집의 색을 고정 시키고 두 번째 집부터 마지막 집까지 3가지 색을 조합하며 최솟값을 구하여 dp배열을 채워준다. 그 후 마지막에 최솟값을 구할 때 고정시킨 첫 집의 색과 다른 마지막 집의 값들에서 최솟값을 추출해내면 된다. 문제 RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑 중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집도 이웃이다. 각 집을 빨강으로 칠할 때 드는 비용, 초..
[백준 10815: JAVA] 숫자 카드 / 이분 탐색 개요 기본적인 이분 탐색을 이용하면 풀이할 수 있다. 일반적으로 이분탐색을 모르면 for문을 끝까지 돌려서 찾으려 할 것이다. 그러나 그렇게 하면 이 문제의 경우 최대 (500,000 * 20,000,000) 번 탐색을 하게 된다. 시간 초과가 발생하기 때문에 이분 탐색을 이용하면 더 빠르게 찾을 수 있다. 문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오. 입력 풀이 이분탐색을 위해 정렬을 진행하고 나면 arr배열에는 아래와 같이 데이터가 정렬이 된다. 문제에서 찾고자 하는 숫자를 num이라고 한다면, 1. 초기 값으로 left = 0, ri..
[백준 2098: JAVA] 외판원 순회 / dp + 비트 마스크 개요 이 문제는 외판원 순회 문제로 TSP(Traveling Salesman Problem) 으로 불린다. 비트 마스크를 dp를 사용할 때 어떻게 활용할 수 있는지 알 수 있는 문제이다. 만약 비트 마스크가 뭔지 모른다면 아래의 문제와 풀이를 먼저 보고 오는 것을 추천한다. https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 2020/02/12 - [알고리즘/백준] - [백준 11723 : JAVA] 집합 / 비트마스크 [백준 11723 : JAVA] 집합 / 비트마스크 개요 이 문..
[백준 11723 : JAVA] 집합 / 비트마스크 개요 이 문제는 비트 마스크의 기본적인 개념을 활용하면 풀이할 수 있는 문제이다. 처음에는 boolean[]을 선언해서 풀었다. boolean [20]을 선언하여 b [0] ▶ true이면 1이 있는 것, false이면 1이 없는 것으로 풀이했다. 그러나 문제 이름처럼 bitmask를 이용하면 더욱 메모리를 효율적으로 사용할 수 있다. int 자료형 a를 선언하면 4바이트(4 * 8bit)를 메모리에 할당받아 총 32개에 대에 참, 거짓을 판단할 수 있게 된다. a = 00000000 00000000 00000000 00000000(2)로 메모리에 할당받는다. 따라서, 총 0~31까지 수의 집합을 나타낼 수 있다. 2^0자리 ▶ 0의 true, false 2^1자리 ▶ 1의 true, false 2^2자..
[백준 1956 : JAVA] 운동 / 벨만-포드 개요 알고리즘 문제를 풀 때는 문제를 잘 읽고 어떤 알고리즘을 적용할 수 있을까?를 먼저 생각하는 편이 좋다. 이 문제는 1 ▶ 1, 2 ▶ 2, 3 ▶3 ..... n ▶n 으로 가는 최단거리 중 최솟값을 구하는 문제이다. 시작 노드가 모든 노드에 해당하는 값을 알아야 하기 때문에 다익스트라, 벨만 포드가 아닌 플로이드 와샬을 사용한다. 플로이드 와샬을 통해 모든 노드 ▶ 모든 노드 의 최단거리를 구한 뒤 사이클을 이루는 도로의 길이 중 최솟값을 구한다. 플로이드 와샬이 처음이라면 아래의 문제와 풀이를 먼저 풀고 이 문제를 푸는 것을 추천한다. 아래의 풀이에는 간략한 플로이드 와샬 알고리즘에 대한 설명이 있다. https://www.acmicpc.net/problem/11404 11404번: 플로이드 ..
[백준 10217 : JAVA] KCM Travel / 벨만-포드 개요 문제를 읽어보면 최단 시간을 구하는 문제이면서 동시에 티켓 가격은 조건을 만족해야 한다. 가중치가 1이 아니므로 DFS, BFS가 아닌 다익스트라, 벨만 포드, 플로이드 와샬을 사용해야 한다. 한 노드 ▶ 노드 이므로 다익스트라, 벨만 포드를 사용해야 한다. 음의 가중치는 없기 때문에 다익스트라를 사용해야 한다. 결국 다익스트라를 사용해야 하는데 이 문제는 다익스트라 + dp를 이용해서 풀이한다. 이때 dp[i][j] = k가 있다면, i노드까지 j비용으로 갈 수 있는 최소의 시간 = k 라고 생각하고 풀이에 들어간다. 문제 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민..
[백준 11657 : JAVA] 타임머신 / 벨만-포드 개요 문제를 읽어보면 그래프의 가중치가 음수인 경우가 있고, 한 노드 ▶ 모든 노드의 최단경로를 구하는 것이다. 그리고 음의 사이클이 존재하면 -1을 출력하고 만약 경로가 존재하지 않으면 -1을 출력한다. 위의 조건들을 살펴보면, 가중치가 음수이므로 다익스트라는 사용할 수 없다. 한 노드 ▶ 모든 노드 이므로 플로이드 와샬 말고 벨만 포드이면 충분할 것 같다. 음의 사이클 유무를 확인해야 하므로 벨만 포드이면 충분할 것 같다. 만약 음의 사이클이 무엇인지 헷갈린다면 아래의 문제와 풀이를 먼저 공부하고 이 문제를 푼다면 도움이 될 것이다. https://www.acmicpc.net/problem/1865 1865번: 웜홀 문제 때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 ..
[백준 1865 : JAVA] 웜홀/ 벨만-포드 개요 문제를 읽어보면 음의 가중치가 있는 그래프에서 음의 사이클의 여부를 확인하는 문제라는 것을 알 수 있다. (음의 사이클이란 경로를 지날 때마다 계속 최단거리가 감소하는 것을 뜻한다.) 위와 같은 그래프가 있을 때, 1 ▶ 1 최단거리가 -4 ▶ -8 ▶ - 12 ▶ -16....로 점점 줄어들게 되는데 이러한 경우를 음의 사이클이 있다고 한다.(음의 사이클은 최단거리를 구할 때 가중치에 음수가 있을 때 발생 가능성을 가지고 있다.) 음의 가중치가 있는 경우 다익스트라와 벨만 포드 중 벨만-포드 알고리즘을 선택해야 한다. 또한 벨만 포드 알고리즘은 음의 사이클의 여부를 확인할 수 있다. 문제 때는 2020년, 백준이는 월드나라의 한 국민이다. 월드 나라에는 N개의 지점이 있고 N개의 지점 사이에는 M..

티스토리툴바