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부터 순회를..

 간단하다고 하지만 생각보다 간단하지 않은 369게임 주어진 숫자를 가지고 map, split, list 함수들을 사용해서 range로 늘어뜨리고, 그 중에서 3, 6, 9가 들어가면 '-' 를 출력하는 문제. python의 문자열, 숫자, 리스트를 잘 다룬다면 쉽게 풀 수 있는 문제인 것 같다. 과거의 나는 숫자로 100의 자리 10의 자리 1의 자리를 구분해서 3, 6, 9를 체크한 후, 해당하는 만큼 '-' 를 출력해서 풀었던 것 같다. 하지만 이번에는 문자열을 list로 split 하여 체크한 후에 포함하는 만큼 개수를 카운팅해서 '-'를 출력 해 보았다. 📌 학습한 내용 1. 문자열에 list함수를 사용하면 단어 단위로 쪼개어 져서 리스트를 형성한다. 2. elif 함수를 사용하면 조건에 맞게..

미래를 보는 원재의 시세차익을 계산해 주는 문제. 처음 문제를 보고 N의 의미가 N개마다 끊어서 미래를 볼 수 있는 줄 알고, N개씩의 시세차익을 합치는 코드를 짰다. 하지만 계속해서 Fail을 당한 후 다시 문제를 꼼꼼히 검토했고, 리스트의 시세차익을 계산해 주는 calPrice() 클래스를 만들어 TestCase마다 시세차익을 계산하는 알고리즘을 구성했다. 📌 학습한 내용 1. 문제를 꼼꼼히 잘 읽어보자. 2. 클래스를 만들어서 사용하면 매우 편리하다. 3. 앞에서부터 했을 때 막히면, 반대로 생각하는 지혜를 가지기! TC = int(input()) def calPrice(Days): MaxNum = Day[-1] # 맨 뒤의 숫자부터 크기 비교 Day.reverse() # 역순으로 바꾼 후 탐색 V..

🎱 파이썬 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)]..