Python

파이썬(python) 백준 16236 : 아기 상어

16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 내용 시간 제한 : 2 초 메모리 : 512 MB 공간 NxN 크기의 공간 등장인물 물고기 M마리, 각 크기는 1~6으로 입력 주어짐 아기상어 1마리, 최초 크기 2 동작 아기상어가 1초에 상하좌우로 이동한다. 아래의 제약 조건 있음. 자기보다 크기가 큰 물고기 : 못먹음, 지나가기 가능 크기 같은 물고기 : 못먹음, 지나가기 가능 크기 작은 물고기 : 먹음. 지나가기 가능 아기상어 현재 크기만큼 물고기 (개수) 먹으면 아기상어 크기+1 종료 조건 더..

파이썬(python) 백준 14496 : 그대, 그머가 되어

14496번: 그대, 그머가 되어 첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1

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

string 0~9 까지 숫자, a~z까지 알파벳을 일일이 적지않고 바로 가져올 수 있다. 알면 꽤 편리한 라이브러리다. import string string.ascii_lowercase # 소문자 abcdefghijklmnopqrstuvwxyz string.ascii_uppercase # 대문자 ABCDEFGHIJKLMNOPQRSTUVWXYZ string.ascii_letters # 대소문자 abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ string.digits # 숫자 0123456789 참고) 공식 문서 6.1. string — Common string operations — Python 3.4.10 documentation 6.1. string — ..

파이썬(python) 투 포인터

투 포인터 리스트에 순차적으로 접근해야할 때 두개의 포인터를 이용하여 합을 구하는 기법 O(N)으로 해결가능 1) a+b = k 시작점은 첫번째, 끝점은 마지막 원소를 가리킨 상태에서 시작. 이 경우는 정렬된 상태에서 진행이 필요하다. start, end, result = 1, n-1, 0 while start x: end-=1 elif total < x: start+=1 else: start+=1 result+=1 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을..

파이썬(python) 알고리즘 - 최단 경로 (다익스트라)

최단 경로 찾기 (다익스트라) 개요 항목 내용 언제 쓰는가? 양의 가중치가 있는 방향/양방향 그래프에서 최단경로 찾기 하나의 노드에서 출발하여 다른 모든 노드로 가는 최소/최대 비용 계산 (노드+간선)*log(간선) 이 2천만 이하 (python 기준) 그래프 유형 방향/양방향, 가중치 가중치 양(o) 음(x) 시간 복잡도 O((V+E)logV), ((V+E)logV cost : distance_arr[next] = cost heapq.heappush(heap,(cost,next)) 문제 예시 & 코드 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 ..

파이썬(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(..