분리집합이라는 말을 들었을 때, Disjoint Set이라는 단어가 일단 생각이 났다. 아무리봐도 Intersection이 없는 집합들 이라고 생각할 수 있겠다. 사실 백준에서 문제 하나를 풀고 있었는데, 이거 태그가 분리집합이라서 ... 공부를 해야겠다고 생각하게 된듯. 즉, [1,2,3,4,5,6] 같은 집합이 주어져있을 때, 이들을 어떻게 묶을 것인지?  어떻게 보면 Strongly Connected Component들이 구성되어있는가? 가 되겠다. 먼저 이러한 분리 집합을 생각함에 있어서 Union - Find라는 두개의 function을 통해서 정의된다. 첫번째로, Find (특정 원소가 어디에 소속되어있는지?) def find(parent, x): if parent[x] != x: re..

이번에 사용한 알고리즘들인 Manacher Algorithm, Dijkstra, Floyd-Warshall Algorithm에 대해 정리 해보았습니다. 1. Manacher Algorithm 문자열에서 가장 긴 회문 (Palindrome)을 찾기 위한 알고리즘입니다. 2. Dijkstra Algorithm (데이크스트라 알고리즘) Non-negative weighted graph가 주어져있을 때, 각 Vertices들의 최소 weight 간선을 찾아내는 문제입니다. 3. Floyd - Warshall Algorithm (플로이드 워셜 알고리즘) 2에서의 데이크스트라가 Non-negative만 해당이 되었다면, Floyd Warshall의 경우에는 음의 가중치 또한 허용합니다.

학회 발표 신청을 낸 뒤, 이제 구체적인 결과를 정말 내기 위해 마지막 박차를 가하고 있다보니 ... 문제를 많이 못 풀게 되었는데, 그래도 틈 나는대로 몇몇 문제들을 풀어보았다. 1. Longest Palindromic Substring https://leetcode.com/problems/longest-palindromic-substring/description/ class Solution: def longestPalindrome(self, s: str) -> str: t = '#'.join('^{}$'.format(s)) print(t) n = len(t) P = [0] * n C = R = 0 for i in range (1,n-1): P[i] = (R > i) and min(R-i, P[2*C ..

슬슬 논문 작성과 학회 발표 준비에 바빠지다보니 포스팅이 조금 빈약해진 느낌. 3주차 스터디는 다음과 같은 문제들을 구현해보았다. 1. 연속부분 수열 합의 갯수 https://school.programmers.co.kr/learn/courses/30/lessons/131701 def solution(elements): ans = [] for i in range (0,len(elements)): ans.append(elements[i]) for i in range (0,len(elements)): ans.append(elements[i]) summary = [] for i in range (0,len(elements)): #길이를 indicate for j in range (1,len(elements)+1..

2주차 스터디 내용은 DFS, BFS를 집중적으로 학습했습니다. LG전자 코딩테스트도 겹쳐있었던지라 집중적으로 이문제 저문제 풀어봤던 것 같습니다. 내용 및 설명 추가 예정 1. 백준 - 영역 구하기 from collections import deque M,N,K = map(int,input().split()) A = [[0 for _ in range (0,N)] for _ in range (0,M)] visited = [[False for _ in range (0,N)] for _ in range (0,M)] for i in range (0,K): #벽(색칠된 부분) 체크하기 a = list(map(int,input().split())) for j in range (a[1],a[3]): for k in..

코딩테스트 대비 스터디를 시작하면서, 첫 주차 알고리즘은 완전 탐색(Brute Force). 대표문제로서 선택된 것이 프로그래머스 - 카펫 (Level 2) 1. 카펫 해당 문제 풀이 코드는 이하와 같습니다. #풀이 1 (Yellow 활용) import math def solution1(brown, yellow): a = brown + yellow #전체 타일 갯수 a for i in range (1,int(math.sqrt(a))+1): #a = i * (a//i) = i * b (i 2 / 3,2,3,4 -> 2,3,4 ..... 이후, 만약 set에 의해 생성되는 튜플의 길이가 1이라면 정사각형의 넓이는 n * n 으로 주어지므로 이를 ans에 추가. (혹은 max 함수를 사용하는 것도 좋아보인다...