💻 Computer Science/자료구조 & 알고리즘

해시라는 단어는 암호화 관련 정보를 알아볼 때 주로 들었던 단어 같다.오늘은 해시에 관련한 개념에 대해 총 정리를 해봐야겠다.Java에서는 HashTable 과 HashMap 둘다 있는데, 이 포스팅에서는 둘을 구분 짓지는 않고, HashMap 기반으로 한 설명임을 알려드리는 바이다. 📌 해시 테이블 자료구조는 무엇인가?해시(Hash) 단어 자체는 어떤 값을 일정 길이로 변환하는 기법이고, 해시 테이블은 그 해시 기법을 적용한 자료구조라고 할 수 있다.간단하게 key-value 구조로 빠르게 검색을 할 수 있다는 것이 특징이다대체 해시 테이블이 뭐길래 빠르게 검색을 할 수 있는 걸까?자 우리가 친구의 전화번호를 검색할 수 있는 사이트를 만들었다고 치자.검색창에 친구의 이름을 치면 전화번호가 나올 것이다..

📌  자료 구조는 왜 공부해야하나 1. 자료 구조가 무엇인가자료 구조 = Data + Structure = 자료들의 집합즉, 자료가 뭉쳐있는 생김새를 말한다.자료 구조는 데이터들의 관계가 논리적으로 정의된 일정한 규칙에 의해 나열된다.자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 조직적, 체계적으로 구분해서 표현한거다.이런 식으로 딱딱 구분지어서 예쁘게 놓은 거란 말이다. 2. 자료 구조의 목적자료구조의 목적은 크게 3가지이다.1. 효율적인 데이터 저장 및 접근2. 메모리 사용의 최적화3. 문제 해결 및 알고리즘 설계 지원각각 다른 책장이 존재한다고 가정하자.1번 책장은 책이 무작위로 꽂혀 있기 때문에 나중에 원하는 책을 찾기가 어려울 수 있다.2번 책장은 칸마다 같은 색상의 책을 진열했다. ..

알고리즘 효율성 체크에서 쓰이는 시간 복잡도와 공간 복잡도, 그리고 Big-O 표기법에 대해 정리하고 넘어가고자 한다.코테에서 어느정도 구현을 하다보면 시간 초과 혹은 메모리 초과를 겪는 경우가 많다.그 때 어떤 곳을 최적화하면 좋을지 알고자 겸사겸사 정리하고 넘어가기로 한다.알 때와 모를 때의 코드 구현은 정말 달라질 것이다. 📌 복잡도 & 점근적 표기법 복잡도, 그것이 무엇인가 🧐컴퓨터 과학에서 알고리즘의 계산 복잡도(Computational Complexity) 혹은 복잡도(Complexity)라는 것은 알고리즘을 실행하는 데 필요한 자원의 양을 뜻한다.이는 곳 알고리즘의 성능을 측정하는 데 사용되고, 복잡도가 작으면 작을 수록 해당 알고리즘이 효율적이라고 판단한다.여러 복잡도가 있지만 대표적인..

1. 큐 (Queue)큐는 이렇게 선입선출(FIFO) 구조이다.연산 과정에는- enqueue : 큐에 데이터를 넣는 작업- dequeue : 큐에서 데이터를 꺼내는 작업- front : 데이터를 꺼내는 부분에 데이터를 반환- rear : 데이터를 넣는 부분에 데이터를 반환이런 개념들이 등장 한다. 1. 쉽게 이해를 위해 예제를 살펴 보겠다.우리가 줄 서있는 대기열을 생각하면 쉽다.티켓 매표소에 이렇게 줄을 서 있다고 가정해보자.줄을 제일 먼저 선 A가 먼저 표를 사고, 제일 나중에 선 E까지 모두 순서대로 표를 살 수 있을 것이다.이렇게 근데 여기서 F가 등장해서 줄을 선다.그럼 이때 rear는 새로 추가된 맨 뒤의 F로 된다.이 F를 추가하는 작업을 enqueue 라고 하고, F 추가할 위치를 나타내는..

재귀 함수 이용해서 구하는 코드 def solution(x): answer = 0 if x =2: fn = fn_1 + fn_2 fn_2 = fn_1 fn_1 = fn x -= 1 return fn 반복문 버전은 프로그래머스의 다른 사람 코드를 참고 했다 재귀 알고리즘은 효율성이 떨어질 가능성이 크지만 생각을 직관적으로 표현이 가능하다는 장점이 있다

이진탐색은 꼭 크기순으로 정렬되어있다는 성질을 이용하여 탐색하는 기법 def solution(L, x): start = 0 upper = len(L) -1 answer = -1 while start

특정 원소를 포함한 인덱스 모두 반환하는 문제, 만약에 없을 시엔 리턴값에 -1을 넣어서 반환한다. def solution(L, x): answer = [] i = 0 while i < len(L): if L[i] == x: answer.append(i) i += 1 if answer == [] : answer = [-1] return answer 이건 나중에 실무에서도 쏠쏠히 써먹을 수 있을거 같아서 기록 탕탕! 좀더 예외처리를 하지 않고 깔끔하게 짜는 연습을 해야할것 같다