Python8 [Python] 1_000은 도대체 뭘까 백준을 풀면서 다른 사람들 코드를 보는 중 i = 1_000 또는 i = 1_000_000 같은 코드를 봤다. 바로 스택오버플로우에 찾아봤다. https://stackoverflow.com/questions/49837534/what-do-1-000-and-100-000-mean What do 1_000 and 100_000 mean?Since I've been learning Python, I've sometimes seen beginner examples that look like this: sum_sq = [None] * 1_000 I've bought three Python books and none have mentioned what the 1_000 and 100_000stackoverflow.. 2022. 6. 14. [Python] 리스트 복사하기 (일차원 & 다차원) 코드 우선 리스트를 복사하려면 일차원이냐 다차원이냐에 따라서 나뉜다. 일차원 리스트 복사하기 # 방법 1 list2 = list1.copy() # 방법 2 list2 = list1[:] # 방법 3 list2 = list(list1) 다차원 리스트 복사하기 import copy list2 = copy.deepcopy(list1) list1 = list2는? 보통은 list1의 요소를 list2에다가 복사하고 싶다면 list2 = list1하면 되는 것 아니냐고 생각할 것이다. 그러나 이렇게 리스트를 복사한다면 list2의 요소를 변경했을 때 list1의 요소도 변경된다. 확인해보자. # 일차원 배열 list1 = [1, 2, 3, 4] list2 = list1 list2[0] = 0 print(list1.. 2022. 3. 25. [Python] DFS & BFS DFS & BFS 란? 먼저 읽으면 좋은 글: [Python] 그래프 (인접 행렬, 인접 리스트) + DFS/BFS를 배우기 앞서 알아야 할 개념들 (탐색 알고리즘, 자료구조) 위에 글에서도 언급했듯, DFS(Depth-First Search)와 BFS(Breadth-First Search)는 그래프 탐색 알고리즘(Graph traversal algorithm)이다. 그래프 탐색 알고리즘이란, 그래프의 모든 꼭짓점(Node 또는 Vertex라 한다)을 방문하는 알고리즘을 의미한다. DFS vs BFS DFS와 BFS의 차이점은 바로 노드 방문 순서이다. DFS DFS는 깊이 우선 탐색이라는 그 이름답게 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 스택 자료구조를 사용하여 그래프의 가장 깊은 곳.. 2022. 3. 19. [Python] 이분/이진 탐색 이분/이진 탐색이란?이분 또는 이진 탐색이라 불리는 이 탐색은(이하 이분 탐색) 탐색 범위를 반씩 좁혀가는 탐색하는 알고리즘이다. 이분 탐색은 결정 문제의 답이 이분적일 때, 그리고 데이터가 정렬되어 있을 때 사용할 수 있다. 보통 정렬되지 않은 리스트를 탐색해야 할 때 앞에서부터 순차적으로 확인하는 탐색인 순차 탐색을 쓰지만, 원소를 하나씩 확인해야 하기에 시간 복잡도가 O(n)이다. 그러나 이분 탐색은 계속해서 탐색 범위를 반으로 줄여나가기에 O(logN)으로 순차 탐색보다 빠르다. 구현이분 탐색을 구현하는 방법에는 2가지가 있다. 하나는 재귀 함수, 그리고 다른 하나는 반복문을 사용하는 것이다. 재귀 함수로 구현def binary_search(array, target, start, end): .. 2022. 3. 2. [Python] 백트래킹 (+ DFS와 차이) 백트래킹이란?백트래킹이란 현재 상태에서 가능한 모든 경로를 따라 들어가 탐색하다, 원하는 값과 불일치하는 부분이 발생하면 더 이상 탐색을 진행하지 않고 전 단계로 돌아가는, 즉 이름 그대로 방금 왔던 길을 되짚어가는, backtrack 하는 알고리즘이다. 백트래킹과 DFS의 차이처음 백트래킹을 접했을 때, 아래와 같이 생각했다. 그런데 공부하면 공부할 수록 아래에 더 알맞다는 걸 깨달았다. 백트래킹이랑 DFS(Depth First Search) 모두 탐색하는 알고리즘이라 혼동하기 쉽다. 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 백트래킹이랑 DFS 모두 원하는 값을 찾기 위해서 다양한 방법을 사용하는데 여기에서 차이가 발생한다. 우선 백트래킹은 불필요한 탐색을 하지 않는.. 2022. 1. 18. [Python] 다이나믹 프로그래밍 (DP) 다이나믹 프로그래밍이란?복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 의미한다. 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그 결과들을 결합하여 답을 구한다. 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는, 메모리 공간을 조금 더 사용함으로 연산 속도를 늘릴 수 있는 알고리즘 설계 기법이다. 예시이렇게 글로만 보면 확 와닿지 않는다. 그럼 예시를 한 번 보도록 하자. 다이나믹 프로그래밍(이하 DP)으로 해결할 수 있는 대표적인 문제 예시로 피보나치 수열이 있다. n번째 피보나치 수는 n-1번째 수 더하기 n-2번째 수이다. 이걸 정리하면 f(n) = f(n-1) + f(n-2)이다. def fibo(n): if n == 0: .. 2022. 1. 15. [Python] 소수 찾기 알고리즘 소수란?1보다 큰 자연수 중, 1과 자기 자신 외에는 나누어지지 않는 수 누가 알고리즘 문제를 만드는지 모르겠으나 이 사람들 소수 찾기에 진심이다. 학교에서 수학 배울 때 빼고 단 한 번도 신경 쓰지 않았던 소수, PS 하다가 소수 문제가 하도 많이 나와, 한 번 정리해야겠다 싶어 정리한다. 소수 찾기 알고리즘소수 찾는 방법은 여러 가지가 있다. 소수인지 판별이 필요한 수를 n이라고 하겠다.1. 숫자 n 나누기2부터 n-1까지 나누기def isPrime(n): if n n-1까지, n이 1과 자기 자신 외의 수로 나누어지는지 판단하는 알고리즘이다. 만약 나누어진다면 바로 false를 리턴한다. n-1까지 걸리지 않는다면 True가 리턴된다. 가장 간단하고, 기초적이지만 오래 걸린다. 2부터 n-1까지의 .. 2021. 12. 20. [Python] input과 sys.stdin.readline의 차이 파이썬으로 백준 문제를 풀어본 사람이라면 가끔씩 많은 입력을 받는 문제를 풀 때 시간과 발생한 적이 있을 것이다. 이럴 때 input 대신 sys.stdin.readline을 사용하면 시간이 초과되지 않는다. 과연 이것은 무엇이길래 입력받는 속도를 향상할 수 있는 걸까? 답을 찾기 위해 우선 input과 sys.stdin.readline의 동작에 대해서 알아보도록 하자. input공식 문서에 따르면, input 함수는:1. 입력으로 들어오는 한 줄을 읽고,2. 문자열로 변환하고,3. 개행 문자를 제거한 뒤,4. 값을 반환하는 형식으로 동작한다고 한다. 입력 하나를 받는데 4단계의 과정을 거치는 것이다.sys.stdin.readline우선 sys와 stdin의 의미를 알아보도록 하자.syssys는 시.. 2021. 12. 10. 이전 1 다음