코딩테스트/파이썬 알고리즘

오늘은 파이썬의 변수 할당에 대해서 알아보겠다. 매일 코테문제를 풀고있었는데도 이런 기초적인 것도 몰랐다는 것에 쑥스러웠다. 갑자기 이걸 작성하게 된 이유는 평소처럼 백준 문제를 풀고있었는데, 이상한 곳에서 계속 오류가 나는 것 때문이었다. 내 코드가 잘못된 것도 아니고 어려운 함수를 쓴 것도 알고리즘을 쓴것도 아니고 맨날 하던 변수선언후 append를 하고있었는데 값이 계속 변하는 것이었다. 도저히 해결을 못해서 백준에 질문을 남겼고 recoma 님이 답변을 주셨다ㅠㅠ 정말 감사합니다. 우선 해당 질문글은 이것이다. 글 읽기 - 파이썬 반복문 질문 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net 위 질문글을 읽어보면 알겠지만, pos라는 배열에는 좌표를 저장하고 있었는데 분명 pos는..

오늘은 BFS 너비우선탐색에 대해서 설명하겠다. 저번 DFS에서 간단하게 말했었는데 다시 설명하겠다. DFS와 구별하면서 이해하는게 훨씬 쉽다. DFS는 한분기의 끝까지 탐색하고 아니면 돌아오고 다시 끝까지가고를 반복하는데, BFS는 "너비" 우선탐색이므로 한단계를 전부 탐색하고 다음 깊이로 들어간다. 즉 루트로부터 가까운 애들을 먼저 탐색한후 점점 멀어진다. 너비우선탐색은 최단경로나 임의의 경로를 찾을 때 쓰인다. DFS는 재귀로 구현을 했는데, WBS는 보통 QUE를 의 선입선출을 이용해서 코드를 구현한다. 이때 주의할점은 반드시 방문한 노드를 기억하는 코드가 있어야된다는 곳이다. 방문만하고 기억하지않으면 무한루프에 빠지게 된다. from collections import deque def bfs(g..

동적프로그래밍을 단순하게 설명하면 큰 문제를 작은문제로 나누어 푸는 방법이다. 단 작은문제들이 계속 반복되어야 한다. 바뀌면 안된다. 동적프로그래밍에서는 메모이제이션(Memoiztion)이라는 방법을 쓰는데 이름에서도 유추할 수 있듯이 메모를 하듯 작은문제들의 답을 기억하여 사용하는 것이다. 동적프로그래밍의 가장 쉬운 예시 피보나치 수를 예로 들어보자. 피보나치 수의 공식은 아래와 같다. 위 처럼 F2를 구하기 위해서는 F1,F0이 필요하고, F3을 구하기 위해서는 F2, F1이 필요하다. 위의 저 공식처럼 계속해서 반복이 일어나며 공식을 찾기만하면 구할 때 마다 정답이 같다. 이렇듯 점화식같이 이전항과 다음항과의 관계를 알아내서 값을 기억하면서 다음 값을 찾아내는 것이 동적프로그래밍이다. 동적프로그래밍..

이번에는 자주 쓰이는 큐와 스택에 대해서 설명할 것이다. 단순 리스트등으로 구현하면 시간초과나 메모리초과가 나오는 문제들을 자료구조를 큐와 스택으로 설정해서 간단하게 풀리는 문제들이 많다. Stack 스택의 가장 큰 특징은 후입선출(LIFO, Last-In-First-Out) (나중에 들어간것이 먼저 나감)이다. 데이터를 추가할 때도 top에 쌓이고, 삭제할 때도 top에 있는 것이 사라진다. 즉 한방향 구조이다. top에 데이터를 삽입하는 것을 push라고 하고, top에 있는 데이터를 삭제하는 것을 pop이라고 한다. 스택은 아래와 같은 문제에서 많이 사용된다. 전부 후입선출이라는 특징때문에 아래와 같이 마지막에 대한 데이터를 다루는 문제에서 유용하다. 특히 괄호쌍 문제는 매우 많이 나온다. - 방문..

오늘은 파이썬에서의 모듈,함수,패키지,메소드등의 차이점에 대해서 공부했다. 갑자기 이걸 공부한 이유는 다른 사람의 코드들을 보다보면 내가 처음안 코드들이 있는데 예를 들어 import math, from collection 등 같은 것들 블로그를 쓸 때마다 이게 모듈인지 패키진지 뭐가 뭔지 몰랐다. 매번 흘려들어서 그냥 그런게 있다고만 알고 있었다. 그래서 이참에 정리해보려고 한다. Module, Package, , Library 비교 1. Module - 함수와 변수 클래스를 모아놓은 하나의 파일. - 파일 이름이 모듈의 이름을 의미하고, 파일 형식이 py이다. - explain이라는 모듈을 가져오기 위해서는 아래와 같이 import한다. import explain 2. Package - 모듈들을 모아..

오늘은 은근 자주 나오는 유클리드 호제법과 에라토스테네스의 체에 대해서 설명해보겠다. 우선 유클리드 호제법은 최대공약수를 구하는 알고리즘이다. 최대공약수를 알면 최소공배수도 쉽게 알 수 있기 때문에 유클리드 호제법은 보통 최대공약수와 최소공배수를 구할 때 모두 쓰인다. 우선 바로 코드부터 보여주자면 if(b>a) : a,b = b,a while(b!=0): a=a%b a,b=b,a print(a) 우선 입력받은 두 수중에 큰 수를 정해놓고 큰 수를 작은 수로 계속 나누어서, 나누어 떨어질 때까지 반복한다. 나누어 떨어질 때(나머지가 0일 때), 나누는 수가 최대공약수이다. 이 방법은 a,b의 최대공약수는 (a-b),a의 최대공약수와 같다는 성질 때문이다. 이 때 최소공배수는 a*b를 a와 b의 최대공약수..