본문 바로가기

알고리즘

백준 2458 키 순서 https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 키를 비교한 결과가 주어졌을 때 자신의 키가 몇번째인지 알수있는 학생이 몇명인지 알아내자. 키를 비교한 결과를 그래프로 나타내면 다음과 같다. 자신이 몇번쨰인지 알기 위해서는 1. 다른 점에서 자기를 방문할수 있다. 2. 자기가 다른 점을 방문 할수 있다. 가 모든 점에 대해 만족 되야한다. 위의 그림에서 4번은 2,6번을 방문 할수있고, 1 3 5는 4를 방문할수 있으므로 4번은 자신의 순서를 알.. 더보기
백준 1766 문제집 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net N개의 문제는 모두 풀어야 한다. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다. 가능하면 쉬운 문제부터 풀어야 한다. (1이 가장 쉽고 N이 가장 어렵다) 내가 어떤 한 문제를 풀기 위해서는 그 문제로 들어오는 노드들 또한 풀어야만 가능하다. 즉 부모노드가 0개여야 가능하다는 뜻이다. 부모노드가 0개인 노드들을 배열.. 더보기
백준 7571 점모으기 https://www.acmicpc.net/problem/7571 7571번: 점 모으기 첫 줄에는 격자공간의 크기와 점들의 개수를 나타내는 두 정수 N과 M이 하나의 공백을 사이에 두고 주어진다. 다음의 M줄에는 각 줄마다 격자공간내의 점의 위치를 나타내는 두 개의 정수가 하나 www.acmicpc.net 위와 같이 위치된 점들을 하나의 점으로 모았을때 최소거리를 구하는 문제다. 점들의 x좌표, y좌표를 각각 xx , yy라는 배열에 저장하고 이점들을 모두 (p,q) 라는 점에 모았을때 거리 D(p,q)를 계산한다고 생각해보면 D(p,q) = |xx[0] - p| + |xx[1] -p| + .... |xx[n-1] -p| + |yy[0] -q| + |yy[1] -q| + |yy[2]-q| + .... .. 더보기
백준 16228 GCC의 유산 https://www.acmicpc.net/problem/16228 더보기
백준 15927 회문은 회문아니야!! https://www.acmicpc.net/problem/15927 15927번: 회문은 회문아니야!! 팰린드롬이란 앞으로 읽으나 뒤로 읽으나 같은 문자열을 말한다. 팰린드롬의 예시로 POP, ABBA 등이 있고, 팰린드롬이 아닌 것의 예시로 ABCA, PALINDROME 등이 있다. 같은 의미를 가지는 여러 단어들을 보자. 회문 (한국어) palindrome (영어, 프랑스어, 노르웨이어, 그리스어, 라틴어) 回文 (일본어, 중국어) palindrom (독일어, 덴마크어) palindromi (핀란드어) palíndromo (스페인어, 포르투갈어) pal www.acmicpc.net 입력 받은 문자열중에서 가장 긴 부분문자열을 구하는 문제이다. DP문제인줄 알았지만 도무지 점화식이 생각 안 나서 다르게.. 더보기
백준 13907 세금 https://www.acmicpc.net/problem/13907 13907번: 세금 첫 번째 줄에 세 정수 N (2 ≤ N ≤ 1,000), M (1 ≤ M ≤ 30,000), K (0 ≤ K ≤ 30,000)가 주어진다. 각각 도시의 수, 도로의 수, 세금 인상 횟수를 의미한다. 두 번째 줄에는 두 정수 S와 D (1 ≤ S, D ≤ N, S ≠ D www.acmicpc.net 주언이는 경제학을 배워 행상인이 되었다. 두 도시를 오가며 장사를 하는데, 통행료의 합이 가장 적은 경로로 이동하려 한다. 도시들은 양방향 도로로 연결되어있으며, 도로마다 통행료가 존재한다. 그런데 정부는 세금 인상안을 발표하였다. 세금을 한 번에 올리면 문제가 발생할 수 있으므로 여러 단계에 걸쳐서 올린다고 한다. 세금이 .. 더보기
백준 문자열제곱 4354 https://www.acmicpc.net/problem/4354 4354번: 문자열 제곱 문제 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다면, 음이 아닌 정수의 제곱도 정의할 수 있다. a^0 = "" (빈 문자열) a^(n+1) = a*(a^n) 문자열 s가 주어졌을 때, 어떤 문자열 a에 대해서 s=a^n을 만족하는 가장 큰 n을 찾는 프로그램을 작성하시오. www.acmicpc.net KMP 알고리즘에서 사용되는 prefix 테이블을 이용하여 풀 수 있는 문제다. prefix테이블이란 문자열의 접두어(prefix)와.. 더보기
SWEA [모의 SW 역량테스트] 등산로 조성 package swea; import java.util.*; import java.io.*; public class 등산로조성 { public static class MyScanner { BufferedReader bf; StringTokenizer st; MyScanner() { bf = new BufferedReader(new InputStreamReader(System.in)); } String next() { while (st == null || !st.hasMoreTokens()) { try { st = new StringTokenizer(bf.readLine()); } catch (Exception e) { e.printStackTrace(); } } return st.nextToken(); .. 더보기

티스토리툴바