백엔드 연습장 백엔드 연습장

공부한지 3주차가 되어가지만 아직 자바 언어가 어색하기만하다. 특히나 인터페이스, 클래스, 상속 같은 개념들이 너무 이해하기가 어렵다. 처음엔 클래스가 그냥 function 인것으로 이해했는데 뭔가 또 다른느낌이고... 특히나 뭔가 객체와 엮이기 시작하면 이게 뭔 내용인가 싶다. 솔직히 말해서 더이상 다른사람들처럼 따라가기가 어렵다고 판단했다. 이미 벌어진 차이를 단번에 메꾸는건 불가능할 테고 그렇다면 이렇게 된 이상 거꾸로 공부하는게 낫다고 생각한다. 문제를 먼저 풀면서 필요한 관련 기능들을 익히고 그 기능들과 관련이 있는 강의를 거꾸로 찾아보는 방법을 택하려고 한다. 가이드 라인으로 주어진 강의를 전부 들을 수 있다면 좋겠지만 실질적으로 과제를 해결하는것 만으로도 벅차다. 성격상, 그리고 이제까지의 ..

Linked List 링크드 리스트 연결 리스트 데이터를 링크로 연결해서 관리하는 자료구조. 노드라고 불리는 기본단위로 이루어져 있으며 노드는 데이터+포인터로 구성. (Pointer - 노드의 연결정보) 메모리상에서 연속성이 보장되지 않으므로 원하는 노드에 접근하기 위해서는 헤드(시작노드)부터 순차적으로 데이터에 접근해야한다. 이러한 특성 때문에 모든 연산의 시간복잡도가 O(n)의 복잡도를 띄는 특징이 있다. 데이터를 추가 삭제하는 연산 자체는 고정된 프로세스를 거치므로 자료의 크기와 관계가 없지만 해당 연산을 하기위해 목표 노드에 접근하는 연산이 자료크기에 정비례하는 연산을 필요로 하기때문.

Hashmap 해시 맵 해싱 함수를 통해 키 값으로부터 해시를 생성하여 그 해시값을 기준으로 데이터를 저장하는 자료구조. 키가 다른 값을 지니더라도 해싱 함수를 통과하면서 같은 해시값을 도출해내는 경우가 있다. 이 경우를 해시충돌이라고 하고 이를 해결하기 위한 방법으로 개방주소법과 분리연결법의 두가지 방법이 있다. 데이터의 양이 늘어날수록 개방주소법보다 분리연결법이 더 효율적이다. 해시 맵의 경우 해싱 프로세스 말고는 접근을 위한 프로세스가 따로 없다. 따라서 해시충돌이 없는 경우 시간 복잡도는 O(1)의 상수형이 된다. 다만 해시맵에서 해시충돌이 없을수는 없고 이러한 충돌이 일어나는 경우 해당 지점의 탐색은 순차탐색이 이루어지게 된다. 어느 방법이든 충돌 위치로부터 순차적으로 다음 위치를 찾아가야 하므..

Heap 힙 우선순위 큐라고도 한다. 최댓값, 최솟값의 빠른 연산을 위해 고안된 완전이진트리. A가 B의 부모노드(Parent node)인 경우 A,B 사이에는 대소관계가 성립한다. 힙은 중복값을 허용하며 반 정렬 상태의 특성을 가진다. 종류로는 루트값이 최대값인 최대힙과 그 반대인 최소힙이 있다. 힙의 연산 삽입 트리의 가장 끝 위치에 데이터를 삽입. 삽입한 키 값과 그 부모노드의 키 값을 비교하여 최대힙의 경우는 키값이 큰 경우, 최소힙의 경우는 작은 경우 부모노드와 키 값을 교체하는걸 반복한다. 연산시의 작업량이 logN 회의 형태가 되므로 시간복잡도는 O(logN)이 된다. 삭제 트리의 루트를 삭제한 뒤 가장 끝의 데이터를 루트와 교체한 뒤 최대힙은 자식노드중 큰 값을 가지는 키와, 최소힙은 작은..

Array 배열 https://jjoonleo.tistory.com/8 배열 ※ 이 글은 배열을 처음 배우시는 분들을 위한 글이 아닙니다. 배열이란? 번호(인덱스)와 번호에 대응하는 데이터들로 이루어진 자료구조 그냥 맨날 쓰는 그 배열 맞다. 근데 이 배열에도 종류가 jjoonleo.tistory.com https://moonsu.tistory.com/58 배열의 시간 복잡도 배열 (Array) 같은 타입의 변수들로 이루어진 집합. 배열을 구성하는 각각의 값을 배열 요소(element)라고 하며, 배열에서의 위치를 가리키는 숫자는 인덱스(index)이다. 배열의 인덱스는 0부터 시작해 moonsu.tistory.com 참고 블로그 배열의 경우 메모리에 데이터가 연속적으로 저장되므로 읽어들이는 속도가 빠르..

Queue FIFO, First in First out 선입선출 방식의 선형 자료구조. 일반적인 대기열을 생각하면 편하다. 음식점에서 가장 먼저 줄 선 사람이 가장 먼저 입장하는 셈. 프린터의 인쇄물 저장 방식이 큐 방식으로 작동한다. 원형큐에 대해서는 따로 정리를 할 필요가 있을지도 모르겠다. 조금 더 공부하고 이 글을 수정할지 새롭게 정리할지 고민해봐야겠다. 백준 1021번 양방향 순환 큐에서 원하는 데이터까지 접근하기 위해 가장 짧은 이동횟수를 계산하는 문제. 사실상 큐와 관련되어서 문제를 해결하기 보다는 단순히 구현하기 쉬운 방향으로 구상했다. Dequeue 이외의 작업이 없는 관계로 따로 데이터가 변경 될 이유가 없기 때문에 ArrayList를 이용해 Dequeue작업에 의한 배열의 위치 조정을..

https://roadmap.sh/backend Backend Developer Roadmap: What is Backend Development? Learn what backend development is, what backend developers do and how to become one using our community-driven roadmap. roadmap.sh 지금의 나는 Learn a Language, 즉 언어를 배우는 중이다. 저 긴 로드맵중 가장 처음이자 기본을 배우는 중이고 앞으로 배워나갈 항목들을 다루기 위한 도구를 갖추는 중이다. DB, API, 웹 보안등 배울건 한참 남은셈이다. 그런만큼 지금 배우는 내용을 제대로 이해하지 못하고 넘어간다면 나중에 필요한 부분에서 빠르게 ..

Stack LIFO Last in First out 후입선출 방식의 선형 자료구조. 자료의 출입구가 한쪽에만 위치하기 때문에 들어온 역순으로 자료를 꺼내야함. 보통은 상자쌓은 자료를 꺼내는 식으로 비유. 함수의 호출이나 재귀함수의 로직, 인터럽트의 처리등 나중에 발생한 이벤트를 먼저 처리해야 하는 경우에 사용됨. 백준 25556 스택 4개를 이용하여 순열을 청소할 수 있는지 확인하는 문제. 스택을 어떻게 써야 할지 모르겠어서 그냥 무식하게 배열을 여러개 만들어서 해결했다. 뭔가 더 좋은 방법이 있을것 같은데 어디서부터 찾아봐야 할 지 감이 안잡힌다. 나중에 다른 방법에 대해 좀더 공부해야 할 것 같음. 순열을 청소하려면 스택에 Push하는 데이터값이 현재 스택의 Top 값보다 커야함. 즉, 순열을 순서대..