alpyrithm_알파이리즘

1915 가장 큰 정사각형 www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 문제 풀기 전 공부할 것 : 다이나믹 프로그래밍 풀이 배열을 입력받는다. 이중 for문을 돌면서 (i, j)가 1이 아니라면 정사각형을 만들 수 없다. 1이라면 (i-1, j), (i, j-1), (i-1, j-1)에서 만들 수 있는 정사각형의 변의 최대 길이 중 최솟값 + 1의 크기로 만들 수 있다. import sys input = sys.stdin.readline n, m = map(int, input().split()) board = [list(m..

3190 뱀 www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제 풀기 전 공부할 것 : 구현, 자료 구조, 시뮬레이션, 덱, 큐 풀이 n X n 크기의 maps를 0으로 초기화한다. 사과가 있는 곳을 1로 표시한다. 현재 방향에 따라, D, L에 따라서 움직임을 다르게 하기 사과를 먹었을 때는 꼬리가 늘어난 채 유지 사과를 먹지 못했을 때, 꼬리를 줄이고 몸의 길이는 그래도 꼬리 정보를 가지고 있는 deque를 만든다. 자신의 몸과 부딪히거나 벽과 부딪히면 게임을..

1254 팰린드롬 만들기 www.acmicpc.net/problem/1254 1254번: 팰린드롬 만들기 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. 동호는 � www.acmicpc.net 문제 풀기 전 공부할 것 : 브루트포스 알고리즘 풀이 문자열 S를 전체, 앞에서 1개 뺀 문자열, 앞에서 2개 뺀 문자열, .... 차례대로 팰린드롬인지 확인하고 만약에 팰린드롬이면 제외한 수만큼 문자를 뒤에 더하면 팰린드롬이 된다. s = input() n = len(s) for i in range(n): if s[i:] == s[i:][::-1]: print(n+i) break

1916 최소비용 구하기 www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 풀기 전 공부할 것 : 다익스트라 풀이 1 우선순위 큐를 이용해서 다익스트라로 문제를 해결한다. import heapq import sys input = sys.stdin.readline INF = 999999999 n = int(input()) m = int(input()) bus = [[] for _ in range(n)] for _ in ra..

14503 로봇 www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 문제 풀기 전 공부할 것 : 구현, 시뮬레이션 풀이 1 로봇 청소기 작동을 하나하나 다 구현해보기 먼저 왼쪽 방향부터 탐색하고, 한 칸 전진하는 direction 함수를 만든다. 현재 바라보고 있는 방향을 가준으로 왼쪽 방향과 좌표를 return 한다. 네 방향 모두 청소가 이미 되어있거나 벽인 경우 후진하는 back 함수를 만든다. 현재 바라보고 있는 방향을 기준으로 현재 방향과 후진한 좌표..

2458 키 순서 www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 문제 풀기 전 공부할 것 : 그래프 탐색, 깊이 우선 탐색, 플로이드-와샬 풀이 학생들의 키를 비교한 결과를 저장한다. 학생들의 키를 비교할 수 있는지 확인하는 check를 초기화한다. 1번 학생부터 dfs 함수를 돌면서 만약에 1번 학생보다 5번 학생이 작다면 1번과 5번, 5번과 1번 둘 다 비교할 수 있으므로 check에 저장한다. check를 돌면서 모든 학생들과 비교할 수 있어 자신의 ..

2638 치즈 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 문제 풀기 전 공부할 것 : 구현, 그래프 탐색, 너비 우선 탐색, 시뮬레이션 풀이 n, m과 모눈종이 위의 치즈를 입력받는다. 치즈가 모두 녹아 없어졌는지 확인하기 위한 check 함수를 만든다. 이중 for문을 통해 치즈가 있다면 False를 return 치즈가 없다면 True를 return 치즈의 4변 중에서 적어도 2변 이상 실내온도의 공기와 접촉해야 치즈가 녹아 없..

12851 숨바꼭질 2 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 � www.acmicpc.net 문제 풀기 전 공부할 것 : 그래프 탐색, 너비 우선 탐색 풀이 수빈이(n)와 동생(k)의 위치를 입력받는다. 수빈이가 동생보다 오른쪽에 위치한다면(n >= k) -1을 수빈이와 동생의 위치 차이만큼 가는 방법 한 가지만 있다. 수빈이가 동생보다 왼쪽에 위치한다면 모든 경우를 따져봐야 한다. check를 통해 수빈이가 각각 위치에 몇..