프로그래밍/알고리즘 (13) 썸네일형 리스트형 문제해결기법 조교를 하며 이번에 과제로 https://www.acmicpc.net/problem/11048해당 문제와 비슷한 문제가 나왔다, 차이가 있다면 최대가 아니라 최소라는 것 그래서 해당 문제에서 유의해야할 것은 두 가지 있다. 위 문제에서는 r+1,c+1을 이용할 필요가 전혀 없다. 음수인 값도 없기 때문에 r+1 -> c+1이나 c+1 -> r+1을 해서 손해를 볼 일이 없기 때문이다. 최소가 되도록 하기 위해서는 r+1과 c+1도 의미가 있다. 사실상 백준의 저 문제에서도 구현에서 r+1,c+1을 포함해도 문제가 없기 때문에 과제로 나온 문제에서 문제가 발생한 사람은 없었다. 다른 하나는 dp를 이용해 이 문제를 해결한다면 테두리의 값을 신경써야 한다. 보통 dp 테이블을 만들 때 n+1, m+1로 제작을 하는데 이.. [파이썬 문법] 나는 재귀를 안 썼는데 왜 recursionError가? 최근 백준 문제를 풀다가 좀 편하게 짜려고 이상한 코드를 하나 짰었다.백준 게시판에 질문도 했었는데 아무도 답이 없었고, 이상한 짓이 굉장히 하고싶어지는 시험기간의 영향으로 해결하게 된 문제이다. 문제는 요약하면 문자열 여러개가 주어지고 배치되는 순서가 주어지면 그거에 맞춰서 문자열을 배치하면 되는 문제이다. n이 50만이나 되고, 문자열 길이의 총합도 50만까지 가능하다. 따라서 일반적으로 문자열을 합치는 방식으로 풀게된다면 시간 초과가 나게 된다. 그 이유는 파이썬 문자열 연산은 최종적으로 완성되는 문자의 길이만큼의 시간이 소요된다. 조금 깊게 가보면 파이썬 문자열은 "불변성"을 갖고, 뒤에 추가되는 것이 아닌 불변하는 여러개의 문자열에서 문자를 긁어와 새로운 문자열을 만드는 것이기 때문이다.a라는 .. 년/월/일/시/분/초 에 대한 고찰 이번 카카오 코딩 테스트도 그렇고 이러한 시간을 이용한 문제는 자주 출제되고는 한다. 나는 보통 이런 문제를 풀 때 가장 큰 단위부터 가장 작은 단위로 바꿔준다. 예를 들면 1년을 초로 바꾼다면 1*365*24*60*60이 될 것이다. 이렇게 바꿈으로써 문제 해결이 쉬워지는 문제들이 여럿 있다. 일단 이런 문제가 있다. https://www.acmicpc.net/problem/2525 2525번: 오븐 시계 첫째 줄에 종료되는 시각의 시와 분을 공백을 사이에 두고 출력한다. (단, 시는 0부터 23까지의 정수, 분은 0부터 59까지의 정수이다. 디지털 시계는 23시 59분에서 1분이 지나면 0시 0분이 된다.) www.acmicpc.net hour,minute=map(int,input().split()).. 파이썬 문자열 연산에 대한 고찰 2 파이썬은 매우 편리한 언어이다. 그만큼 자칫하면 실수하기 쉬운 몇몇 기능들이 있다. 그중 하나를 소개하려고 한다. 이번에 소개할 착각하기 쉬운 연산은 in 연산과 == 연산이다. ==연산은 좌우가 같은지 확인하는 연산이고 문자열의 경우 두 문자열이 같은지 확인하는 연산이다. 이것은 두 문자열의 글자 하나하나 비교하는 것이므로 O(1)이 아닌 O(N)이다. 정수의 경우 O(1)이지만 문자열의 경우 'ss...sf' 와 'ss...sss' 를 비교하면 맨 마지막 글자까지 탐색하면서 O(N) 만큼의 시간이 걸리게 된다. in 연산은 a in b 이런 식으로 a가 b 안에 속하는 지 확인할 때 사용하는 연산이다. 문자열의 경우 우리가 ctrl+F로 찾는 것처럼 a라는 문자열을 b에서 찾는 것이다. 이 경우 O(.. 파이썬 문자열 연산에 대한 고찰 파이썬은 매우 편리한 언어이다. 그만큼 자칫하면 실수하기 쉬운 몇몇 기능들이 있다. 그중 하나를 소개하려고 한다. 파이썬에서는 문자열을 더할 수 있다. 'SSS' + 'ZZZ' = 'SSSZZZ' 이다. 이것을 O(1) 혹은 그에 준하는 연산이라 생각하면 안된다. 이것이 O(1)인지 아니라는 것을 증명하는 것은 간단하다. 만약 O(1)이라면 더하는 문자열의 길이에 상관없이 비슷한 시간이 걸릴 것이다. 예를 들어 'S'+'S' 와 'SS...S' + 'SS...S' 에 걸리는 시간이 동일하다면 O(1)일 것이다. now = time() word='s' add='s' for i in range(1000000): word+=add print(time()-now) now = time() word='sssssss.. 소수 판별법에 대한 고찰 소수 판별은 기초적인 알고리즘이며 여전히 코딩 테스트에서도 자주 출몰하고 여러 문제에 섞여들어가고는 하는 단골 유형이다. 그렇다면 소수를 판별하는 방법에 대해 고민해보자. 단일 소수 판별법 하나에 자연수에 대해 소수인지 판별하는 경우 아래와 같은 시간복잡도로 해결할 수 있다. 1. O(N) - 모두 탐색 말 그대로 모두 탐색하면 된다. n=(int(input()) isPrime=True if n>1 else False for i in range(2,n): if n%i==0: isPrime=False break 위와 같이 코드를 작성하면 2~n-1 까지의 수로 모두 나눠보며 나눠진다면 최종적으로 isPrime은 False일 것이고 나눠지지 않는다면 최종적으로 isPrime은 True일 것이다. 하지만 이렇.. 소수 판별에 대한 고찰 소수 판별은 기초적인 알고리즘이며 여전히 코딩 테스트에서도 자주 출몰하고 여러 문제에 섞여들어가고는 하는 단골 유형이다. 그렇다면 소수를 판별하는 방법에 대해 고민해보자. 단일 소수 판별법 하나에 자연수에 대해 소수인지 판별하는 경우 아래와 같은 시간복잡도로 해결할 수 있다. 1. O(N) - 모두 탐색 말 그대로 모두 탐색하면 된다. n=(int(input()) isPrime=True if n>1 else False for i in range(2,n): if n%i==0: isPrime=False break 위와 같이 코드를 작성하면 2~n-1 까지의 수로 모두 나눠보며 나눠진다면 최종적으로 isPrime은 False일 것이고 나눠지지 않는다면 최종적으로 isPrime은 True일 것이다. 하지만 이렇.. 깊이우선탐색 구현에 대한 고찰 깊이우선탐색은 탐색 알고리즘이고 스택의 원리를 이용해서 구현된다. (너비우선탐색은 큐, 다익스트라는 힙의 방식을 이용한다) 대부분의 사람들은 깊이우선탐색을 함수를 이용해서 구현하고는 한다. 실제로 함수가 호출되고 종료되며 작동하는 것은 스택의 원리와 유사하게 작동하지만 왜 실제로 스택을 이용하지 않는 것일까? 파이썬에서는 특히 이 점을 신경써야 한다. 왜냐하면 기본적으로 재귀 제한이 3천밖에 안되므로 만약 깊이우선탐색으로 일자로 4천개의 노드가 이어져 있는 그래프를 탐색한다면 Recursionerror를 반환할 것이다. 그러므로 sys 라이브러리의 setrecursionlimit을 이용해 재귀 제한을 풀어주어야 한다. 이러한 번거로움이나 문제점을 발생시키지 않도록 그러면 스택을 이용해서 구현을 해주면 되.. 다익스트라와 0-1 BFS에 대한 고찰 가중치가 존재하는 그래프 즉 0과 1 이 두 개만 존재하는 그래프가 존재한다고 했을 때 이때 다익스트라 알고리즘을 사용하면 O(ELogV)의 시간복잡도를 갖는다. 하지만 이런 상황에서는 우선순위 큐가 아닌 덱을 활용하여 O(E+V)의 시간복잡도로 해결할 수 있다. logV가 매우 강력한 복잡도이긴 하지만 역시 곱보단 합이 훨씬 시간적으로 이득이다. 그 방법또한 간단하다. 덱을 이용해서 다음에 넘어가려는 곳의 가중치가 1이라면 덱의 뒤쪽에 append 0이라면 앞에 append해주면 된다. append와 pop은 O(1)이고 V개의 정점에서 탐색하고 E개의 간선만큼의 값이 큐에 들어가므로 O(V+E)이다. 원리는 다음과 같다. 일단 탐색을 진행하면서 다음 노드가 0이라면 누적값에 0을 더하면 값이 변하지 .. 다익스트라 알고리즘과 플로이드 와샬 알고리즘에 대한 고찰 E개의 간선과 V개의 정점을 갖는 그래프가 있다고 가정하였을 때 다익스트라는 한 개의 정점에서 나머지 연결된 정점들까지의 거리를 O(ElogV)의 시간복잡도로 구할 수 있다. 시간복잡도에 대한 이유는 간선 만큼의 heap에 push가 발생한다. 그 횟수가 E이고 heap에 push하는데 걸리는 시간은 LogN 이므로 E개에 간선에 대해서 push가 발생하므로 LogN이 걸리는 push를 E번 수행 즉 E*logV 이다. 플로이드 와샬 알고리즘은 모든 정점에서 다른 모든 정점까지의 거리를 O(V^3)의 시간복잡도로 구할 수 있다. (왜냐하면 3중 for문 으로 구하니까) 그렇다면 모든 정점에서 다른 모든 정점까지의 거리를 구하려 할때 모든 정점에서 다익스트라를 사용한다면 시간복잡도는 V (모든 정점에 대해.. 이전 1 2 다음
