본문 바로가기

알고리즘 (2020 : 08 : 10 ~ )/구현, 시뮬

 (65)
[백준 / BOJ] 6503 망가진 키보드 문제 출처 : www.acmicpc.net/problem/6503 6503번: 망가진 키보드 입력은 여러 개의 테스트 케이스로 이루어져 있고, 각 테스트 케이스는 두 줄로 이루어져 있다. 테스트 케이스의 첫째 줄에는 m이 주어진다. (1 ≤ m ≤ 128) 둘째 줄에는 상근이가 입력하려고 하는 www.acmicpc.net 상근이의 키보드가 망가져서, 키보드에서 작동가능한 키가 m개 밖에없다. 상근이가 입력하려는 문자가 주어졌을때, m개의 키를 눌러서 입력할수있는 최대 부분 문자열의 길이를 구하는 문제다. 풀이 예제 출력을보면 This can't be solved by brute force 라고 친절히 적혀있으므로 완전탐색으로는 풀리지않고, (문자열의 갯수가 완탐으로는 못풀만큼 입력되는듯) 다른 방법으로 ..
[백준 / BOJ] 1941 소문난 칠공주 문제 출처 : www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 5*5그리드에 학생들의 파가 주어진다. (이다솜파 : S, 임도연파 : Y) 이다솜은 자신의 파를 늘리기위해 소문난 칠공주를 결성하기로했다. 칠공주가 되기위해선 3가지 조건이 필요한데, 1. 칠공주에 속하는 학생들은 서로 인접해있어야한다. 2. 7명의 학생으로 구성되어야한다. 3. 이다솜파보다 임도연파가 더 많아야한다. 이때, 소문난 칠공주를 결성하는 모든 경우의수를 구하는 문제다. 풀이 푸는데 2일..
[백준 / BOJ] 1644 소수의 연속합 문제 출처 : www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 자연수 N이 주어진다. 연속된 소수들을 더해서 자연수 N을 더하는 경우의수를 구하는 문제다. 풀이 '연속된 소수들을 이용해서 N을 만들어야 한다'는 조건이 있기때문에, 투포인터를 이용해 풀수있다. 소수만을 가지고 N을 만들어야 한다. 매번 해당 숫자가 소수인지 판단하면 너무 오래걸리기 때문에, 에라스토테네스의 체를 이용해 미리 소수들을 구해서 벡터에 넣어줬다. 연속된 소수들의 시작idx와 끝idx를 나타내는 left, right를 선언해줬다. 연속된 소수들의 합 S = (vec[left] + vec[left + 1]..
[백준 / BOJ] 13460 구슬 탈출 2 문제 출처 : www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 보드의 가로, 세로의 길이가 주어지고, 두 구슬 R,B의 위치가 주어진다. 보드를 기울여 구슬을 동서남북으로 움직일수있다. 단, 한번 움직이면, 벽, 다른 구슬, 구멍을 만날때까지 기울인 방향으로 움직여야한다. R구슬만 탈출시키는 최소한의 이동 횟수를 구하면 된다. 풀이 시키는대로 하면되는 구현문제다. BFS알고리즘을 이용해 풀었다. - check..
[백준 / BOJ] 9466 텀 프로젝트 문제 출처 : www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 문제 해결 강의를 신청한 학생들은 텀 프로젝트를 수행해야한다. 각 학생들마다 팀을 하고싶은 학생이 다르고, 한 학생이 한명의 학생만 선택할수있다. 학생들의 팀원선택이 사이클을 이루면 해당 학생들은 팀을 이뤘다고할때, 팀을 이루지못한 학생들의 수를 구하는 문제다. 풀이 학생들의 사이클을 찾으면 되는 문제인데, 시간초과를 조심해야한다. 풀이의 핵심은 한 학생을 기준으로 그룹을 찾을때마다, 해당 그룹안에 포..
[백준 / BOJ] 1806 부분합 문제 출처 : www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 수열의 길이 N과 만들어야할 최소 수 S가 주어진다. 수열의 각 원소들의 합이 S이상이 되는 최소 길이를 구하는 문제다. 풀이 N이 최대 10만까지 가기때문에, 최악의 경우 100001 * 50000번 반복해서 시간초과가 난다. 투포인트로 풀었는데, 수열의 인덱스를 나타내는 변수 p1, p2를 선언한다. p1 ~ p2의 합이 S보다 커질때까지 p2를 증가시킨다. 이때, 합이 S보다 ..
[백준 / BOJ] 8982 수족관 1 문제 출처 : www.acmicpc.net/problem/8982 8982번: 수족관 1 입력의 첫 줄은 수족관의 경계에 있는 꼭짓점의 개수 N(1 ≤ N ≤ 5,000)이 주어진다. N은 짝수이다. 수족관의 경계는 항상 꼭짓점 (0, 0)부터 시작한다. 그리고 마지막 꼭짓점은 (A, 0)의 형태로 끝난 www.acmicpc.net 물이 들어있는 수족관이있다. 수족관의 바닥에 구멍이 뚫려있을때, 각 구멍을통해 빠져나간후 남은 물의 양을 구하는 문제다. 풀이 범위가 크지않아 완전탐색으로도 풀리는 문제다. 각 구멍의 좌표를 기준으로 왼쪽, 오른쪽으로 탐색하며 현재의 높이보다 수족관의 바닥의 높이가 높을경우, 높이를 올려주며 남아있는 물의 양을 구해주면된다. 1. 구멍이 있는 바닥의 x1(시작 x 좌표) 부터..
[백준 / BOJ] 2495 연속구간 문제 출처 : www.acmicpc.net/problem/2495 2495번: 연속구간 여덟 자리의 양의 정수가 주어질 때, 그 안에서 연속하여 같은 숫자가 나오는 것이 없으면 1을 출력하고, 있으면 같은 숫자가 연속해서 나오는 구간 중 가장 긴 것의 길이를 출력하는 프로그램을 www.acmicpc.net 여덟자리 정수가 주어졌을때, 연속해서 나오는 정수들의 최대 갯수를 구하면된다. 풀이 입력받고 연속해서 나오는 정수들의 최대갯수를 구하면 된다. 정수로 입력받고 한자리씩 짤라가며 해도 되지만, String을 사용하면 훨씬 편하게 할수있다. 소스코드 https://github.com/devxb/JJUNalgo/blob/master/2495%20%EC%97%B0%EC%86%8D%EA%B5%AC%EA%B0%8..

티스토리툴바