본문 바로가기

BackJoon

5582 공통 부분 문자열 [LCS] LCS란 Longest Common Subsequence 즉 최장 공통 부분문자열을 구하는 알고리즘입니다.예를들면 'ABCD' 와 'CDEFG' 라는 문자열이 있을때 'CD'라는 부분 문자열이 최장 공통 부분 문자열이 됩니다. 문자열의 길이가 짧은 경우에는 두 문자열의 모든 부분문자열을 비교해 찾을수 있지만 문자열이 길어질경우 많은 시간이 걸리게 됩니다. 다음은 모든 문자열을 비교해 찾는 소스코드입니다. 아주간단합니다. a = input() b = input() a_len = len(a) b_len = len(a) res = 0 for i in range(b_len): for j in range(i + 1, b_len + 1): if a.find(b[i:j]) != -1: res = max(res, le.. 더보기
10158 개미 겉으로 보기에는 쉬운 탐색문제이다 하지만 입력범위가 무려 x, y 더보기
1238 파티 [최단경로 알고리즘] 문제를 처음 읽고 음 floyd 알고리즘을 이용해 모든 최단경로를 구하면 되겠군! 했지만 n의 값이 최대 1000이였다.. 1000^3 이면 역시나 될리가 없다가지치기를 몇번 시도해봤지만 floyd 알고리즘에 대해 수박겉핥기식으로 아는정도라 시도하다가 포기했다.다시 고민한 결과 모든 정점의 최단경로를 구할필요가 없다는점에서 아이디어를 얻었다.즉 도착지 정점에서는 각 정점으로 가는 최단경로값은 모두 구해야한다, 하지만 다른 정점에서는 도착지로 가는 정점만 구하면 된다.즉 이말은 역방향 그래프를 하나더 생성해 정방향 도착지에서 모든정점 한번 역방향 도착지에서 모든 정점 한번 이런식으로 총 두번 구하면 된다.소스코드는 bfs로 나와있다. 딱히 다익스트라를 안써도 될것같아 (귀찮아서) bfs로 구했다 impor.. 더보기
1717 집합의 표현 [union-find] 문제 예제가 좀 애매해서 문제를 이해하는데 좀 시간이 걸렸다. 결국 알고리즘분류가 disjoint-set 인걸보고 이해했다.이 문제는 단순히 set을 이용해서 풀수도 있지만 입력제한에서 볼수있듯이 시간초과가 날수밖에없다.그렇다면 disjoint-set 다른말로 union-find 자료구조를 이용하면 해결할수 있다.union-find는 크루스칼 알고리즘에도 사용되는 구조로 즉, 원소가 같은 루트값을 가지는지 효과적으로 체크해주는 구조로 쉽게 생각하면 쉽다여기서 parent가 각 부모를 나타내는 리스트고 rank는 union을 최적화하기 위해 각 트리의 레벨을 설정함으로써 union 연산시 트리의 레벨이 낮은 쪽이 큰쪽밑으로 붙도록 하는 것이다. 즉 최적화를 위해 만든 리스트라고 보면된다. (없어도 돌아가긴.. 더보기
1987 알파벳 [BFS/DFS] BFS로 풀었다.. 단순히 완전탐색으로 할경우 20X20이여도 메모리초과가 뜬다.DFS로 풀었다.. 메모리초과는 안뜨지만 30~40%에서 시간초과가 뜬다. Python이여서 그런거같다.. 뭔가 쉬워보이는 문제면서도 안풀리길래 몇일 고민했다. 중복되는 방문을 체크하면 안되는줄 알았는데 우연히 예제입력 돌리다 반복되는 구조를 파악하고 이에 cache배열을 선언해 if cache[ny][nx] == data + board[ny][nx] 조건을 주엇다 즉 똑같은 값을 가진 문자열 데이터가 이미 존재하면 큐에 추가가 안되도록 말이다. 그랬더니 20x20 에서 나오던 경우의수 수십만가지가 엄청나게 줄고 (아무래도 알파벳수가 26가 끝이니) 다른언어와 비슷한속도로 풀었다. (뿌듯) import collections .. 더보기
2589 보물섬 [BFS] 2589 보물섬 bfs 문제인건 알고 있었으나 python 특유의 느린속도때문에 최대입력이 50x50이여도 각 칸마다 bfs로 brute force방식으로 하기엔 안될거같은 생각이 들었음에도,, 해보니 그냥 된다?! 최악의 수인 50x50 모두 Land 일경우 2500번을 visit배열을 생성하고 6252500번 pop, append를 반복하기에 당연히 시간도 테스트당시 10초이상걸리고 시간초과가 뜨겠거니 하고 다른방식을 생각하다 도저히 메모제이션이나 시간을줄일 방법이 안떠올라 안되면 c++로 해보자하고 해봤는데 정답으로 나온다.... 그냥 간단한 문제였던걸로 생각하자. import collections def bfs(): direct = [[0, 1], [1, 0], [0, -1], [-1, 0]] m.. 더보기
1931 회의실배정 [그리디 알고리즘] 그리디 알고리즘 탐욕법으로 가장최적인 답을 선택하는 패러다임을 이용하면 된다 [이 용어에 대해서는 아직 잘 모르겠다] input이 최대 100000번이 될수도 있으니 input함수대신 sys.stdin 을 이용하구 정렬되는데 걸리는시간이 O(NlgN) 에다 반복문 2번 2N이므로 이므로 대략 시간복잡도는 O(NlgN) 으로 풀수가 있다. 회의가 끝나는 시간을 기준으로 정렬하고 다시 반복문을 통해 회의가 제일 일찍 끝나는시간을 y_min 저장한후 회의시작시간이 y_min 보다 더 높은값이 나오면 그에 따른 회의시간이 끝나는 기준을 y_min에 저장 cnt 증가 반복을 통해 풀수 있다. import sys read = sys.stdin.readline n = int(read()) arr = [] for i .. 더보기
10164 격자상의 경로 [python] k 포인트 기준으로 두개의 영역으로 나눠 그 경우의수를 곱하는 방식을 이용하였다. 메모제이션을 사용하지않고 완전탐색을 하면 15x15 크기여도 시간초과로 인해 풀 수가 없다. 각 이동경로마다 방문된 곳이면 방문하지않고 방문된곳의 크기를 올리는 방식으로 문제를 풀었다 방문하는방법은 bfs를 이용하였다. def bfs(sy, sx, ey, ex): direct = [[0, 1], [1, 0]] q = [(sy, sx)] matrix[sy][sx] = 1 while q: y, x = q.pop(0) for dy, dx in direct: cy = dy + y cx = dx + x if cy >= ey + 1 or cx >= ex + 1: continue if matrix[cy][cx]: matrix[cy][c.. 더보기
2512 예산 [Python] 이진탐색을 이용하면 시간안에 풀 수 있다. def binary_search(): first, last = 0, max(arr) check = 0 while first x: check = 0 mid = (first + last) // 2 for i in arr: if i < mid: check += i else: check += mid if check 더보기
1937 욕심쟁이 판다 [Python] 문제대로 2차원 배열을 이용한 맵을 만든후 1,1 위치부터 판다가 살수 있는 최대일수를 구하는 방식으로 구현했다. 최대일수 구하는 방법은 dfs를 이용하였으며 재귀를 통해 방문될때마다 그 재귀를 호출한 스택에는 +1값을 주도록 하였다 최대일수가 메모되있으면 다른 행열을 찾아보는방식으로 시간을 절약하였다. import sys sys.setrecursionlimit(10**6) read = sys.stdin.readline def dfs(y, x): cache[y][x] += 1 for dy, dx in direct: cy = dy + y cx = dx + x if cy = n or cx >= n: continue if matrix[y][x] < matrix[cy][cx.. 더보기

티스토리툴바