Python

파이썬(python) 백준 7576 : 토마토

7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 내용 시간 제한 : 1 초 메모리 : 256 MB 세로 n 가로 m의 창고에 토마토가 있다. 익은 토마토는 하루 지날때마다 4방향의 안익은 토마토를 익은 토마토로 바꿈 창고의 모든 토마토 익으려면 최소 며칠 걸리는지 구하라 익은 토마토 : 1 안익은 토마토 : 0 토마토 없음 : -1. 입력 가로 m 세로 n nxm 크기의 창고 정보 출력 처음부터 모든 토마토가 익은 상태면 0 출력 토마토가 모두 익지 못하는 상황이면 -1 출력 토마토가 모..

파이썬(python) 문자열 중복제거 (unique)

문자열 중복제거 1. set로 변환 후 join 함수 사용 : 순서보장 X s = 'aaabbbccc' b = ''.join(set(s)) print(b) # cba 2. dict.fromkeys(word) 파이썬 3.6부터 dict가 순서보장하기 때문에 사용가능 s = 'aaabbbccc' a = ''.join(dict.fromkeys(s)) print(a) # abc 3. OrderedDict로 변환 후 join 함수 사용 : 순서 보장 O 파이썬 3.6이전 버전에는 기본 내장 dict가 순서 보장 안되어서 사용했던 OrderedDict 사용 from collections import OrderedDict s = 'aaabbbccc' a = ''.join(OrderedDict.fromkeys(s)) ..

파이썬(python) 알고리즘 - 동적 계획법 푸는 방법

DP문제를 풀어나가는 순서 1. 문제의 조건대로 손으로 그려보며 반복되는 부분을 찾습니다. 2. dp테이블 dp[i]는 무엇을 의미하는지 정의해봅니다. dp[i] = ??? 3. 디테일한 점화식을 세웁니다. dp[i] = dp[i-1] + dp[i-2] 4. 필요하다면 dp 테이블을 확장합니다. dp[i] → dp[i][j] 5. 중복되는 부분을 어떻게 활용할 수 있을지 생각합니다. 어떤 방법으로도 점화식 세워지지 않으면 계산 과정이나 정의의 순서를 뒤집어서 생각해봅니다. 예를 들면 계산 과정을 완전히 거꾸로 뒤집어보는 발상을 해봅니다. 즉 1+1=2 이 아니라 2=1+1 이라는 발상을 하는 것입니다. 1번으로 되돌아가서 다시 진행합니다. DP문제 유형이라고 어떻게 판단하는가? 문제만 보면 완전 탐색과 ..

파이썬 (python) 자료형

자료 형 자료형 마다 부여된 성질을 이해해야 한다. Sequence(연속적인 값이 이어진 형태)/집합/매핑 → Iterable(for문으로 순차접근 가능) Literal(상수) → Immutable(변경불가능) str(문자열) → Literal(상수) 이면서 Iterable(순차접근 가능)한 특수한 형태. 자료형 Iterable Literal / Container Mutable / Immutable int X Literal Immutable float X Literal Immutable list O Container (Sequence) Mutable tuple O Container (Sequence) Immutable range O Container (Sequence) Immutable str O Lit..

파이썬(python) 라이브러리 - collections.deque

collections.deque 파이썬에서 queue를 이용할때 사용한다. list를 이용하면 add 연산에 O(n) 만큼의 시간이 들기 때문에 deque를 사용해야함. 데이터가 오른쪽으로 추가되고 왼쪽으로 나가는 형태 q = collections.deque() q.append() # 오른쪽으로 더하기 q.popleft() # 왼쪽으로 값 빼기 q.appendleft() # 왼쪽으로 추가 q.pop() # 오른쪽으로 빼기 q.extend() # 오른쪽으로 값 추가 (각요소를 잘라서 넣어줌) deque(['a','b','c']).extend('defg') → ['a','b','c','d','e','f','g'] append로 넣으면 'defg'로 들어가짐 q.rotate(n) n만큼 요소들을 회전시켜준다...

파이썬(python) 알고리즘 - DFS, BFS

DFS (깊이 우선 탐색) 깊이를 우선으로 탐색하는 알고리즘 시작 노드에서 방문하지 않은 인접 노드를 큐에 삽입 (방문 했음을 표시) 더 이상 방문할 수 없는 경우 탐색 중단하고 이전 상태로 되돌아옴 특징 스택 or 재귀함수 사용 한 방향으로 최대한 깊게 접근해본다 (경고) 파이썬 최대 재귀 횟수는 1000번까지 가능하다. 재귀를 많이 호출하는 문제는 제한횟수에 걸려서 런타임 에러가 발생할 수도 있다. sys.setrecursionlimit(제한횟수) 로 제한을 늘릴 수 있다. import sys sys.setrecursionlimit(제한횟수) 기본 형태 def dfs(arr, cur, visited): visited[cur] = True for i in arr[cur]: if not visited[i..

파이썬(python) 백준 2580 : 스도쿠

백준 2580 : 스도쿠 문제 내용 시간 제한 : 1 초 메모리 : 256 MB baekjoon의 백트래킹 알고리즘으로 풀 수 있는 입력만 주어진다. 다음은 그 알고리즘의 수행 시간이다. C++14: 80ms Java: 292ms PyPy3: 1172ms 문제 아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다. 입력 모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다. 스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다. 출력 첫째 줄에 정답을 출력한다. 예제 입..

파이썬 (python) 백준 13305 : 주유소

백준 13305 : 주유소 문제 내용 시간 제한 : 2 초 메모리 : 512 MB 문제 일직선 상의 n개 도시 순서대로 이동 (n: 2~10만) - 노드 : 도시를 뜻하며, 숫자는 해당 도시에서의 기름값 - 간선 : 도시간의 도로길이 (1km이동 당 1리터 기름 사용) 입력 도시 개수 n 도로길이 순서대로 n-1개 주유소 리터당 가격 순서대로 n개 출력 모든 도시 이동하는 최소 비용 예제 입력 1 4 2 3 1 5 2 4 1 예제 출력 1 18 예제 입력 2 4 3 3 4 1 1 1 1 예제 출력 2 10 유형 그리디 알고리즘 풀이 이 문제는 그리디 알고리즘 문제이다. 기름값이 싼 도시에서 기름을 최대한 많이 구입하는게 이득이다. 이동을 위해 1번 도시에서는 무조건 기름 구매할 수 밖에 없다. 더 싼 가..

파이썬 (python) 알고리즘 - 그리디 알고리즘

그리디 알고리즘 현재 상황에서 최적의 값을 탐욕적으로 취하는 알고리즘 그리디 알고리즘으로 얻은 해가 최적의 해를 보장할 수 없는 때가 많지만, 코딩 테스트에서는 최적의 해를 보장하도록 나오므로 걱정하지 않아도 됨. 특징 몇 가지 선택지가 주어짐. 각각의 선택지를 최소한의 선택으로 조건을 만족하도록 하는 해를 구하기 이때 선택지A 보다 B가 더 최적이라는 것에 대한 정당성을 설명할 수 있어야 함. 백준 단계별로 문제 풀어보기 - 그리디 알고리즘 그리디 알고리즘 단계 동전의 조건이 특별해서 동적 프로그래밍보다 빠르게 답을 찾을 수 있는 문제 www.acmicpc.net 문제 풀이 파이썬(python) 백준 1541 : 잃어버린 괄호 백준 1541 : 잃어버린 괄호 문제 내용 시간 제한 : 2 초 메모리 : ..

파이썬(python) 백준 1541 : 잃어버린 괄호

백준 1541 : 잃어버린 괄호 문제 내용 시간 제한 : 2 초 메모리 : 128 MB 문제 양수와 +, -, 로 이루어진 식에 괄호를 적절히 쳐서 이 식의 값을 최소로 만들어라 입력 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다. 출력 첫째 줄에 정답을 출력한다. 예제 입력 1 55-50+40 예제 출력 1 -35 유형 수학 그리디 알고리즘 문자열 파싱 풀이 이 문제는 그리디 알고리즘 문제이다. 괄호를 쳐서 식을 최소로 만들기 위해서는 최대한 -를 탐욕..