Seongwon Lim

제약 사항 시간 제한 : 2 초 메모리 제한 : 512MB 문제 입력 출력 예제 입력 ABCBA // 예제입력 1 PALINDROME // 예제입력 2 ZZZ // 예제입력 3 예제 출력 4 // 예제 출력 1 10 // 예제 출력 2 -1 // 예제 출력 3 잘못된 접근 방식 s = input() answer = -1 for i in range(len(s)-1): temp = s[i] for j in range(i+1, len(s)): temp += s[j] # 부분 문자열 reverse = temp[::-1] # 부분 문자열을 뒤집은 변수 if len(temp) >= 2 and temp != reverse: answer = max(answer, len(temp)) print(answer) 브루트포스 ..

제약 사항 시간 제한 : 1.5 초 메모리 제한 : 128MB 문제 입력 출력 예제 입력 5 6 9 5 7 4 예제 출력 0 0 2 2 4 잘못된 접근 방식 import sys input = sys.stdin.readline n = int(input()) li = list(map(int, input().rstrip().split())) result = [] for i in range(len(li)-1, -1, -1): temp = li[i] st = [] if i == 0: # 맨 앞의 탑인 경우 result.append(0) else: for j in range(i-1, -1, -1): # 이전 탑들의 높이 탐색 if li[j] > temp and not st: st.append((li[j], j+1)..

서론 이번 글에서는 모든 정점 사이의 최단 경로를 구하는 알고리즘인 플로이드-워셜(Floyd-Warshall) 알고리즘의 개념을 살펴보고 예제를 알고리즘의 동작 원리를 알아보고자 한다. 또한, 파이썬을 통해 해당 알고리즘을 구현하는 방법을 살펴볼 것이다. Floyd-Warshall Algorithm 플로이드 워셜 알고리즘은 그래프(Graph) 상에서 가능한 모든 노드 쌍에 대한 최단 거리를 구하는 알고리즘으로, 최단 경로 알고리즘 (Shortest Path Algorithm) 이라고도 불린다. 특정 정점에서 모든 정점까지의 최단 거리를 구하는 다익스트라(dijkstra) 알고리즘과 다른 점은 다음과 같다. 모든 노드 쌍에 대한 최단 거리를 구할 수 있다. 간선의 가중치가 음의 값을 가질 수 있다. 플로이..

선택 정렬(Selection Sort) 선택 정렬은 n개의 레코드 중에서 최소값을 찾아 첫 번째 위치에 놓고, 나머지 (n-1)개 중에서 다시 최소값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 알고리즘이다. 선택 정렬의 특징은 다음과 같다. 평균과 최악 모두 수행 시간 복잡도는 O(n^2) 이다. 회전을 수행할 때마다 가장 작은 값의 레코드가 맨 앞으로 이동하므로 다음 회전에서는 맨 앞에 있는 레코드는 정렬하지 않는다. 예를 들어 [8, 5, 6, 2, 4] 라는 5의 길이를 가지고 있는 배열이 있다고 가정해보면 1회전이 끝나면 2라는 값은 맨 앞으로 정렬된다. 따라서 2회전 때에는 2번째 부터 정렬 알고리즘을 수행하면 된다. 예제를 통해서 선택 정렬을 이해해보자. 선택 정렬 예제 초기..

버블 정렬 (Bubble Sort) 버블 정렬은 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식이다. 버블 정렬의 특징은 다음과 같다. 계속 정렬 여부를 플래그 비트(f)로 결정한다. 평균과 최악 모두 수행 시간 복잡도는 O(n^2) 이다. 회전을 수행할 때마다 가장 큰 값의 레코드가 맨 뒤로 이동하므로 다음 회전에서는 맨 끝에 있는 레코드는 정렬하지 않는다. 예를 들어 [8, 5, 6, 2, 4] 라는 5의 길이를 가지고 있는 배열이 있다고 가정해보면 1회전이 끝나면 8이라는 값은 맨 뒤로 정렬된다. 따라서 2회전 때에는 길이 5를 n 이라고 했을 때 n-1 번째 까지만 정렬 알고리즘을 수행하면 된다. i 번째와 i+1 번째를 비교했을 ..

삽입 정렬 (Insertion Sort) 삽입 정렬이란 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 알고리즘이다. 삽입 정렬의 특징은 다음과 같다. 두 번째 키와 첫 번째 키를 비교하여 순서대로 나열(1회전)하고, 이어서 세 번째 키를 1,2 번째 키와 비교하여 순서대로 나열(2회전)하고, 계속해서 n번째 키를 앞의 n-1개의 키와 비교하여 알맞은 순서에 삽입하여 정렬하는 알고리즘이다. 평균과 최악 모두 수행 시간 복잡도는 O(n^2) 이다. 예제를 통해서 삽입 정렬을 이해해보자. 삽입 정렬 예제 초기 상태 : [8, 5, 6, 2, 4] 1회전 두 번째 레코드 5를 Key로 지정하여 이전 자료들과 비교한다. Key(5)가 첫 번째 레코드인 8 보다 작으므로, 8을 Key..