목록Algorithm (26)
-
문제 https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 풀이 방법 s → t 를 만드는 것은 경우의 수가 너무 많기 때문에 시간 복잡도 측면에서 비효율적이다. 따라서 t → s 를 만드는 것이 낫다. 기존 방법 문자열의 뒤에 A를 추가한다. 문자열을 뒤집고 뒤에 B를 추가한다. 반대 방법 문자열의 끝에 있는 A를 제거한다. 문자열 끝에 있는 B를 제거하고 문자열을 뒤집는다. 만약 t → s 변환이 성공하면 1..
문제 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 풀이 방법 외부 공기와 두 칸 이상 맞닿으면 다음 턴에 치즈가 녹지만, 내부 공기와 맞닿으면 녹지 않는다. 따라서 기존에 0이었던 외부 공기를 모두 2로 바꿔주는 작업이 필요하다. 외부 공기를 모두 2로 바꿔주었으면, 두 칸 이상의 외부 공기와 맞닿은 치즈를 체크해서 2로 바꿔준다. (녹은 것) 반복한다. 코드 import sys sys.setrecursionlimit(10**6..
문제 https://www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 www.acmicpc.net 풀이 input이 아래와 같다면, [0][2], [0][4], [2][2], [2][4]를 꼭짓점으로 하는 정사각형이 넓이가 최대가 되는 정사각형이다. 3 5 42101 22100 22101 우리는 넓이가 최대가 되는 정사각형을 찾는게 목적이므로, for문을 돌 때 최대 크기부터 하나씩 줄여가며 시작한다. 네 꼭짓점이 같으면 True를 리턴하고, 그 때의 변 길이를 제곱하여 넓이를 구한다. ..
from collections import deque n = int(input()) game = [[0]*n for _ in range(n)] k = int(input()) for i in range(k): x, y = map(int, input().split()) game[x-1][y-1] = 2 l = int(input()) queue = deque() dirDict = dict() queue.append((0, 0)) dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] for _ in range(l): x, c = input().split() dirDict[int(x)] = c x, y = 0, 0 game[x][y] = 1 cnt = 0 direction = 0 def turn(a..
문제 https://www.acmicpc.net/problem/1347 코드 n = int(input()) cmd = input() dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1] V = [['#' for j in range(101)] for i in range(101)] x, y, d = 50, 50, 2 ex = ey = sy = sx = 50 V[x][y] = '.' for i in cmd: if(i == 'L'): d = (d+3) % 4 elif(i == 'R'): d = (d+1) % 4 else: x = x + dx[d] y = y + dy[d] V[x][y] = '.' sy, ey, sx, ex = min(sy, y), max(ey, y), min(sx, x), max(..
소수를 찾는 알고리즘이다. 방법은 다음과 같다. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색) 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색) 자기 자신을 제외한 3의 배수를 모두 지운다. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색) 자기 자신을 제외한 5의 배수를 모두 지운다. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색) 자기 자신을 제외한 7의 배수를 모두 지운다. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다. 파이썬 코드로 구현 def prime_list(n): #..
문제 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 풀이 m, n = map(int, input().split()) for i in range(m, n+1): if i == 1: continue # 소수가 아닌 경우 for문 종료 for j in range(2, int(i ** 0.5) + 1): if(i%j == 0): break else: print(i) 1. i가 1인 경우는 소수가 아니므로 제외한다. 2. 임의의 수 i의 최대 약수가 sqrt(i) 이하이므로 i**0..
문제 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이 n = int(input()) cards = list(map(int, input().split())) m = int(input()) numbers = list(map(int, input().split())) count = {} for i in cards: if i in count: count[i] += 1 else: count[i] = 1 for i i..