본문 바로가기

알고리즘 (2020 : 08 : 10 ~ )

 (260)
[백준 / BOJ] 12904 A와 B 문제 출처 : https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 문자 'A'와 'B'가 주어진다. 두 문자를 아래와 같은 규칙으로 연결해 문자열 T를 만든다. 1. 문자열 뒤에 A를 붙인다. 2. 문자열 을 뒤집고 뒤에 B를 붙인다. 이때, 문자열 S를 이용해 문자열 T를 만들 수 있는지 알아내는 프로그램을 만드는 문제다. 풀이 아이디어 문제다. 문자열 S를 이용해 문자열 T를 만들려면, 매 선택마다 2가지 ..
[백준 / BOJ] 17363 우유가 넘어지면? 문제 출처 : https://www.acmicpc.net/problem/17363 17363번: 우유가 넘어지면? 첫 줄에 그림의 세로 길이와 가로 길이를 의미하는 정수 N과 M(1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에 걸쳐 그림의 각 줄을 의미하는 M글자의 문자열이 하나씩 주어진다. 문자열은 공백을 포 www.acmicpc.net 입력된 N*M배열을 왼쪽으로 90도 회전한 결과를 출력하는 문제다. 풀이 문제에서 하란대로 구현하면 되는 간단한 문제다. 입력받은 문자를 왼쪽으로 90도 회전한 값을 HashMap에 저장해 놓고 HashMap에 저장된 값과 매치해서 출력하면된다. 주요 소스코드 private void init(){ dic.put('.','.'); dic.put('O','O')..
[백준 / BOJ] 17383 옥토끼는 통신교육을 풀어라!! 문제 출처 : https://www.acmicpc.net/problem/17383 17383번: 옥토끼는 통신교육을 풀어라!! 옥토끼가 이런 식으로 문제를 풀면 tncks0121은 옥토끼가 5, 10, 15, 20, 25, 30, 34분에 문제를 풀었으므로 최대 5분동안 휴식을 한 것으로 간주한다. www.acmicpc.net 옥토끼는 두개의 문제를 한번에 풀수있다. N개의 문제가 주어질때, 문제를 푸는 시간사이의 공백을 최소화하는 시간을 구하는 문제다. 풀이 결정문제로 풀은 문제였다. Ni가 최대 10억이고, 완전탐색으로 풀경우, 최소 max(Ni)*(a), (a>N)시간복잡도가 나와서, 항상 시간초과가 나온다. 위의 식 N*(a)의 시간을 줄이는 방법은 다음과 같다. 1. N N이 의미하는것은, 모든..
[백준 / BOJ] 17374 비트베리 문제 출처 : https://www.acmicpc.net/problem/17374 17374번: 비트베리 비트베리는 국내 최다 사용자를 확보하고 있는 간편암호화폐 지갑이다. 비트베리의 가장 큰 특징 중 하나는 카카오 계정으로 지갑을 만들고, 전화번호로 암호화폐를 주고받을 수 있는 점이다. www.acmicpc.net 페카즈는 자신이 갖고있는 비트코인의 수를 최대로 하고싶다. 페카즈와 빈센트가 할 수 있는 거래가 주어질때, 최대 비트코인수를 구하는 문제다. 풀이 이분탐색으로 푼 문제다. 할수있는 거래그래프는 아래와 같은데, 아래를 보면 베리를 코인으로 최대로 바꾸는것이 항상 최선임을 알수있다. 비트 -> 코인 코인 -> 비트 베리 -> 코인 코인 -> 베리 베리 -> 코인 -> 비트 얻을 수 있는 비트코인..
[백준 / BOJ] 21319 챔피언(Easy) 문제 출처 : https://www.acmicpc.net/problem/21319 21319번: 챔피언 (Easy) 1번 선수는 어떻게 해도 챔피언이 될 수 없다. 2번 선수는 어떻게 해도 챔피언이 될 수 없다. 3번 선수는 (2, 3), (1, 3), (3, 4) 순서대로 격투가 일어나면 챔피언이 될 수 있다. 4번 선수는 (3, 4), (2, 4), www.acmicpc.net N명의 선수가 비 내림차순으로 주어진다. 각 선수는 자신의 양쪽선수와 경기를 하며 파워가 더 쌘 선수가 승리한다. 승리시 자신의 파워가 +1 증가하며, 패배한 선수의 양쪽 선수와 연결된다. 위 과정을 반복후, 경기장에 혼자 남아있을때, 그 선수를 챔피언 이라고 한다. 이때, 챔피언이 될 가능성이 있는 선수를 모두 구하는 문제다..
[백준 / BOJ] 19538 루머 문제 출처 : https://www.acmicpc.net/problem/19538 19538번: 루머 예제 1 0분 : 최초 유포자($1$, $6$번 사람)가 루머를 생성한다. 1분 : $1$번 사람은 $2$, $3$번 사람에게 루머를 퍼뜨린다. $2$번 사람은 주변인 $2$명 중 $1$명이 루머를 믿고 있어 루머를 믿게 된다. $3$ www.acmicpc.net N명이 사람이 있다. 이 N명의 사람은 어떠한 루머를 자신과 연관된 주변인중 절반이상이 믿는다면 자신또한 그 루머 믿는다. 이때, 모든 사람이 루머를 믿기위해서 걸리는 시간을 구하는 프로그램을 구하는 문제다. 충분히 많은 시간이 지나도 루머를 믿지 않을 경우 -1을 출력하면된다. 소스코드 기본적인 다익스트라 문제였다. 각 사람이 루머를 믿기시작..
[백준 / BOJ] 19542 전단지 돌리기 문제 출처 : https://www.acmicpc.net/problem/19542 19542번: 전단지 돌리기 현민이는 트리 모양의 길 위에서 오토바이를 타고 전단지를 돌리려고 한다. 현민이의 목표는 케니소프트에서 출발하여 모든 노드에 전단지를 돌리고, 다시 케니소프트로 돌아오는 것이다. 현민 www.acmicpc.net 현민이는 트리 모양의 길 위에서 오토바이를 타고 전단지를 돌리려고 한다. 현민이는 KENNYSOFT위치에서 시작하여 전단지를 다 돌리고 KENNYSOFT로 돌아오며, 이때, 전단지를 던져 거리가 D미만인 노드에 전단지를 한번에 돌릴 수 있다. 현민이가 전단지를 모든 노드에 돌리고 KENNYSOFT로 돌아오는 최단 경로를 구하는 문제다. 풀이 트리탐색으로 풀리는 문제였다. 1년전에 풀려고..
[백준 / BOJ] 15900 나무 탈출 문제 출처 : https://www.acmicpc.net/problem/15900 15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게 www.acmicpc.net 트리의 정점의 개수 N, N-1개의 줄에 거쳐 간선의 정보가 주어진다. 각 간선의 끝(리프노드)에 게임 말이 존재한다. 성원이와 형석이는 이 게임 말을 한턴에 한번씩 부모노드로 움직이는 방식으로 게임을 진행하려고한다. 게임 말은 루트노드에 도착하면 사라지며, 이 과정을 반복하다 자신의 턴에 더 이상 고를수있는 게임 말이 없다면, 그 사람은 게임에서 패배한다. 항상 성원이가 먼저 시작..

티스토리툴바