Algorithm Study
[백준 파이썬] #4396 지뢰 찾기
풀기 전 생각해보기😮 지뢰가 있을 경우 모든 지뢰의 위치 표시 이차원 배열의 방향 탐색 풀이🛫 N = int(input()) mine = [list(input()) for i in range(N)]# 지뢰의 위치 open = [list(input()) for i in range(N)]# 지뢰가 있는지 확인한 위치 zone = [[0 for i in range(N)] for j in range(N)]# 플레이어가 보는 위치 # U UR R DR D DL L UL dcol = [1, 1, 0, -1, -1, -1, 0, 1] drow = [0, 1, 1, 1, 0, -1, -1, -1] for col in range(N): for row in range(N): # 지뢰가 있는 곳 주위의 값 표시 if min..
[파이썬] 시프트 연산자 이용
※ 일반적으로 시프트 연산자를 이용해 구한 값은 일반적인 수식을 이용해 계산한 값보다 빠르게 처리된다 (기계어) 홀수 / 짝수 판별 if 10 & 1: # 홀수 pass else: # 짝수 pass 10은 이진법에서 1010, 1은 이진법에서 000 & 연산으로 묶여있기 때문에 위 코드는 False가 도출된다 True일 경우 홀수, False일 경우 짝수이므로 결과값은 짝수이다 → 10에 다른 값을 넣어주어서 홀수/짝수 판별에 이용할 수 있다 정수형의 2의 제곱, 2의 제곱근 # 2의 n제곱 print(10n) 10 * 2^n과 같은 연산이 수행된다. 만약 10
[알고리즘] 문자열 패턴 매칭
패턴 매칭에 사용되는 알고리즘 고지식한 패턴 검색 알고리즘(=Brute Force) 카프-라빈 알고리즘 KMP 알고리즘 보이어-무어 알고리즘 고지식한 패턴 검색 (Brute Force) 문자열을 처음부터 끝까지 차례대로 순회, 패턴 내의 문자들을 일일이 비교 텍스트에서 패턴이 존재하는 모든 위치를 찾는 문제 시간복잡도 : O(MN) M: 패턴의 길이, N: 텍스트의 길이 최악의 경우 텍스트의 모든 위치에 대해 패턴을 비교해야 함 패턴 매칭 알고리즘의 중요 포인트 일치하는 경우 ( t[i] == p[j] ) i, j를 증가시켜서 다음 문자를 비교 불일치하는 경우 다음 매칭의 시작위치로 i, j 값을 설정 ※ 자주 사용되는 대치어 텍스트 패턴 기본 t p 인덱스 i j 길이 m n KMP 알고리즘 불일치가 ..
[Algorithm Study] 파이썬 부분집합 구하기 예시
반복문을 이용해 부분집합 구하기 arr = list(map(int, input().split())) subsets = [[]] for i in arr: L = len(subsets) for l in range(L): subsets.append(subsets[l] + [i]) print(subsets) 비트연산자를 이용해서 부분집합 구하기 arr = list(map(int, input().split())) n = len(arr) for i in range(1
[백준 파이썬] #2804 크로스워드 만들기
풀기 전 생각해보기😮 이차원 배열을 생성할 수 있는가 이차원 배열 구조에서 원하는 위치의 요소를 선택할 수 있는가 풀이🛫 # 2804 크로스워드 만들기 # Bronze II word1, word2 = input().split() # 이차원 배열 생성 arr = [['.' for i in range(len(word1))] for j in range(len(word2))] # word1, word2에서 겹치는 글자의 인덱스 찾기 idx = 0 for i in word1: if i in word2: idx = i break # word1, word2에서 겹치는 글자의 인덱스 찾기 crs_idx_1 = word1.index(idx)# 1 crs_idx_2 = word2.index(idx)# 4 # 인덱스를 기준..
[백준 파이썬] # 2447 별 찍기 - 10
Silver III # 2447 별 찍기 - 10 링크 : https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 풀이 N = int(input()) # 빈 공간 생성 arr = [[' '] * N for i in range(N)] # 재귀문 작성 def fill_stars(size, x, y): # size: 확인하려는 공간(n*n)의 크기, x: x좌표, y: 좌표) # 재귀문의 탈출 조건, 더 이상 작아질 수 없을 때 ..
[백준 파이썬] # 1966 프린터 큐
Silver III # 1966 프린터 큐 링크 : https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 풀이 from collections import deque # 테스트 케이스 T개 T = int(input()) for i in range(T): N, M = map(int, input().split()) q = deque(list(map(int, input().split()))) idx = deque(list(range(N))) cnt = 0 # ..
[백준 파이썬] # 11279 최대 힙
Silver II # 11279 최대 힙 링크 : https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 풀이 import heapq import sys N = int(sys.stdin.readline()) heap = [] for i in range(N): x = int(sys.stdin.readline()) if x != 0: heapq.heappush(heap, -x) else: if len(heap) == 0: print(0..
[백준 파이썬] # 3273 두 수의 합
Silver III # 3273 두 수의 합 링크 : https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 풀이 n = int(input()) arr = list(map(int, input().split())) x = int(input()) arr.sort() start, end = 0, n-1 cnt = 0 while start < end: summary = arr[start] + arr[en..
[백준 파이썬] #10815 숫자 카드
Silver IV # 10815 숫자 카드 링크 : https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이 N = int(input()) has = list(map(int, input().split())) has.s6ort() M = int(input()) cards = list(map(int, input().split())) def bs(li, target): start = 0 end = len(li)-1 whil..