All Good

전체 글 - Table of Contents332

⛆ Flood Fill intro⛆ 플러드 필(Flood Fill) 알고리즘 이란, 주어진 2차원 그래프에서 연결영역의 개수 및, 각 연결영역의 연결 노드 개수를 구하는 알고리즘이다. 즉, 플러드 필은 DFS / BFS 그래프 순회 알고리즘을 응용한 알고리즘으로, 주어진 2차원 배열에서 연결 영역 관련 문제를 풀 때 사용된다.  ⛆ 대표적인 케이스로, 연결 영역 개수 구하기, 가장 큰 영역 면적 구하기, 각 연결 영역 내의 노드 개수 구하기 등등이 나온다. ⛆ 시간 복잡도는 traverse할 2차원 그래프의 행 개수가 N이고 열 개수가 M이라면 O(NM), 공간 복잡도는 O(NM)이다.  1. 연결 영역 개수 구하기ex) BOJ 4963 S2 Q. 1과 0으로만 이루어진 2d array에서 1로만 이루어진 연결 영역, 즉 섬의.. Computer Science/Algorithms 2024. 5. 19.
★BFS&DFS Upper-Intermediate I - 16 Solved★ ☝️ 중상급의 BFS/DFS 유형은 그래프 연결 요소 / 연결 요소 내의 노드 개수 / 최단 거리(Easy) 3개의 알고리즘으로 분류할 수 있다.★ 11724 연결 요소의 개수 ★☝️ DFSimport sysinput=sys.stdin.readlinesys.setrecursionlimit(10000)N,M=map(int,input().split())#dfsdef dfs(graph,start,visited): visited[start] = True for node in graph[start]: if not visited[node]: dfs(graph,node,visited)#graphgraph=[[] for _ in range(N+1)]for _ in range(.. BOJ/🥈 2024. 5. 12.
🌸Model Analysis - Convolution / number of Pooling params + shape size ① case 1# Define the modelmodel = tf.keras.models.Sequential([ # Add convolutions and max pooling tf.keras.layers.Conv2D(32, (3,3), activation='relu', input_shape=(28, 28, 1)), tf.keras.layers.MaxPooling2D(2, 2), tf.keras.layers.Conv2D(32, (3,3), activation='relu'), tf.keras.layers.MaxPooling2D(2,2), # Add the same layers as before .. Deep Learning/Fundamentals 2024. 5. 12.
★Math & Geometry Advanced I - 2 Solved★ ★ 1011 Fly me to the Alpha Centauri ★import sysinput=sys.stdin.readlinefor _ in range(int(input())): x,y=map(int,input().split()) diff=y-x closest_root=int(diff**(1/2)) if diff == (closest_root**2): print(closest_root*2-1) elif (diff-(closest_root**2)) 🍋 kn은 kn-1 / kn / kn+1 중 한 개만 가능 + 맨 앞과 맨 뒤의 거리 step은 1만 가능하다는 조건 하에 수학 규칙성을 찾는 문제→ y-x를 diff라고 한다면, 중복된 step 간격 없이 오름차순 -.. BOJ/🥇 2024. 4. 27.
🏘️Euler Sieve intro 🏘️ 소수 판정법으로 유명한 에라토스테네스의 체(Sieve of Eratosthenes)를 개선한 '오일러의 체(Euler Sieve)'에 대해서 소개한다. 에라토스테네스의 체는 소수 판별 시간 복잡도가 O(nloglogn)임이 알려져 있고, 이를 개선한 오일러의 체 시간 복잡도는 단 선형 시간만에 O(n)으로 판별이 가능하다. 🏘️ 에라토스테네스의 체의 시간 복잡도가 선형 시간(O(n))이 될 수 없는 이유는 합성수 210을 들면 쉽게 알 수 있다. 210은 2x3x5x7로 나타낼 수 있는데, 에라토스테네스의 체에 의해서는 2x3x5x7 / 2x3x5x7 / 2x3x5x7 / 2x3x5x7 와 같이 각각 빨간색 숫자일 때 210이 합성수임을 중복해서 알려주고 있다. 🏘️ 따라서, 이를 단 한.. Computer Science/Algorithms 2024. 4. 21.
🥐Counting Sort orders① 정렬할 데이터를 준비한다.7 5 9 0 3 1 6 2 9 1 4 8 0 5 2○ 이 때, 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있는 list를 생성 ○ ② 왼쪽부터 데이터를 하나씩 확인하며 데이터의 값과 동일한 index의 데이터를 1씩 증가시킨다. ③ 오름차순 결과를 확인하기 위해 각 원소의 계수가 저장된 list를 왼쪽 끝부터 돌려 해당 데이터의 값만큼 반복해 인덱스를 출력한다. - 출력 결과 -0 0 1 1 2 2 3 4 5 5 6 7 8 9 9about Counting Sort🥐 특정한 조건이 부합할 때만 사용할 수 있으나 매우 빠르게 동작하는 정렬 알고리즘. (*특정한 조건: 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용) 🥐 .. Computer Science/Algorithms 2024. 4. 17.
🗼Tower of Hanoi intro🗼 유명한 '하노이의 탑' 알고리즘에 대해 소개한다. 3개의 기둥이 있고, 다양한 크기의 n개의 원판(원판의 크기는 모두 다르다)이 존재한다. 퍼즐을 시작하기 전에는 한 기둥에 n개의 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다. 아래 3가지 조건을 만족 시키면서 다른 기둥으로 옮겨서 다시 쌓는 퍼즐이다. ① 한 번에 1개의 원판만 옮길 수 있다.② 가장 위에 있는 원판만 이동할 수 있다.③ 큰 원판이 작은 원판 위에 있어서는 안된다. 이 때, 최소 이동횟수로 맨 왼쪽 기둥에서 맨 오른쪽 기둥으로 n개의 원판을 순서에 맞추어서 쌓아주면 된다example demo (n=3)🗼 n=3일 때 Hanoi Tower를 쌓아보자!🗼 Hanoi Tower 문제는 크게 아래 3가지 순서로 진행된다.. Computer Science/Algorithms 2024. 4. 9.
➕Merge Sort orders ★ 원소를 개별적으로 나누고, 병합하는 두 과정이 수반되는 정렬 ★ (아래 과정 ②는 divide / ③은 merge) (따라서 merge sort는 나누고 + 합치고 두 과정) ① 정렬할 데이터 준비 (오름차순 가정) 7 3 1 5 6 4 2 ② 본격적인 merge sort를 하기에 앞서서 각각 원소가 1개씩만 있게끔 recursive하게 array를 절반으로 쪼갠다 (recursion 적용) 7 3 1 | 5 6 4 2 → 7 | 3 1 | 5 6 | 4 2 → 7 | 3 | 1 | 5 | 6 | 4 | 2 ③-1) 두 개씩 쪼개는 루트의 역 방향으로 작은 원소를 앞에, 큰 원소를 뒤에 놓는다. (1) 3 1 에서 3 | 1로 쪼갰으므로 1 3으로 정렬 (2) 5 6 에서 5 | 6으로 .. Computer Science/Algorithms 2024. 4. 6.
★Implementation&Simluation Upper-Advanced I - 1 Solved★ ★ 19237 어른 상어 ★ import sysinput=sys.stdin.readlinefrom collections import dequeN,M,k=map(int,input().split()) #NxNsize / M sharks / smell limit ktrace=[]smell=[[0]*N for _ in range(N)]sharks=deque()shark_ds_priorities=[]#shark_dsdx,dy=['?',-1,1,0,0],['?',0,0,-1,1]num_of_sharks=Mfor i in range(N): l=list(map(int,input().split())) trace.append(l) for j in range(N): if l[j] != 0: .. BOJ/🥇 2024. 3. 3.
★Stack & Queue & Deque Advanced I - 3 Solved★ ★ 9935 문자열 폭발 ★ import sysinput=sys.stdin.readlines=list(input().rstrip())explode=list(input().rstrip())explode_length=len(explode)ans=[]for x in range(len(s)): ans.append(s[x]) if s[x] == explode[-1]: if explode_length 😮 폭발 문자열의 길이가 최대 36이므로, 문자열을 계속 ans에 넣다가 맨 마지막 폭발 문자열이 들어갈 경우, 앞선 들어간 문자열이 폭발 문자열이 맞다면 pop() 연산으로 빠르게 삭제. 그리고 계속 update. stack에 넣고 빼는 연산 O(1)을 활용해 시간 복잡도 최대 O(N)★ 1.. BOJ/🥇 2024. 2. 24.
🍡 Two Pointers intro🍡 two pointers란 배열에서 원래 이중 for문으로 O(N^2)에 처리되는 작업을 2개 포인터의 움직임으로 O(N)에 해결하는 알고리즘이다. 이중 for문으로 돌리면 i=0일때의 정보를 i=1일 때 전혀 쓰이지 않지만, two pointers는 i=0일 때의 작업이 i=1일 때의 작업에 쓰인다. 과거 정보를 기억한 채로 효율적이게 index를 O(N)으로 움직이는 알고리즘. 이분탐색 문제를 투포인터로도 풀 수 있는 경우가 많고, 그 반대도 많다. two pointers는 O(N)으로, 각각의 모든 case를 일일이 점검할 필요 없이, 일부 case는 점프하는 경우만 풀이가 가능.explanation🍡 위와 같은 배열이 있다고 할 때, a일때 b~i를 돌고 / b일 때 c~i를 도는 .. Computer Science/Algorithms 2024. 2. 11.
★Two-Pointers Advanced I - 10 Solved★ ★ 15961 회전 초밥 ★ import sysinput=sys.stdin.readlinefrom collections import defaultdictN,d,k,c=map(int,input().split())kinds=[int(input()) for _ in range(N)]y,ans,cnt,freq=0,0,0,defaultdict(int)for x in range(N): while cnt 🧦 x와 y 투 포인터 모두 첫 초밥부터 시작하되, k개의 묶음마다 진행하므로(슬라이딩 윈도우 포스팅 참조), x가 전체 초밥 x(1)부터 x(8)까지 움직일 때 y의 끝은 y(1) 부터 y(11)까지 (k=4일 경우) 움직인다 / dictionary 활용해 freq로 종류 개수 update하며 freq.ke.. BOJ/🥇 2024. 2. 11.

티스토리툴바