ekdud 님의 블로그

이번주.. 좀 더 열심히 할 수 있었는데. 아쉬움이 남는 한 주다.코드카타도 매일매일 다 못풀고 ㅜㅠ 갑자기 코드카타 난이도가 확 올라간 느낌이다.아니 어떻게든 돌아가게 만들어놓고 다른 풀이 확인해보면 ㅎㅎ.. 왜 이렇게 할생각을 못했나싶다. 나도 효율적이고 똑똑한 코드 짜고싶어 ..!✔️ 다음주는 일단 백트래킹부터 문제 풀어보고 시작하기 !!!✔️DFS, BFS 문제 풀기

📑  파이썬 Set 자료형• 집합을 구현한 것으로 숫자, 문자, 문자열까지도 포함할 수 있다.• 셋 선언하기:  set이름 = { 원소들 }  또는  = set() 으로 비어있는 set을 선언할 수 있다.• 원소들의 중복을 허용하지 않는다. • 순서가 없다. set자료형을 출력하면 매번 다른 순서로 출력된다.• 슬라이싱과 인덱싱이 불가하다.• set 자료형의 개별 원소에 접근하려면 리스트로 형변환하여 접근해야 한다. [ 메소드 ]• 원소 추가 .add()    여러 개의 원소를 추가하는 경우 .update([ ... , ... , ... ])• 원소 삭제 .remove()  *해당 값이 없는 경우 에러가 발생하므로 에러 발생을 원치 않는다면 .discard() 메소드 사용.• 집합 연산: set자료형의..

📑 하드웨어 기본• 메인보드: 컴퓨터의 부품 및 장치들을 설치하여 연동할 수 있게하는 부품. 제작사마다 모양, 색상 등이 다르지만 비슷함. Desktop / Laptop(노트북) • CPU: Central Processing Unit. 중앙처리장치. 컴퓨터의 두뇌 역할. 명령어를 해석하여 연산을 수행하는 역할. 컴퓨터의 성능에 가장 크게 관여. GPU에 비해 복잡한 연산 수행.*clock - CPU의 처리속도 단위. 석영이 진동하는 진동수에 따라 CPU가 동작. '오버클락'한다는 것은 기존의 컴퓨터의 속도를 강제로 빠르게하는 기술. CPU의 수명이 줄어들게 될 수 있다. • GPU: 그래픽처리장치. 그래픽 연산을 하기 위해 병렬처리를 할 수 있도록 설계되어 있음. GPU에는 코어가 수백,수천 개 존재...

시간 복잡도cost - 시간자원(CPU), 공간자원(Memory) 점근적 복잡도 f(n) : 입력크기 n에 대한 알고리즘의 시간 복잡도(성능). 상수시간 복잡도 O(1) - 입력값이 아무리 커도 실행시간이 일정한 최고의 알고리즘. 단, 상수시간이 매우 큰 경우에는 의미가 없다..로그시간 복잡도 O(log) - 매우 큰 값에도 영향을 받지 않는다.선형시간 복잡도 O(n) - 입력값에 비례한다. 정렬되지 않은 리스트에서 최대, 최소 등을 찾는 경우가 이에 해당한다.O(nlogn) - 병합정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘.O(n^2) - 버블 정렬 같은 비효율적인 정렬 알고리즘.(nested loop에 해당)O(2^n) - n^2이랑 비교할 수 없을만큼.. 느리다.O(n!) - 답은 나와도 사용..

🤍 트리 구조 1) 직접 클래스를 구현하기 2) 배열로 표현하기: 완전 이진 트리는 왼쪽부터 데이터가 쌓이므로 이를 순서대로 배열에 쌓으면서 표현하는 것. (BFS 순으로 배열에 넣는다) - 완전 이진 트리(단, 각 레벨에 노드가 꽉 차있다고 가정할 때): 레벨이 k이, 각 레벨에 최대로 들어갈 수 있는 노드의 개수는 2^k개.즉, 높이가 h일 때 최대 노드의 개수(N)는 2^(h+1) - 1 개이다. *트리의 높이는 레벨 0(루트 노드)부터 센다.N = 2^(h+1) - 1 일 때,  h = log₂(N=1) - 1  완전 이진트리 노드의 경우에 이렇고,이진 트리의 높이는 최대 O(log(N))이다.  이진 트리 구현# 트리 구현from binarytree.structures import TreeN..

🤍백트래킹: 필요없는 경우를 가지치기(pruning)함으로써 시간복잡도를 줄이는 방법.N-Queens 문제 The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order. Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' bo..

이번주는 강의와 알고리즘 코딩 문제 풀이 위주로 진행되었다. 스택과 큐, 그리고 해시테이블, 최대 힙을 구현해보았고 이를 사용해 코드카타 문제를 풀어보았다. 아직 연결리스트 부분은.. 제대로 구현하지 못해서 복습이 필요하다.  그리고 배열과 리스트가 계속 헷갈렸는데, 배열(array)와 연결리스트가 리스트에 속하고 배열은 접근이 쉽고 삽입이 어려운 반면, 연결리스트는 접근이 어렵고 삽입이 쉽다는 차이가 있다는 것을 배웠다. (시간복잡도 측면에서 큰 차이가 있어 목적에 맞게 사용하면 된다.) 그리고 흔히 파이썬에서 리스트라고 부르는 것이 배열이라는 것도 알게되었는데 구글링해서 찾은 정보와 강의자료의 정보가 좀 차이가 있어 헷갈렸다. 일단 파이썬에서의 리스트 = 배열이라 생각하면 될 것 같다. 다른 언어에서..

🤍DFS(Depth First Search): 깊이 우선 탐색. 노드를 방문하고 깊이 우선으로 인접한 노드를 방문한다. 그리고 그 노드에서 또다시 깊이 우선으로 인접한 노드를 방문한다. 이 과정을 반복하여 더 이상 갈 곳이 없게 되면 다른 방향으로 다시 탐색한다. *방문했던 노드는 다시 방문하지 않는다. DFS 구현1. 재귀로 구현 - 왼쪽부터 탐색재귀; 반복적으로 발생하는 일과 종료 조건(끝까지 가서 더이상 방문할 자식이 없으면 종료)을 알아야 한다.2. 스택으로 구현 - 오른쪽부터 탐색 def dfs_recursive(node, visited): # 재귀적으로 구현 # 방문처리 visited.append(node) # 인접 노드 방문 for adj in graph[node]: ..

🤍 연결리스트와 배열의 차이 리스트(list)는 선형적으로(순서가 존재한다는 뜻) 값들을 가지고 있는 자료구조로, 배열(array)과 연결리스트(linked list)로 나누어진다.  •  배열은 파이썬의 리스트로, 접근이 쉽고 삽입, 삭제가 어렵다. 접근에 O(1), 삽입/삭제에 O(n)이 걸림. 연결리스트는 직접 구현해야하며 접근이 어렵고 삽입, 삭제가 쉽다. 접근에 O(n), 삽입/삭제에 O(1) 소요.연결 리스트는 비록 랜덤 엑세스는 불가하지만 삽입/삭제 연산의 용이함은 스택, 큐, 덱 등의 기본적인 자료구조를 구현하는 데 많은 도움이 된다.* 랜덤 액세스: 특정 인덱스의 값을 O(1)만에 참조하는 것. 연결리스트는 k번째 값에 접근하는 데 O(k)만큼 걸림.  연결리스트 구현class List..

🤍힙: 최대힙과 최소힙이 있으며, 데이터에서 최대값 또는 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리이다.*완전 이진 트리: 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있다. 최대힙: Max heap. 항상 큰 값이 상위 레벨에 있는 자료구조(부모노드 값 > 자식노드 값)로, 최대값을 빠르게 구할 수 있다. BST(이진 탐색 트리)와 다르게 좌우 자식의 위치는 대소관계와 상관이 없다.  계산의 편의를 위해 인덱스를 1부터 사용.=> parent: x, left: 2x, right: 2x+1 1. 맨 마지막에 원소를 넣는다.2. 부모노드와 비교한다.3. 부모노드보다 새로운 원소가 더 크다면 둘의 자리를 변경한다.4. 과정 2,3을 가..