TopCode

학습 내용 자료구조 중 트리(Tree) 구조의 개념 이해 이진 트리와 이진 탐색트리 Python 링크드 리스트 생성에 이진 탐색 트리 적용하기 🌲 대표적인 자료 구조 트리(Tree) 트리구조는 성능도 좋고, 많이 사용하는 자료구조입니다. node라는 개념으로 1차원적인 리스트 라는 배열의 개념을 확장한 느낌이 드는 데요. node와 branch를 이용해서, 마치 나무가 뿌리를 내린듯한 구조로 탐색 알고리즘 구현을 위해 많이 사용됩니다. 트리(Tree) 관련 용어 정리 Node: 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함) Root Node: 트리 맨 위에 있는 노드 Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노..

학습 내용 Hash Table의 충돌을 개선하기 위한 공간 확대 SHA-1, SHA-256 을 사용하여 충돌을 개선하기 Hash 자료구조의 시간복잡도 계산해보기 📘 해쉬 테이블의 빈번한 충돌을 지우기 위한 방법 해쉬 테이블은 잘 활용하면 속도도 매우 빠르고, 효율적인 자료구조를 구축할 수 있습니다. 하지만 해쉬 테이블 내의 충돌에 대비하지 않으면 매우 비효율적으로 변할 수 있습니다. 충돌을 줄이기 위해서는 일반적으로 공간을 늘리는 방법과 안정적인 해쉬값을 생성하는 방법이 있습니다. 해쉬 함수 재정의 및 저장공간 확대 해쉬 테이블 내 충돌이 발생하는 이유는 구축방식에 따라 다르겠지만, 같은 주소값을 가지는 값들이 서로 충돌하여 발생하는 문제가 큽니다. 따라서 일반적으로는 해쉬 테이블의 공간을 충분히 확보하..

학습내용 Hash Table의 단점 중 하나인 충돌 문제를 Linear Probing 기법으로 해결하기 제한된 Hash Table의 저장공간 활용하기 🧨 저장공간 충돌을 막아주는 Linear Probing 기법 해쉬 테이블 자료구조를 사용하다 보면, 같은 주소값을 가진 데이터들로 인해 충돌문제가 발생하곤 합니다. 이때 Chaining 기법을 활용해서 저장공간 외의 공간을 활용할 수 도 있는 데요. 상황에 따라 한정된 저장 공간이 주어진 상황속에서는 Linear Probing 기법을 적용할 수 있습니다. Linear Probing 기법은 '폐쇄 해싱' 또는 'Close Hashing' 기법 중 하나로, 충돌이 일어나면 해당 hash address의 다음 address부터 순회를..

🌲 트리(Tree) 개념 트리는 비선형 구조로 원소들 간에 1:N 관계를 가지는 자료구조입니다. 원소들 간에 계층 관계를 가지며 상위 원소에서 하위원소로 내려가면서 확장되는 트리(나무) 모양의 구조입니다. 용어 루트(root) : 노드 중 최상위 노드 노드(node) : 트리의 원소 간선(edge) : 노드를 연결하는 선, 부모 노드와 자식 노드를 연결 루트 노드(root node) : 트리의 시작 노드(부모가 없는 노드) 잎 노드(leaf node) : 단말 노드(자식이 없는 노드) 차수(degree) : 노드의 차수는 노드에 연결된 자식 노드의 수 단말 노드(리프 노드) : 차수가 0인 노드, 자식 노드가 없는 노드 노드의 높이 : 루트에서 노드에 이르는 간선의 수. 노드의 레벨 트리의 높이 : 트리..

🎱 파이썬 SWEA-Problem[D-2] 1974.스도쿠 검증 주어진 9X9 배열을 가지고 스도쿠 검증을 합니다. 올바른 스도쿠 퍼즐일 경우 1을, 아닐경우 0을 출력합니다. 💡 아이디어 가로/세로, 블럭을 구분해서 카운팅정렬을 사용하여 스도쿠 퍼즐을 검증합니다. 가로와 세로는 하나의 for문으로 검증가능하여 한번에 검사하고, 블럭은 새로운 for문을 이용합니다. 검증의 용이성을 위해 sdoku 함수를 만들어 리스트와 num(1~9)를 입력받아 사용합니다. 🎲 파이썬 코드 ※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다. > 문제보기 T = int(input()) # 스도쿠 검사하는 함수 def sdoku(list, nums): check = [0 for _ in range(9)]..

🔎 DFS DFS(Depth-First Search)는 그래프의 깊은 부분부터 우선적으로 탐색하는 알고리즘 노드와 간선으로 이루어진 그래프 구조에서 시작점을 기준으로 인접 노드의 깊은 부분부터 탐색하는 알고리즘 입니다. DFS는 스택자료구조를 이용하여 인접 노드의 방문여부를 체크하고 모든 노드를 방문한 즉, 노드의 깊은부분에 도달하면 스택에서 상단 노드를 pop 하는 방식으로 목표 노드를 탐색합니다.메모리 효율적인 부분에서 그래프는 인접리스트 방식이 더 우월하지만, 특정한 두 노드의 연결정보를 얻기 위해서는 인접행렬방식이 더욱 유리합니다. 🔍 BFS BFS(Breadth First Search)는 너비우선탐색으로 가까운 노드부터 탐색하는 알고리즘 너비우선탐색인 BFS는 DFS와 다르게 큐(Queue)자료..

🚛 파이썬 SW문제해결 기본 - 큐(Queue) 주어진 N개의 수를 다음과 같은 조건을 통해 8가지 암호를 만드는 문제입니다. 조건은 주어진 N개의 수를 큐(Queue)라고 생각하고 맨앞의 수에서 1~5를 순서대로 뺀 후 큐의 맨 뒤에 append하는 싸이클입니다. 💡 아이디어 큐, 8개의 숫자 중 첫번째 숫자를 1~5씩 마이너스하는 싸이클을 돌며 8개의 한자리 수가 남을 때까지 반복하고 맨 마지막 자리가 0이면 종료 반복횟수가 정해지지 않았으므로 while을 사용해서 반복. 맨앞자리가 계속해서 뒤로 가므로 슬라이싱을 이용하여 배열을 다시 만들어줌. 맨 뒷자리가 0이 되었을때 break로 탈출. while문 탈출할때 for문한번 나오고 또 나와야 하므로 check라는 종료조건 생성. 🎲 파이썬 코드 ※ ..

🚛 파이썬 SW 문제해결 기본 - Stack2 주어진 계산식을 1) 후위표기식으로 변경하고 2) 그 표기식을 계산하는 문제입니다. 연산자는 +, * 두 가지이고, 괄호의 유효성여부는 항상 옳은 경우만 주어집니다. 💡 아이디어 문제 그대로 후위표기식으로 주어진 문자열을 변경하고, 계산해주는 함수를 만들었습니다. 후위표기식 변경 시 숫자는 그대로 append하고 문자는 '(', '+', '*', ')' 에 대한 조건을 각각 만들어 스택에서 연산자 우선순위를 반영하는 코드를 만들었습니다. 후위표기식으로 바꿔서 계산하기, +, *, (,) 괄호는 항상 유효. 피연산자 0~9 + : 괄호가 없으면 스택에 있는 것들 pop, 괄호있으면 append * : 괄호가 없으면 스택에 있는 '*' 모두 pop, 괄호있으면 ..

🚛 파이썬 SW문제해결 기본 - Stack2 가위바위보할 상대를 구할 때 주어진 카드 순서를 절반씩 나누어 토너먼트 형태로 시합 대진을 구성하는 문제입니다. 최종적으로 상대가 나눠지게 되면 가위바위보를 진행하고 최종적으로 승자를 가려내어 출력합니다. 💡 아이디어 반복되는 작업을 함수와 재귀를 활용해서 해결합니다. 범위를 둘로 나눌때 구간을 잘 나누어 주어야 겹치는 부분이 발생하지 않습니다. 🎲 파이썬 코드 ※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다. # TODO 4880 토너먼트 가위바위보 def game(i, j): # 종료조건..점점 줄어들기 때문에 자신과 같아지면 i 출력 if i == j: return i # 게임을 시키는 범위. # 범위를 둘로 나눠서 재귀를 돌림.. ..

🚛 파이썬 SW문제해결 기본 - Stack2 델타값과 스택을 활용해서 상하좌우 4방향을 체크하는 문제입니다. 델타값을 이용해서 4방향을 체크할때에 배열의 범위를 벗어나지 않도록 체크하는 것이 중요합니다. 💡 아이디어 DFS 알고리즘을 기반으로 미로의 시작점에서 부터 4방향을 체크해가며 목적지를 찾아나가는 방식으로 코드를 구성했습니다. Stack에는 이동가능한 곳들을 담아주고 방문한 곳은 기본 배열에서 0으로 초기화 되어있던 것을 1로 바꾸어줍니다. 계속해서 이동하며 목적지인 3에 도착하면 break하여 반복문을 빠져나옵니다. 🎲 파이썬 코드 ※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다. """ - 문제 미로 : 2(출발), 3(도착), 0(통로), 1(벽) 도착할 수 있으면 1 ..

🚛 파이썬 SW문제해결 기본 - Stack2 스택을 활용한 후입표기법 계산기 만들기 문제입니다. 후입표기법으로 주어진 문자열을 계산만 하면 되는 문제이기 때문에 크게 어렵지 않은 문제였습니다. 💡 아이디어 숫자와 문자열을 구분하는 isdigit, isalpha 메소드를 활용합니다. 전체적으로 숫자일때와 문자열일때를 구분하고 문자열안에서는 '.'를 기준으로 조건문으로 나눠주었습니다. 💻 파이썬 코드 ※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다. T = int(input()) for tc in range(1, T+1): lst = list(map(str, input().split())) Stack = [] for i in range(len(lst)): # 숫자일 경우.. if lst..