전체 글

파이썬(python) 값 전달, 참조 전달

Call by value (값에 의한 호출) 함수의 인자로 실제 변수를 넘기지 않고 변수의 값(객체)를 복사하여 인자로 넘김 Immutable (불변) 객체가 이에 해당된다. def func(name): name = 1 → a와 다른 메모리에 존재하는 name이라는 새 변수임 a = 1 func(a) Call by Reference (참조에 의한 호출) 공식적으론 Call by Assignment 라고 함. 함수의 인자로 실제 변수를 넘기고, 변수의 값(객체)를 변경시킬 수 있음. Mutable (가변) 객체가 이에 해당된다. def func(name): name[0]=4 a=[1,2,3] func(a) 결과 : a=[4,2,3] ※ 그러나 가변객체여도 인자로 받은 객체를 다른 객체로 치환해버리면 원본은..

파이썬(python) 과 C언어의 변수 저장 방식 차이

변수 저장 방식 차이 C언어 메모리 공간을 할당 받고 값을 집어 넣어서 사용하는 방식이다. 메모리 공간을 할당받는 방식이 정적/동적으로 나뉜다. 정적 메모리 할당 컴파일시 고정된 크기/타입의 메모리 공간 할당받아서 사용가능. (스택 공간) 크기 정해지고 중간에 바꿀 수 없음. 소멸할때 운영체제가 자동으로 메모리 반납 int a = 0; a라는 변수가 int형 크기만큼 메모리 공간 할당 받아서 그곳에 0을 넣음. 프로그램 종료시 운영체제가 알아서 메모리 반납 동적 메모리 할당 & 포인터 런타임에 원하는 크기/타입의 메모리 공간을 만들고, 그 공간을 가리키는 주소를 포인터 변수에 저장하여 사용해야 함. (힙 공간) (※ 포인트 변수란 값이 아닌 주소를 가리키는 변수임) 메모리 반납 수동으로 해주어야 함. 1..

파이썬(python) 리스트 잡기술

zip 함수 여러 개의 iterable 객체들을 지퍼를 닫아주듯 번갈아가며 짝지어서 튜플 형태의 iterator로 반환 길이 다르면 나머지 버려진다. zip(iterable_1, iterable_2) - output : zip 객체(iterable=반복가능) [tuple(1,2번이 번갈아가져 짝지어진 형태), ...] 이 객체를 list, tuple 등으로 변환하여 사용 사용법 list(zip(iterable_1, iterable_2)) - input : iterable_1 : [1,2,3] iterable_2 : [4,5,6] - output : [(1,4),(2,5),(3,6)] - 설명 : zip 함수로 객체 2개를 짝지어진 형태로 변환함 그 결과로 나온 zip 객체를 list로 변환 map 함수 ..

파이썬(python) 라이브러리 - heapq

heapq 파이썬에서 힙 (우선순위 큐) 자료구조를 이용할때 사용한다. C++, 자바는 우선순위 큐 자료구조를 제공하지만 파이썬은 리스트를 우선순위 큐 처럼 다룰 수 있는 함수를 제공한다. 최소 힙 (Default) heap = [] : 리스트 heapq.heappush(heap, 원소) : 힙에 하나 추가 O(logN) a = heapq.heappop(heap) : 힙에서 하나 빼서 반환 O(logN) heap[0] : 힙에서 빼지않고 값 얻기 O(1) 이미 값이 있는 리스트를 힙으로 사용하려면 변환이 필요 heapq.heapify(heap) : 변환 (리스트 → 힙) O(N) 최대 힙 튜플의 첫 번째 원소가 기준이 되는 것을 이용 heap = [] : 리스트 p = [4,3,2,5] heapq.hea..

파이썬(python) 백준 2206 : 벽 부수고 이동하기

2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제 내용 시간 제한 : 2 초 메모리 : 192 MB N×M의 행렬로 표현되는 맵에서 (1, 1)에서 (N, M)로 이동할때 최단 경로로 이동 이동은 4방향이다. 시작, 끝점 카운트해서 최단경로 길이 구하라. 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동해도 됨 0은 이동할 수 있는 곳 1은 이동할 수 없는 벽이 있는 곳 입력 첫째 줄에 N(1 ≤ N ≤ 1,000), M(..

파이썬(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 유형 수학 그리디 알고리즘 문자열 파싱 풀이 이 문제는 그리디 알고리즘 문제이다. 괄호를 쳐서 식을 최소로 만들기 위해서는 최대한 -를 탐욕..