본문 바로가기

분류 전체보기168

210124_TIL 🍎 오늘 한 일 ✔️ DFS, BFS, 백트래킹 알아보기 자료 구조 중 트리에 대해 배우면서 주로 DFS(깊이 우선 탐색)에만 집중해서 배웠는데, BFS(너비 우선 탐색)에 대해서도 궁금해져서 찾아봤다. 깊이 우선 탐색 현재 노드에서 갈 수 있는 곳까지 최대한 최대한 깊이 가보는 방법이고, 스택이나 재귀로 구현할 수 있다. 경로마다 가중치나 특징이 있을 때 주로 쓴다고 한다. 반면 너비 우선 탐색은 현재 노드에서 가까운 곳부터 탐색하면서 최대한 넓게 가보는 방법으로 큐로 구현할 수 있다. 보통 최단경로를 찾을 때 쓴다고 한다. 그리고 웹페이지 크롤링이나 가비지 컬렉션에도 이 BFS 방식이 사용된다고 하는데 검색속도 자체가 DFS보다 빨라서 실시간에 적합하기 때문인 것 같다는 생각이 들었다. 🍎 기억할 것.. 2021. 1. 25.
DFS(깊이우선탐색) / BFS(너비우선탐색) 그래프를 탐색하는 방법에 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 두 가지가 있다. 말 그대로 '깊이'를 우선시해서 탐색을 하는지, '너비'를 우선시해서 탐색하는 지에 차이가 있다. 아래 그림을 보며 어떻게 달라지는지 한번 비교해보자! DFS (Depth-First Search, 깊이 우선 탐색) 우선 DFS는 기본적으로 최대한 깊이 내려간 뒤에, 더 이상 갈 곳이 없을 때 옆으로 이동하는 탐색 방식이다. 스택(Stack)이나 재귀(Recurse)를 이용해서 구현 가능하다. 스택으로 구현할 때는 모든 노드가 중복없이 딱 한 번씩만 담겨야 하고, 재귀로 구현할 때도 노드 방문 여부를 반드시 체크해서 무한재귀에 빠지지 않게 주의해야 한다. DFS는 모든 노드를 방문하고자 할 때 주로 사용한다. 탐.. 2021. 1. 24.
210123_TIL 🍎오늘 한 일 ✔️ Data Structure 복습 데이터 자료 구조들을 한번씩 다시 그려보고, 관련된 socrative 문제들 중 헷갈렸거나 새로 배운 개념들을 정리했다. 시간 복잡도와 각각의 장단점에 초점을 맞춰 복습했다. ✔️ Sprint 회고 기록해두기 사실 지난 주동안 새로 배운 것도 많고 그날그날 배운걸 정리하기에도 시간이 빠듯해서 지지난주에 했던 포켓몬 게임을 만들었던 Sprint에 대한 기록을 해두지 못하고 넘어갔었다. 느낀 점도 그렇고 새로 알게된 것들을 잊기 전에 정리해두자는 마음으로 기획부터 구현과정, 새로 배운 기능에 대해 다시한번 복습하며 기록했다. 🍎 기억할 것 ✔️ z-index 어느 객체가 앞으로 나오고, 뒤에 나올지 배치 순서를 결정하는 CSS 속성 ✔️ pageX, pag.. 2021. 1. 24.
포켓몬 게임 만들기 (Javascript, HTML, CSS) 한 줄 소개 🕹 포켓볼을 주워 포켓몬을 잡아 경험치를 쌓고, 레벨을 올리는 게임이다. 주요 기능 1. 로그인 화면 입력한 아이디로 게임을 시작할 수 있다. 아이디는 세 글자 이상으로 지정해야한다. 유효성 검사를 통해 글자수를 확인해 세글자 미만일 경우 입력창이 빨간색으로 바뀌며 다시 입력하라는 피드백을 보낸다. 2. 레벨에 따른 테마 변경 & 경험치 얻는 TIP 일정한 경험치가 쌓이면 레벨이 올라가고, 레벨에 따라 테마가 풀 → 바다 → 숲으로 배경과 포켓몬 타입이 바뀌게 된다. 경험치는 포켓몬을 잡아야 올라간다. TIP 1. 포켓몬 포켓몬이 움직이는 속도는 랜덤하게 지정되는데, 경험치를 속도에 비례하게 증가하도록 설정해둬서 빠른 포켓몬을 잡을수록 더 많은 경험치를 얻을 수 있다. TIP 2. 포켓볼 포.. 2021. 1. 23.
210122_TIL (시간복잡도, 자료구조 복습) 🍎 오늘 한 일 ✔️ Big-O 표기법 & 자료구조 연관지어 생각해보기 빅오(Big-O) 표기법은 그냥 알고리즘이 돌아가는 최악의 시간이고, 상수..지수.. 등이 있다는 것, 그리고 대략 어떤 코드가 어느정도의 시간이 걸리는 구나 정도로만 알고 있었다. 빅오 표기법에 대해 좀 더 깊게 다루는 세션을 들으면서 자료구조와 어떻게 연관되는지도 자세히 배워 전에 블로깅 해뒀던 글에 추가했고, n^3의 시간도 빅오로 표시하면 n^2로 취급한다는 것, 그리고 코딩테스트 문제를 풀 때 시간복잡도에 대한 조건을 보고 어떤 자료구조를 써서 풀 수 있는 문제인지 역으로 힌트를 얻을 수 있다는 것도 알게 되었다. ✔️ Data Structure 복습 이번 주 동안 배웠던 자료구조들(스택, 큐, 연결리스트 ,해시테이블, 그래.. 2021. 1. 23.
210121_TIL (자료구조 - 트리, 이진검색트리) 🍎 오늘 한 일 ✔️ Graph, Tree, Binary Search Tree 메서드 작성해보기 오늘도 페어분과 Graph, Tree, Binary Search Tree 자료구조들의 메서드들을 코드로 작성해봤다. 세 가지 구조 모두 기본적으로 노드(node)라고 하는 요소들과 노드와 노드를 연결하는 간선(edge)으로 구성되기 때문에 비슷한 느낌이 있었다. 그래프 자료구조는 방향성이 존재하지 않는 무방향 그래프를 기준으로 해서 비교적 쉽게 해결했던 것 같은데, 이진 검색 트리는 순서나 방향이 정해져 있어서 가장 시간이 많이 걸렸다. 그래도 무엇보다 구조상 재귀를 사용했어야 했는데, 재귀가 실행되는 모습이 조금씩 머리속에 상상이 되기 시작했다는게 제일 기뻤다..ㅠㅠ ✔️ 자료구조 블로깅 어제 공부했던 연결.. 2021. 1. 22.
Data Structure(5) Tree(트리), Binary Search Tree(이진검색트리) Tree (트리) 트리는 노드(node)들을 선(edge)으로 연결한 계층형 자료구조이다. 제일 위에 root(뿌리) 노드 하나가 있고, 그 아래 나머지 자식 노드들이 선으로 연결되고 또 연결되는 구조이다. 나무를 거꾸로 한 모양같다고 해서 트리라는 이름이 붙여졌다고 한다. 관련 용어 루트노드(root node) : 최상위 노드 리프노드(leaf node) : 자식이 없는 노드 부모 노드(parent node) : 노드에 연결된 한단계 상위 레벨 노드 자식노드(child node) : 서브트리의 루트노드들 ex. A의 자식 : B, C 형제노드(sibling) : 같은 부모 + 같은 depth에 있는 노드들 노드의 차수 : 한 노드의 서브트리의 수 트리의 차수 : 트리노드 차수들 중 최대 차수 트리의 높.. 2021. 1. 22.
Data Structure(4) Graph(그래프) Graph (그래프) Graph(그래프)는 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조이다. 지하철 노선도처럼 서로 연결된 데이터들이 어떤 관계인 지 표시할 때 주로 사용한다. let subway = { '교대': ['동대문운동장','사당','충무로'], '동대문운동장': ['교대','을지로3가','충무로'], '사당': ['교대','서울역', '신도림'], '서울역': ['사당','시청','신도림','충무로'], ...} Graph 종류 그래프는 방향성을 가졌는지 여부에 따라 방향 그래프(Directed Graph), 무방향 그래프(Undirected Graph)로 구분할 수 있다. 1. 방향 그래프(Directed Graph) 방향 그래프는 말 그대로 방향을 나타내는 화살표가 있는 그래.. 2021. 1. 22.
Data Structure(3) Hash Table(해시 테이블) Hash Table (해시 테이블) 해시 테이블은 { 키(key) : 값(value) } 쌍을 저장하고 있는 자료 구조이다. 해시 테이블은 키를 저장할 때에 메모리 공간을 덜 사용할 수 있도록, 키(key)를 '해시 함수'(Hash function)라는 함수를 통해 특정 숫자값의 인덱스(index)로 변환한다. 해시 테이블은 필요할 때에만 메모리 크기를 늘리고, 가능한 작은 크기를 유지한다. 해시테이블 : 키(key) → 해시 함수(Hash function) → 인덱스(index)로 변환해 저장하는 자료구조! 관련 용어 키(key) : 원래의 데이터 값(해시 함수 입력 전) 값(value) : 최종 저장되는 값 해싱(hashing) : key → index로 바꾸는 과정 해시함수(hash function.. 2021. 1. 21.
Data Structure(2) Linked List (연결 리스트) Linked List (연결 리스트) 우선 List(리스트)는 데이터에 순서를 매겨둔 자료구조이다. 데이터들이 순서대로 쭉 늘어진 모양을 하고있다. 아직까지 이 데이터들은 차례대로 줄을 서고 있을 뿐 서로에 대해 모르는 상태이다. Linked List(연결 리스트)는 데이터들이 연락처를 주고받아 자기 뒤에있는 사람에게 연락을 할 수 있게 된 상태이다. 대신 누군가를 건너뛰거나 뒤를 돌아서 앞 사람에게 연락을 할 수는 없다. 오직 자기 뒷사람에게만 연락할 수 있다! 조금만 더 자세히 살펴보자. 연결 리스트에 일렬로 연결된 데이터들을 각각 노드(node)라고 한다. 그리고 이 노드들은 각각 1) 데이터(data)와 2) 다음 노드 정보(next)를 갖는다. ✔️ 노드(node) = 데이터(data) + 다음.. 2021. 1. 21.
210120_TIL (자료구조 - 해시테이블, 그래프) 🍎 오늘 배운 것 ✔️ 해시테이블 (자료구조) 해시 테이블의 메서드 중 삽입, 삭제, 리사이징을 하는 메서드들을 페어분과 직접 코드로 작성해봤다. 처음에 해시테이블의 전반적인 구조를 생각하지 않고 무작정 코드를 작성하려해서 자꾸 오류가 났는데, 잠시 리프레시할 시간을 갖고 구조를 그림으로 그려보니 조금씩 감이 잡히기 시작했던 것 같다. 특히 bucket의 존재를 잊고있어서,, 많이 해맸던 것 같다. 통과는 됐지만 왜인지 잘 이해가 가지 않아서 초기화하고 처음부터 다시 작성해보니까 숲을 봤어야 했는데 나무를 보고있었다는걸 깨닫기도 했다. 자료구조는 꼭 그림으로 하나씩 그려보자..! ✔️ 그래프 (자료구조) 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조인 그래프(Graph)에 대해 공부했다. 그.. 2021. 1. 21.
210119_TIL (자료구조 - 스택, 큐, 연결리스트) 🍎 오늘 배운 것 ✔️ 자료 구조 (스택, 큐, 연결리스트) 여러 개의 데이터들을 효율적으로 관리하기 위해 저장 순서나 처리 순서를 정해둔 '자료 구조'에 대해 배웠다. 가장 먼저 스택(Stack), 큐(Queue), 연결리스트(Linked List) 에 대해 공부했는데 사실 개념만 봐서는 잘 와닿지 않았다. 각각의 자료 구조들과 관련된 메서드들을 직접 코드로 작성해보기도 했는데, 오히려 이 과정에서 이해가 되기 시작한 부분들이 많았다. 특히 연결 리스트는 뭔가 머리속에 딱 그려지지가 않아서 직접 손으로 그려보거나, 예시를 객체 형태로 작성해보면서 익숙해지려고 노력했던 것 같다. 공부한 내용들을 저녁 시간동안 쭉 정리해보고, 작성했던 코드도 수도 코드로 다시 써보니까 각각의 자료구조를 언제 사용하는게 효.. 2021. 1. 20.
반응형

티스토리툴바