문제 https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 풀이 벽을 가장 적게 부수고, 목적지에 도착할때 부순 벽의 개수를 출력하는 문제 BFS를 이용해서 목적지에 도착할 때 visited에 부순 벽의 개수를 저장한다. 만약 다음 이동할 칸의 부순 벽의 횟수가 지금 부순 벽의 횟수보다 큰 경우 이동한다. 도착 지점의 인덱스 값 - 1을 출력하면 문제를 해결할 수 있다. 여담으로 해당 문제는 찾아보니 해결 방법이 여러 개가 있었는데, 첫번째로는 하얀..
문제 https://www.acmicpc.net/problem/12919 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 풀이 주어진 연산으로 S==T를 만들 수 있다면 1을 출력, 그렇지 않다면 0을 출력하는 쉬운 문제 처음엔 주어진 문제대로 코드를 제출해 보았지만(S를 T로 만들기) 시간초과가 발생하였다. 반대의 경우로 T를 S로 만드는 방법을 구현해 보았다. 제출 코드 # 2023/01/30 재귀 # https://www.acmicpc.net/problem/1291..
문제 https://www.acmicpc.net/problem/1938 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 ≤ N ≤ 50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문 www.acmicpc.net 풀이 시작 지점 "B"에서 도착 지점 "E"까지 도착하는데 걸리는 최소 횟수를 출력하는 문제 일단 각 지점의 중간 값을 구한 다음 도착 지점의 값과 시작 지점의 값이 같다면 정답을 출력하면 된다. 아래 기능만 구현할 수 있다면 문제를 해결할 수 있다고 생각한다. 현재 상태에서 이동할 수 있는 곳이 있다면 이동 현재 상태에서 회전할 수 있으면 회전 도착 여부 확인 및 정..
문제 https://www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 풀이 회전 초밥을 먹을 때 종류의 최대값을 구하는 문제 이전에 풀었던 [2531] 회전 초밥 문제(https://simple0710.tistory.com/10)와 같은 맥락이지만, 같은 코드로 제출할 경우 시간초과가 발생한다. 두 포인터와, 슬라이딩 윈도우 알고리즘을 사용한다. k 만큼의 구역을 설정하고 left 와 right 를 한칸씩 이동시키면..
문제 https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 풀이 회전 초밥을 먹을 때 종류의 최대값을 구하는 문제 집합 자료형(set)을 이용하여 중복된 번호가 없는 회전 초밥 데이터를 구하고, 쿠폰 번호에 해당하는 번호가 없는 경우 +1을 수행한 후, res 값과 비교한다. 굉장히 단순하다고 생각되는 풀이지만, k만큼의 리스트를 계속 만들어 내므로 시간 복잡도가 O(n * k) 이다. 이 방법 보다 더 좋은 ..
문제 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 풀이 현재 위치의 오른쪽에서 현재 위치의 수보다 큰 값을 저장하고, 정답을 출력하는 간단해 보이는 문제이다. 풀이 1에서는 이중 반복문 구조(O(N^2))로 인한 시간초과가 발생하였다. 풀이 2는 정답을 담는 배열 res, 인덱스를 담는 배열 check를 이용하였다. 현재 값이 arr[check[-1]]보다 크다면 res[check[-1]]의 값을 현재 값으로 한 후, check에 현재 값의 인덱스를 ..
문제 https://www.acmicpc.net/problem/5635 5635번: 생일 어떤 반에 있는 학생들의 생일이 주어졌을 때, 가장 나이가 적은 사람과 가장 많은 사람을 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 나이가 가장 작은 사람과 나이가 가장 많은 사람의 이름을 출력하는 문제 연, 월, 일, 이름 순으로 데이터를 저장하고 정렬한다. 가장 먼저 태어난 사람이 맨 처음에 있고, 가장 늦게 태어난 사람이 배열 맨 마지막에 있으므로 해당 부분의 이름을 출력한다. 제출 코드 # 2023/01/26 문자열, 정렬 # https://www.acmicpc.net/problem/5635 import sys input = sys.stdin.readline data = [] for _ ..
문제 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 현재 위치가 1인 경우 자신의 왼쪽, 왼쪽 위의 대각선, 위쪽을 확인하고 최소 값을 현재 값과 더한다. 그 후 max값을 계속 저장한 뒤 제곱한 값을 출력한다. 1의 위치에서 정사각형의 크기를 계속 계산하는 경우는 DP를 수행하는 것보다 높은 복잡도를 가질 것이다. 제출 코드 # 2023/01/25 DP # https://www.acmicpc.net/problem/1915 import sys input = sys.stdin.readline N, M = ma..
