Python

자료구조 활용 [개념]

스택 (Stack) 나중에 입력된 데이터가 먼저 출력되는 LIFO 자료구조 (하노이의 탑..) 파이썬에서는 리스트 자료형을 사용하여 스택 구조로 데이터를 처리할 수 있다. 리스트로 데이터의 입출력을 하려면 아래와 같은 함수를 사용한다. 데이터 입력: push → append() 데이터 출력: pop → pop() pop은 데이터 맨 마지막 값을 뽑아 반환시켜 준다. pop으로 뽑아낸 데이터는 리스트에서 없어진다. stack = [] # 빈 리스트 선언 stack.append(2) stack.append(5) stack.append(8) # stack: [2,5,8] stack.pop() # 8 stack.pop() # 5 stack.pop() # 2 큐 (Queue) 가장 먼저 입력된 데이터가 가장 먼저..

정규 표현식

정규 표현식 정규 표현식에서 사용하는 메타문자에는 다음과 같은 것이 있다. . ^ $ * + ? { } [ ] \ | ( ) 1013 Contact (골드 5) import sys import re # 정규 표현식을 지원하는 re 모듈 input = sys.stdin.readline T = int(input()) # 반복문을 통해 테스트 케이스를 확인 for _ in range(T): t = str(input().rstrip("\n")) pattern = re.compile('(100+1+|01)+') # re.compile()함수를 통해 () 안의 패턴 컴파일 ans = pattern.fullmatch(t) # pattern과 t가 매치되는지 확인 # 매치가 되면 테스트 케이스는 제시한 패턴인 것이다...

Dynamic Programming

9251 (골드 5) import sys input = sys.stdin.readline s1 = input().rstrip() s2 = input().rstrip() # dp테이블 생성 # 가장 윗줄과 가장 왼쪽줄도 비교를 해줘야 하기 때문에 한칸씩 더해서 만들어준다. matrix = [[0]*(len(s2)+1) for _ in range(len(s1)+1)] for i in range(1, len(s1)+1): for j in range(1, len(s2)+1): if s1[i-1] == s2[j-1]: matrix[i][j] = matrix[i-1][j-1]+1 else: matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1]) print(matrix[-1][-1..

유니온 파인드

서로소 집합 서로소 집합이란 공통 원소가 없는 두 집합을 의미한다. 서로소 집합 자료구조는 몇몇 그래프 알고리즘에서 매우 중요하게 사용된다. 서로소 집합 자료구조 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 union(합집합) 연산은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산이다. find(찾기) 연산은 특정 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다. 스택과 큐가 각각 push와 pop 연산으로 이루어진 것처럼, 서로소 집합 자료구조는 union과 find 연산으로 구성된다. 이 자료구조를 구현할 때는 트리를 이용하여 집합을 표현한다. 트리를 이용하여 집합을 표현하는 서로소 집합 계산 알고리즘은 다음과 같다. union(합집합) 연산을 확인하여, 서로 ..

07) 이진탐색

순차 탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 보통 정렬되지 않은 리스트에서 데이터를 찾을 때 사용한다. 리스트에 특정 값의 원소가 있는지 체크할 때 리스트에 특정 값이 원소의 개수를 세는 count() 메서드를 이용할 때 이진 탐색 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 이진탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. 찾으려는 데이터와 중간점에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다. 이진 탐색의 시간 복잡도 한 번 탐색할 때마다 확인하는 원소의 개수가 절반씩 줄어든다는 점에서 시간복잡도는 O(logN)이다. (=퀵정렬) 이진 탐색 구현 방법 1. 재귀함수 이용 # 이진탐색 재귀..

12) 구현

피지컬로 승부하기 코딩 테스트에서 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'을 의미하며, 개발할 때 프로그래밍 언어 문법에 능숙하고 타자가 빠른 사람을 보고 '피지컬이 좋다'라고 이야기 한다. 구현 문제는 그러한 '피지컬을 요구하는' 문제이며, 완전탐색과 시뮬레이션 유형이 구현 유형에 해당한다. 방향 벡터 (in 2차원 공간) x: 행 만큼(세로 크기) / y: 열 만큼(가로 크기) *내 기존 생각과 반대 -> (x,y)로 쓰자 / 위로 가면 (-1,0)이고 아래면 (1,0)임을 기억하자 * # 동,북,서,남 dx = [0,-1,0,1] dy = [1,0,-1,0] # 현재 위치 x,y = 2,2 # 다음 위치 for i in range(4): nx = x+dx[i] ny = y+dy[..

리스트 순회

https://dojang.io/mod/page/view.php?id=2292 파이썬 코딩 도장: 23.2 반복문으로 2차원 리스트의 요소를 모두 출력하기 이제 반복문을 사용하여 2차원 리스트의 요소를 모두 출력하는 방법을 알아보겠습니다. 23.2.1 for 반복문을 한 번만 사용하기 먼저 for 반복문을 한 번만 사용하는 방식입니다. >>> a = [[10, 20], [30, dojang.io 1. for 반복문을 한 번 사용하기 a = [[10, 20], [30, 40], [50, 60]] for x,y in a: print(x,y) 2차원 리스트에 for를 사용하면 가로 한 줄씩 반복한다. (전체 리스트 기준으로는 안쪽 리스트가 통째로 반복) for x,y in a 와 같이 in 앞에 변수 두 개를..

리스트 입력

1차원 배열 1. 띄어쓰기 입력 시 하나의 리스트에 저장하기 split(): 특정문자를 기준으로 나누어 받은 문자열을 문자로 분리 map(): 리스트로 입력받은 데이터를 형식에 맞게 변환 ex) int() list(): 리스트로 변환 data = list(map(int, input().split())) 결과> [1,2,3,4] 2. 띄어쓰기로 변수 입력받기 a,b,c = map(int, input().split()) 입력> 1 2 3 결과> a=1, b=2, c=3 3. Enter로 변수 입력받기 arr = [] for i in range(n): # 원소의 개수 n일 때 arr.append(int(input())) 2차원 배열 1. 세로 크기의 리스트 생성하고 한 리스트씩 입력받기 arr = [for ..

최단경로

최단 경로 최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 '길 찾기' 문제로도 불린다. '한 시점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우', '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우' ... 등의 다양한 사례가 존재한다. 최단 경로는 보통 그래프를 이용하여 표현하는데 각 지점은 그래프에서 '노드'로, 지점간 연결된 도로는 '간선'으로 표현된다. 실제 코딩 테스트에서는 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하도록 요구하는 문제가 많이 출제된다. 다익스트라, 플로이드 워셜, 벨만 포드 알고리즘 등의 3가지가 주로 사용된다. 다익스트라 알고리즘 다익스트라는 그래프에서 여러 노드가 있을 때, 특정 노드에서 출발..

03) 그리디 알고리즘

그리디 알고리즘은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 통해 매 순간 가장 좋아보이는 것을 선택하여 문제를 푸는 방식이다. ex) 거스름돈 당신은 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전히 무한히 존재한다. 손님에게 거슬러 줘야 할 돈이 N원일 때, 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다. → 이 문제는 그리디를 이용해 풀 수 있는 대표적인 문제로 '가장 큰 화폐 단위부터' 돈을 거슬러 주는 간단한 방식으로 구현 할 수 있다. N = int(input()) # 1260 count = 0 # N을 500,100,50,10으로 나누자 coin_types = [500,100,50,10] fo..