알고리즘
-
[백준] 5430번 : AC - 자바(JAVA)알고리즘/백준 2022. 8. 11. 00:01
https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문제 해석 두 가지 함수 R(뒤집기)와 D(버리기)가 있습니다. R은 배열에 있는 수의 순서를 뒤집습니다. D는 첫번째 수를 버리는 함수입니다. 첫 번째 줄에는 테스트 케이스의 개수가 주어집니다. (최대 100개) 각 테스트 케이스의 첫째 줄에는 수행할 함수 p 가 주어집니다. (최대 10만 개) 배열에 들어있는 수의 개수 n이 주어집니다. (최대 10만 개) 다음 줄에는 배열의 정보가 주어집니다. 이때 배열이 비어있는데 D를 사용하는 경우에는 에러가 ..
-
[백준] 14889번 : 스타트와 링크 - 자바(JAVA)알고리즘/백준 2022. 8. 9. 00:01
https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제 해석 축구를 하기 위해 모인 사람은 N명이고 N은 짝수입니다. N/2명으로 두 팀을 나누려고 합니다. N=4일때 다음과 같이 시너지를 가집니다. 두 팀의 능력치의 차이를 최소로 하려고 합니다. 문제 풀이전 설계 S(i,j)는 1~100사이의 수 입니다. N은 4이상 20이하의 짝수입니다. 우선 두 그룹으로 나누는 작업을 수행합니다. (1,2) / (3,4) (1,3) / (2,4) (1,4) / (2,3) 이때 ..
-
[백준] 18870번 : 좌표 압축 - 자바(JAVA)알고리즘/백준 2022. 8. 7. 00:01
https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 문제 해석 수직선 위에 N개의 좌표가 존재합니다. 이 좌표들을 압축하려고 합니다. X(i)를 좌표 압축한 결과 X`(i)의 값은 X(i) > X(j)를 만족하는 서로 다른 좌표의 개수와 같아야 합니다. 문제만 보고 이해가 잘 되지 않으면 예제를 보면 이해하기 쉽습니다. 5 2 4 -10 4 -9 -10은 정렬했을 때 0번째 수, -9는 첫번째 수,..
-
[백준] 1865번: 웜홀 - 자바(JAVA)알고리즘/백준 2022. 8. 4. 00:01
https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 문제 해석 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 존재합니다. 도로에는 방향이 없으며 웜홀에는 방향이 존재합니다. 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로입니다. 도착을 하게 되면 시작 했을 때보다 시간이 뒤로 가게 됩니다. 이때 한 지점에서 출발하여 시간여행을 하여 다시 출발하였던 위치로 돌아왔을 때 출발하였을 때 보다 시간이 되돌아가는 경우..
-
[백준] 2447번 : 별 찍기 - 10 - 자바(JAVA)알고리즘/백준 2022. 8. 1. 00:01
https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 문제 해석 재귀함수를 활용하여 별을 찍는 문제 같습니다. 분할정복 느낌으로 사각형 크기가 3인 사각형을 확장해 나가는 것 같습니다. 문제 풀이 전 설계 재귀함수의 반복은 N=3일때까지 반복을 합니다. (가장 작은 단위가 N=3일때 ) 만약 N=9가 들어오게 된다면 위 사각형 그리기, 가운데 공백있는 사각형 그리기, 아래 사각형 그리기로 나뉘어 재귀함수를 호출해야 할 것 ..
-
[백준] 3078번 : 좋은 친구 - 자바(JAVA)알고리즘/백준 2022. 7. 30. 00:01
https://www.acmicpc.net/problem/3078 3078번: 좋은 친구 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다. www.acmicpc.net 문제 해석 모든 학생은 자신과 반 등수의 차이가 K를 넘으면 친구가 아니다. 이때 좋은 친구는 이름의 길이가 같아야 합니다. N명의 학생들의 이름이 성적순으로 주어졌을 때 좋은 친구가 몇 쌍이나 있는지 구하세요 좋은 친구 = 등수의 차이가 K보다 작거나 같으면서 이름의 길이가 같음 문제 풀이 전 설계 우선 N은 최대 30만입니다. 좋은 친구의 문서 쌍을 구해야 합니다. 투 포인..
-
[백준] 16500번 : 문자열 판별 - 자바(Java)알고리즘/백준 2022. 7. 29. 00:01
https://www.acmicpc.net/problem/16500 16500번: 문자열 판별 첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 www.acmicpc.net 문제 해석 알파벳 소문자로 이루어진 문자열 S가 있습니다 알파벳 소문자로 이루어진 단어 A가 있습니다. 이때 A에 포함된 단어목록을 한 개 이상 공백없이 붙여서 만들 수 있는지 없는지 구하는 프로그램을 작성하세요. 문자열 S의 길이는 100이하입니다. A의 개수도 100개이하입니다. 문자열 S : softwarecontest 단어A : software, contest 단어A를..
-
[백준] 20303번 : 할로윈의 양아치 - 자바(JAVA)알고리즘/백준 2022. 7. 27. 00:01
https://www.acmicpc.net/problem/20303 20303번: 할로윈의 양아치 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, www.acmicpc.net 문제 해석 스브러스는 사탕을 뺏으려고 한다. 이때 스브러스는 사탕을 뺏을 때 한 아이의 사탕을 뺏으면 그 아이 친구들의 사탕도 모조리 뺏어버립니다. 이때 K명 이상의 아이들의 뺏지 않으면서 최대로 뺏을 수 있는 사탕의 양을 구하세요 문제 풀이전 설계 거리에 있는 아이들의 수 N = 30,000 아이들의 친구 관계..