본문 바로가기

알고리즘

 (100)
백준 17071 숨바꼭질 5(java) https://www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 � www.acmicpc.net 대망의 숨바꼭질 마지막 문제다 . 조금의 센스가 필요한.... 구현문제 핵심은 홀수 초의 최적거리와 짝수 초의 최적거리를 나누는 것! import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWr..
백준 14442 벽 부수고 이동하기(Java) https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 가중치 없는 최단거리 문제는 거의 무조건 BFS이다. 그리고 이 문제를 풀 때 주의할 점은, '벽'이라는 변수가 있기 때문에 방문 체크를 잘 해야한다는 것이다. 벽을 부수면서 빠르게 도착점에 근접했더라도, 이미 벽을 부술 수 있는 기회를 다 써버렸다면 도착점에 도달할 수 없다. 만약 단순 2차원 배열로 매 순간 방문 체크를 True로 했다면, 벽을 부술 수 있는..
백준 2150 Strongly Connected Component(java) https://www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net SCC 알고리즘을 연습하는 문제 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.lang.reflect.Array; imp..
백준 1781 컵라면(java) https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라� www.acmicpc.net 처음엔 부분합을 최대로 하는 문제라고 생각했지만 lowebound를 구하는 과정에서 그게 아니라는 걸 알게됐다. 데드라인 기준으로 오름차순 정렬을 한다. 차례대로 우선순위 큐에 라면을 넣으면서, 개수가 데드라인을 넘어가면 제일 라면이 적은 것부터 빼낸다. 데드라인은 배열의 크기로 볼 수 있다. 만약 어떤 한 과제의 데드라인이 3이라면 배열에서 0~2까지 인덱스에 들어갈 수 있다. 꼭 2에 들어갈 필요가 ..
백준 4179 불!(java) https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문� www.acmicpc.net 자바로 연습하는 중인데 참으로 코드가 길다 ^_^... 그냥 구현하는 문제다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.LinkedList; import jav..
백준 17822 : 원판돌리기(java) https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 로직 구성은 예전에 끝냈는데, java가 익숙치않아서 한참걸렸다... 단순 구현문제! import java.io.*; import java.util.*; class Pair { int x, d, k; Pair(int a, int b, int c) { x = a; d = b; k = c; } } public class boj17822 { static BufferedReader br ..
백준 1275 커피숍2 https://www.acmicpc.net/problem/1275 1275번: 커피숍2 첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합� www.acmicpc.net 반복문을 이용한 세그먼트 트리다. 대놓고 세그트리 쓰라는 문제라서 당황 /* 커피숍2 */ #include #include #include #define ll long long int #define iNF 2100000000 using namespace std; void seg_init(); ll seg_find(int l, int r); void seg_updat..
백준 2610 회의준비 https://www.acmicpc.net/problem/2610 2610번: 회의준비 첫째 중에 회의에 참석하는 사람의 수 N이 주어진다. 참석자들은 1부터 N까지의 자연수로 표현되며 회의에 참석하는 인원은 100 이하이다. 둘째 줄에는 서로 알고 있는 관계의 수 M이 주어진다. 이 www.acmicpc.net 플로이드 워셜 알고리즘과 약간의 구현이 필요한 문제이다. floyd에서 dp를 구하고 이를 활용해서 각 그룹의 대표와 그 그룹의 최대값이자 최솟값(?)을 구했다. /* 회의준비 */ #include #include #include #include #define ll long long int #define pp pair #define INF 2100000000 using namespace std;..
백준 11657 /* 타임머신 */ #include #include #include #define INF 2100000000 #define ll long long int #define pp pair using namespace std; void input(); void solve(); struct line { int src, dst, wgt; line(int a, int b, int c) { src = a; dst = b; wgt = c; } }; int N, M; ll dist[501]; vector edge; int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); input(); solve(); return 0; } void ..
백준 1865 웜홀 https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), � www.acmicpc.net 벨만 포드 알고리즘을 이용하는 문제다. 이 문제를 풀면서 배운점은 문제의식을 명확히 하라는 점이다. 벨만 포드는 다익스트라 알고리즘보다 시간복잡도(O(V*E) vs O(ElogE))가 크기 때문에 잘 사용하지 않는다. 하지만 다익스트라 알고리즘보다 정확해서 음의 가중치가 섞인 경로에서 최적 경로를 찾아낼 수 있고 음의 사이클의 유무도 파악할 수 있다. 결국은 Shortes Path..

티스토리툴바