Algorithm/BOJ

2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 문제를 처음 봤을 때 이해가 가지 않아서 정리했습니다. 문제 설명을 왜 이렇게 했을까 😞😞 문제 이해하기 회장은 점수가 가장 적은 사람이 됩니다. 점수 계산 방법은 다음과 같습니다. 1점 : A회원이 B회원과 친구 관계 (A-B) 2점 : A회원이 B회원과 친구 관계이면서, B회원의 친구인 C회원과도 친구 관계 (A-B-C) 3점 : A회원이 B회원과 친구 관계이면서, B회원의 친구인 C회원과도 친구 관계이면서, C회원의 친구인 D회원과도 친구 관계 (A-B-C..

2016번: 미팅 주선하기 태현이는 네 명의 친구와 5대 5 미팅에 참여하게 되었다. 미팅 자리에서 각 사람의 소개가 끝나고, 각자의 짝을 정할 시간이 되었는데, 태현이가 다음과 같은 방법을 제안하였고, 모두 이에 찬성 www.acmicpc.net 문제 미팅 자리에서 각자의 짝을 정하는 방법은 다음과 같습니다. 태현이가 1번, 나머지 남학생이 2-5번, 여학생이 6-10번입니다. 각자 상대에 대한 선호도 순위를 매겨서 씁니다. 이때, 두 명 이상의 상대에게 같은 선호도를 적용하면 안 되고, 5명 모두에 대한 순위를 매겨야 합니다. 6번 여학생부터 가장 좋아하는 남학생에게 프러포즈를 하며, 퇴자 맞으면 다음 순서의 남학생에게 프러포즈를 합니다. 남학생은 현재 짝이 없으면 무조건 프러포즈를 받으며, 두 명 ..

2615번: 오목 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호 www.acmicpc.net 바둑판에 19개의 가로줄과 19개의 세로줄이 그려져 있을 때, 같은 색의 바둑알이 연속적으로 다섯 알 놓이면 이기게 되는 게임입니다. 여기서 연속적으로는 가로, 세로 또는 대각선 방향을 뜻하며, 여섯 알 이상이 연속적으로 놓은 경우에는 이긴 것이 아닙니다. 바둑판 상태가 주어졌을 때, 검은색은 1, 흰색은 2, 알이 놓이지 않은 자리는 0으로 표시합니다. 검은색이 이기면 1, 흰색이 이기면 2, 아직 승부가 결정되지 않으면 0을 출력합니다. 그리고 검은색 또는..

1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 이 문제는 주어진 C개의 문자를 L 길이의 암호로 만드는 문제이며, 암호는 최소 한 개의 모음과 최소 두 개의 자음을 포함한 정렬된 형태로 만들어야 합니다. 브루트포스를 이용해서 풀면 되는 문제라 편안한 마음으로 풀었네요 😎😎 import java.io.*; import java.util.Arrays; import java.util.StringTokenizer; class Main { static BufferedReader br = new BufferedReader(..

import java.io.*; import java.util.*; public class Main { public static String strReverse(ArrayDeque deque, boolean isReverse) { String temp = ""; while(!deque.isEmpty()) { if (isReverse) { // 뒤집어진 상태 temp += deque.pollLast(); } else { temp += deque.pollFirst(); } } return temp; } public static String strRemove(String s, String t) { int sLen = s.length(); int tLen = t.length(); int count = tLen ..

10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 이 문제에서는 N개의 물건, M 개의 물건쌍이 주어지며, 물건 i와 비교 결과를 알 수 없는 물건 수를 출력하는 문제입니다. 해당 문제를 풀기 위해서는 플로이드-워셜(Floyd-Warshall) 알고리즘을 적용해야 합니다. 플로이드-워셜은 모든 정점에서 모든 정점으로의 최단 거리를 구하는 알고리즘으로, 거쳐가는 정점을 기준으로 알고리즘을 수행합니다. 그리고 반복문 3개가 중첩되어 있는데, 제일 바깥쪽 반복문은 거쳐가는 꼭짓점, 두 번째 반..

1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 이 문제는 사람 수 N, 파티 수 M, 진실을 아는 사람 수와 번호, M개 파티에 오는 사람 수와 번호가 입력값으로 주어집니다. 그리고 지민이가 거짓말쟁이로 알려지지 않으면서 과장된 이야기를 할 수 있는 파티 수의 최댓값을 출력하면 됩니다. 저는 이 문제를 다음과 같은 방법으로 풀었습니다. 진실을 아는 사람, 각 파티별 참가자, 모든 사람의 파티 참가에 대한 기록을 만들었습니다. bfs 수행을 위해 사람 확인 여부를 기록할 배열을 하나 생성한 후, Queue에 진실을 아는..

5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 이 문제에서는 테스트케이스 T, 수행할 함수 p, 배열 길이 n, 숫자가 들어간 배열이 입력으로 주어집니다. p는 'RDD'와 같은 형태로 주어지는데, 여기서 R은 배열 순서를 뒤집고, D는 첫 번째 숫자를 버립니다. 배열이 비어있는데 D를 사용한 경우 에러가 발생합니다. 주어진 정수 배열에 함수 수행 결과를 출력하면 되는데, 에러 발생 시 error를 출력합니다. 모든 R에 대해서 배열을 뒤집어가며 수행을 하는 경우 시간초과가 발생하게 됩니다. 시간초과가 발생하지 않게 하려면, R의 상태에 따라 D의 수행 위치를 바..

5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 이 문제는 한 번호가 다른 번호의 접두어로 사용되는지 확인하고, 하나라도 접두어로 사용된 경우 NO를 출력하고, 그렇지 않은 경우 YES를 출력하는 문제입니다. 입력받은 전화번호를 정렬한 후 현재 위치의 번호가 다음 위치의 번호의 접두어로 속하는지 startWith()을 통해 확인합니다. 이때, 두 전화번호가 같은 경우는 없으므로 두 번호의 길이가 같을 경우 확인할 필요가 없습니다. import java.io.*; import java.u..

11720번: 숫자의 합 첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다. www.acmicpc.net 숫자의 개수 N이 주어지고, 숫자 N개가 공백 없이 주어질 때 이 숫자들의 합에 대해서 출력하는 문제입니다. 전제 문자에서 index 자리 순으로 문자를 가져온 후 answer 변수에 더합니다. 이때, answer이 Int 형이기 때문에 아스키코드 값이 더해집니다. 올바른 값을 얻기 위해서는 얻어낸 문자를 '0' 으로 빼야 합니다. (문자 아스키코드 - 문자 0의 아스키코드) 모든 문자에 대해 더한 후 answer을 출력하면 됩니다. import java.util.Scanner; public class Main { public static voi..

15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 드래곤 커브는 x = 행, y = 열, d = 방향, g = 세대로 이루어져있습니다. 0세대는 길이가 1인 선분이고, 1세대는 0세대를 시게방향으로 90도 돌려서 끝점에 붙인 형태입니다. 이런 식으로 g세대는 (g-1)세대를 시계방향으로 90도 돌린 후 끝점에 붙이며 진행됩니다. 즉, g세대를 알려면 그 전 세대에 대해 거꾸로 이어붙인 형태입니다. 방향은 다음과 같이 주어집니다. 0: x좌표가 증가하는 방향 (→) 1: y좌표가 감소하는..

17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 이 문제는 NxM 크기의 배열 A가 주어지며, 배열 A의 값은 각 행의 합 중 최솟값을 나타냅니다. 배열 회전 연산은 (r, c, s)로 이루어져있는데, r행 c열을 둘러싼 정사각형을 시계방향으로 돌립니다. 여기서 정사각형은 가장 왼쪽 윗칸이 r-s행, c-s열, 가장 오른쪽 아랫칸이 r+s행, c+s행인 정사각형입니다. 만약, s가 2일 경우 가장 왼족 윗칸이 r-s+1행, c-s+1열, 가장 오른쪽 아랫칸이 r+s-1행, c+s-..