오늘은 counter 함수를 설명하겠다. 관련된 문제로는 백준의 #11652 카드 문제가 있다. 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net 우선 나는 맨처음에 그냥 딕셔너리를 내가 만들어서 숫자의 개수를 세줬는데 이 기능을 그대로 해주는 함수가 있었다. collections 모듈의 counter 함수이다. 당연히 코드 맨윗줄에 모듈을 먼저 불러와야 하므로 import를 을 해줘야 한다 from collections import counter 위에서도 설명했지만 그냥 아래의 기능을 한 줄로 가능하게 하..
코딩테스트/파이썬 알고리즘
오늘은 알고리즘이 아니라 함수를 설명할 것이다. 백준에서 가장 간단한 입출력 문제들을 푸는데 계속 시간초과 오류가 떴었다. 다른 곳에서는 시간을 줄일 데가 없는데 계속 초과떠서 답답해하면서 검색하던 찰나에 sys함수를 발견했다. sys는 파이썬의 표준 라이브러리중에 하나이다. 이 라이브러리 안에서 sys.stdin.readline()이라는 함수가 있는데 이 함수가 바로 input()과 동일한 함수이다. 유일한 차이점은 sys.stdin.readline()은 맨뒤에 개행문자가 같이 입력된다는 점이다. 즉 우리가 입력값을 치고 엔터를 누를 때 그 문자도 같이 들어간다. 그것을 제외하고는 input()과 똑같이 단순 입력을 하는데 왜 이 함수를 쓰냐면 시간이 훨씬 빠르다. 또한 메모리도 적게 사용한다. 그래서..
오늘은 DFS(Depth-First-Search) 깊이 우선 탐색에 대해서 공부하려고 한다. DFS는 루트노드(혹은 임의의노드)에서 시작해서 다음 분기로 넘어가기전에 해당 분기를 완벽하게 탐색하고 넘어가는 알고리즘을 뜩한다. 이 방법은 모든 노드를 탐색하려고 할 때 사용하며 BFS 너비우선탐색보다 간단하지만 모든 노드를 왔다갔다 하기 때문에 느리다. 이해하기 쉬운 비유로는 연속으로 된 갈림길이 있을 때 한방향으로 쭉가다가 막히면 바로 전 갈림길로 돌아와서 반대로 쭉가고 다시 돌아오고를 반복하는 것으로 이해 할 수 있다. 이렇게 계속 돌아오는 알고리즘이기 때문에 순환 알고리즘 즉 재귀함수의 형태를 띄고있다. 또한 스택을 사용하여 구현한다. graph = { 'a': ['b', 'c', 'e'], 'b': ..
Greedy(탐욕법) 알고리즘은 생각하기 단순하면서 강력하다. Greedy의 제일 핵심은 "매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향은 고려 하지 않는 것" 이다. 대부분의 탐욕법 문제는 가장큰 순서대로, 가장 작은 순서대로등의 힌트가 문제에 주어진다. 이 문제는 위에서 말했듯이 나중에 미칠 영향을 고려하지 않기 때문에 Greedy로 문제를 짜려면 미리 이 문제에 이 알고리즘을 적용해서 최적의 해가 나올지를 생각해야 한다. 즉, 문제를 먼저 정확히 이해해야한다. 대표적인 문제로는 거스름돈 문제로 백준의 #11047j번 동전0이 있다. 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 ..
BruteForce 알고리즘의 정의는 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법이다. 기본적으로 모든 경우의 수를 계산한다고 생각하면 되서 연관된 알고리즘으로는 순차탐색,DFS(깊이우선탐색),BFS(너비우선탐색)이 있다. 순차탐색관련 문제를 풀 때는 아래와 같은 방법으로 해결하면 된다. 1)문제에서 주어진 자료를 선형 구조로 구조화 2) 구조화된 자료들을 구조에 맞는 방법으로 해를 구할 때까지 탐색 3) 탐색한 해를 주어진 문제의 출력 형식에 맞게 정리 여기서 선형구조라 함은 -데이터가 연속적으로 연결되어 있는 모양으로 구성하는 방법으로, 아래와 같은 것들이 있다. 우선 브루트포스의 단점으로는 수가 커질수록 시간이 오래걸린다는 것이다. 처음 정의 그대로 모든방법을 실행하..
우선 비트마스킹은 이름에서 알 수 있듯이 비트를 이용한 알고리즘이다. 정확히 하자면 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법이다. 비트마스킹을 사용하면 더 빠르고 간결한 코드와 메모리 효율성을 얻을 수 있다. 우선 비트마스킹에 대해 설명하기전에 비트마스킹을 할 때 쓰이는 비트연산자의 종류에 대해 알아보자. 우선 비트마스킹이 빠른 이유는 집합등을 관리(삭제,추가 등)을 할 때 집합안의 유무를 0,1두개로 표현하여 간편하다. 각각의 자리르 지정해두고 그 자리의 비트가 1이면 집합에 있는것, 0이면 그 집합에 존재하지 않는 것을 의미한다. 예를들어 A,B,C,D,E,F가 있을 때 각각 A는 첫번째 자리, B는 두번째 자리 이렇게 쭉 정해놨으면 {A}라는 부..
