본문 바로가기

전체보기

 (168)
백준 1958 LCS 3 https://www.acmicpc.net/problem/1958 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. (각 문자열의 길이는 100보다 작거나 같다) www.acmicpc.net 삼중배열을 이용한 LCS 문제 요구하는 알고리즘이 선명한 문제는 상대적으로 쉬운 것 같다. import java.io.*; public class Main { static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static BufferedReader br = new BufferedReader(new InputStreamReader(System.i..
백준 14444, 13275 가장 긴 팰린드롬 부분 문자열 https://www.acmicpc.net/problem/14444 14444번: 가장 긴 팰린드롬 부분 문자열 알파벳 소문자로만 이루어진 문자열 S가 주어졌을 때, S의 부분 문자열 중에서 팰린드롬 이면서 길이가 가장 긴 것의 길이를 구하는 프로그램을 작성하시오. www.acmicpc.net https://www.acmicpc.net/problem/13275 13275번: 가장 긴 팰린드롬 부분 문자열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있으며 길이는 1보다 크거나 같고, 100,000보다 작거나 같다. www.acmicpc.net 두 개가 같은 문제다. 자바로 풀면 시간초과뜬다. 마나허 알고리즘을 사용하는 '전형적인' 문제다. /* 가장 긴 팰린드롬 부분 문자열 */ #..
백준 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;..

티스토리툴바