기록

문제 보기 [사용한 알고리즘] 브루트 포스, 구현, 부분 집합 [접근 방식] 입력받은 문자열 S가 팰린드롬인지 확인합니다. 만약 팰린드롬이 아니라면 입력 문자열 S를 뒤집어서 부분 팰린드롬의 길이를 찾은 후 최종 팰린드롬의 길이를 출력합니다. 이 과정은 아래 알고리즘에서 자세히 설명하도록 하겠습니다. [알고리즘] 1. 문자열 S가 팰린드롬인지 확인합니다. 만약 팰린드롬이라면 문자열 S의 길이를 출력합니다. 2. 문자열 S가 팰린드롬이 아니라면 reversed(S)에서 인덱스 0부터 시작하는 부분 팰린드롬의 문자열의 길이를 구합니다. 3. 문자열(S)의 길이 * 2 - 부분 팰린드롬 문자열의 길이를 출력합니다. abab를 예로 들어 설명하겠습니다. abab가 팰린드롬인지 확인합니다. 팰린드롬이 아니므로 2..

문제 보기 [사용한 알고리즘] BFS(너비 우선 탐색) [문제 접근] 지도 상의 최단 거리를 구하는 문제는 대부분 DFS보다 BFS가 효율적이라 BFS로 접근하였습니다. DFS는 모든 경우를 탐색해야지 최단 경로인지 알 수 있기 때문입니다. [알고리즘] 1. 현재 위치를 기준으로 상, 하, 좌, 우 이동합니다. (말의 형태로 이동이 가능한 상황이라면 말의 이동도 수행합니다) 2. 이동하려는 공간에 이전에 더 적은 말의 이동으로 도달한 적이 있다면 이동을 하지 않습니다. 3. 큐가 빌 때까지 혹은 도착지점에 도달할 때까지 위 과정을 반복합니다. 4. 도착지에 도달했으면 이동 횟수, 만약에 도달하지 못했으면 -1을 출력합니다. [코드] from collections import deque import sys..

문제 보기 [사용한 알고리즘] dijkstra(다익스트라), BFS(넓이 우선 탐색) [문제 접근] 출발점과 도착점을 알고 있고 음의 가중치가 없는 최단 경로를 구해야 하기 때문에 다익스트라를 사용하였습니다. [알고리즘] 1. 다익스트라 알고리즘을 사용하여 최단 경로의 값을 구합니다. 2. BFS 알고리즘을 사용하여 최단 경로의 경로를 구합니다. 3. BFS 알고리즘으로로 구한 경로를 삭제합니다. 4. 다시 한번 다익스트라 알고리즘을 사용해서 거의 최단 경로를 구합니다. [코드] from collections import deque import sys import heapq INF = 1e9 def dijkstra(): q = [] heapq.heappush(q, (0, s)) distance[s] = ..

문제 보기 [사용한 알고리즘] 이분 탐색(binary search) [문제 접근] N명의 아이들을 놀이기구에 태울 수 있는 시간을 구한 후 놀이기구의 번호를 구하였습니다. N의 범위가 크기 때문에 0초부터 시간을 탐색하는 것이 아니라 이분 탐색으로 시간을 구하였습니다. [알고리즘] 1. 놀이기구의 수보다 아이들의 수가 적으면 아이들의 수를 출력합니다. 2. 이분 탐색을 통해 아이들을 모두 태울 수 있는 시간을 찾습니다. 3. 구한 시간 - 1분까지 몇 명의 아이를 태울 수 있는지 탐색합니다. 4. 구한 시간에 탑승하는 아이들을 계산하면서 제일 마지막에 탑승하는 놀이기구의 번호를 출력합니다. (놀이기구 탑승 인원이 N명이 될 때의 놀이기구 번호를 출력하면 됩니다) [코드] import sys if __na..

문제 보기 [사용한 알고리즘] DFS(깊이 우선 탐색) [문제 접근] 주어진 트리에서 전위 순회와 중위 순회 결과를 적어보니 규칙을 발견하였습니다. 전위 순위에서 발견한 루트 값을 중위 순위에서 찾아보니 루트 값을 기준으로 왼쪽 서브 트리, 오른쪽 서브 트리로 분리되었습니다. 따라서 이를 응용하여 재귀로 구현하면 후위 순위를 구하였습니다. [알고리즘] 1. 전위 순회의 루트와 중위 순회의 값 중 일치하는 인덱스 위치를 찾습니다. 2. 인덱스를 기준으로 왼쪽 서브 트리, 오른쪽 서브 트리를 탐색합니다. 3. 후위 순회이기 때문에 서브 트리 탐색이 끝난 후 루트를 출력합니다. [코드] import sys def solve(root, start, end): for i in range(start, end): i..

문제 보기 [사용한 알고리즘] 크루스칼(kruskal) [문제 접근] 모든 행성은 연결되어 있기 때문에 x, y, z 좌표별로 정렬한 후 각 행성 사이의 거리를 구합니다. 거리를 모두 구한 후 가장 작은 거리부터 하나씩 연결하는 크루스칼 알고리즘을 사용하여 최소 스패닝 트리를 구하였습니다. 만약 정렬을 통해 각 행성 사이의 거리를 구하지 않고 모든 행성 사이의 거리를 구하면 시간 초과가 발생할 것이라 생각합니다. [알고리즘] 1. 행성 좌표를 입력받습니다. 2. x, y, z 좌표별로 각각 정렬한 후 각 행성 사이의 거리를 구합니다. 3. 가장 작은 거리부터 사이클을 확인한 후 연결하는 크루스칼 알고리즘을 사용하여 최소 스패닝 트리를 구합니다. [코드] import sys def find_parent(x..

문제 보기 [사용한 알고리즘] 스택(stack) [문제 접근] 후위 표기식은 중위 표기식과 달리 괄호가 없는 식이기 때문에 연산자들의 우선순위와 스택을 활용하면 구현하고자 하였습니다. [알고리즘] 1. 중위 표기식을 입력받습니다. 2. 첫 번째 문자부터 순서대로 탐색합니다. - 연산자가 아니면 postfix에 더합니다. (postfix -> 최종 식) - '(' 연산자는 s에 삽입합니다. (s -> 연산자 저장 스택) - ')' 연산자는 '(' 연산자를 만날 때까지 스택에 있는 값들을 pop 한 후 postfix에 더합니다. - '+' 혹은 '-' 연산자는 '(' 연산자를 만날 때까지 스택에 있는 값을 pop 한 후 postfix에 더합니다. - '*' 혹은 '/' 연산자는 '*' 혹은 '/' 연산자를 ..

문제 보기 [사용한 알고리즘] 구현 [문제 접근] 1. x, y 범위가 -10억 ~ 10억이고 입력 값의 개수가 최대 10만 개이기 때문에 O(n^2) 시간 복잡도로 구현하면 시간제한 2초를 초과합니다. 따라서 O(n) 시간 복잡도로 문제를 구현하고자 하였습니다. 2. x가 증가하는 순으로 좌표가 주어지기 때문에 기존에 주어진 좌표와 새로 들어온 좌표가 모두 겹치는 경우, x만 겹치는 경우, 둘 다 겹치지 않는 경우 3가지가 존재합니다. 따라서 각각의 경우에 따라서 기존의 좌표 값과 결괏값을 저장하는 변수를 관리하면 O(n) 시간 복잡도로 문제를 구현할 수 있다고 생각하였습니다. [알고리즘] 1. 첫 번째 x, y 좌표를 입력받습니다. 2. 새로 들어온 temp_x, temp_y 좌표와 기존의 좌표의 포..

문제 보기 [사용한 알고리즘] 우선순위 큐(Priority Queue) [문제 접근] 두 개의 heap을 이용하여 중간값을 관리하였습니다. 왼쪽 힙을 left(max heap), 오른쪽 힙을 right(min heap)라고 가정하면 left와 right의 보유 원소 개수(길이)가 같으면 left에 무조건 삽입합니다. 이외에는 right에 삽입합니다. 그리고 만약 left의 가장 큰 값과 right의 가장 작은 값을 비교해서 left의 가장 큰 값이 더 크면 left의 가장 큰 값과 right의 가장 작은 값을 바꿔줍니다. 그러면 right의 가장 큰 값은 중간값이기 때문에 효율적으로 중간값을 관리할 수 있습니다. [알고리즘] 1. 두 개의 heap을 선언합니다. left(max heap), right(m..

문제 보기 [사용한 알고리즘] 구현 [문제 접근] 애벌레가 자라는 날짜 한 줄마다 정보를 업데이트하면 시간 초과가 발생하였다. 따라서 애벌레가 각 날마다 자라는 정도를 모두 더한 후 한 번에 처리하였습니다. [알고리즘] 1. 각 날마다 애벌레가 자라는 정도를 모두 더해서 저장합니다. 2. 나머지 애벌레들의 자라는 정도를 계산합니다. * 제일 왼쪽 아래 칸에서 시작해서 위쪽으로 올라가서 제일 오른쪽에 도착하는 애벌레 증가 정보는 감소하지 않으므로 현재 칸에서 0행에 있는 값 - 1 만큼 현재 칸의 애벌레 크기를 증가시키면 됩니다. [코드] import sys def around_grow(array): for i in range(1, m): for j in range(1, m): array[i][j] += ..