🐭 이번 주는 뭐 했어?

자료구조

이번 주는 알고리즘을 처음 시작하는 주차이었고 알고리즘의 자료구조들 중 기초적인 것이 어떤 것들이 있는지 알아보는 시간이었다 이번 포스팅에서는 자료구조의 종류에 어떤 것을 공부했는지 적어볼 예정이다

첫 팀장

안 그래도 잘 못 하는 알고리즘인데 처음 시작하자마자 바로 팀장이어서 부담이 엄청나게 컸다 물론 항해에서 팀장은 처음 방향 정도만 만들고 그 이후에는 팀원들과 다 같이 함께 해결해나가야 하므로 이후에는 중요하지 않지만 어쨌든 처음 방향을 어떻게 해야 모두가 만족하고 일주일을 알차게 보낼 수 있을지 고민을 많이 했다 그렇게 해서 생각했던데 처음에 제공하는 강의 내용을 공유하고 이후에
하루에 한 번씩 팀원끼리 과제를 분배해 각자 맡은 문제를 저녁에 발표하는 시간과 다음 날 아침에는 과제를 다시 한번 직접 풀어보면서 완벽하게 이해했는지 진행했었다

🐭 그래서 이번 주에 뭘 배웠어?

자료구조 종류

사실 과제는 절대 기초가 아니다 그치만 개념은 기초고 문제를 풀 때 꼭 알아야 하는 것들이 포함되어있었기 때문에 어떻게 보면 가장 중요한 첫 발판을 밟는 시간이었다고 생각했다 그럼 지금부터 하나씩 어떤 자료구조를 배웠는지 적겠습니다

- 연결리스트

연결리스트 라는 것을 설명할 때는 우리가 잘 알고 있는 배열과 비교하는 것이 가장 좋다

Array

• 장점
  기본 리스트 접근이 아주 쉬움
  특정 원소를 조회할 때 시간복잡도 O(1)
• 단점
  삽입 삭제 과정에 번거로움 시간복잡도 O(n)

Linked List

• 장점
  삽입 삭제 과정에 아주 쉬움 시간복잡도 O(1)
• 단점
  직접 구현해서 만들어야 해서 접근이 어려움

알고리즘을 풀 때 시간초과가 발생할 수도 있기 때문에 시간복잡도를 잘 고려해 문제를 푸는 것도 중요했다 따라서 리스트를 구현할 때 상황에 맞게 사용하는 것이 좋다

릿코드 - 21 두 정렬 리스트의 병합

- 스택

한쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료구조이다
장을 볼 때 물건을 담고 계산할 때 가장 위에 있는 거부터 꺼내는 걸 생각하면 이해하기 쉽다
현재 이 알고리즘은 파이썬이므로 push는 append로 입력한다

백준 - 1874 스택 수열

- 큐

한쪽 에서는 자료를 넣고 반대쪽에서는 자료를 뺄 수 있는 FIFO(First In First Out) 형식의 자료구조이다 놀이동산에서 놀이기구를 타기 위해 줄을 서고 순서대로 기구를 탄다고 생각하면 이해하기 쉽다

릿코드 - 232 스택을 이용한 큐 구현

- 해쉬테이블

key, value를 생각하면 이해하기 쉽다 하나의 문자열을 해시함수를 이용해 새로운 값을 변환하고 해당을 과정을 통해 만들어진 데이터를 저장하는 자료구조를 해쉬테이블이라고 한다

릿코드 - 3 중복 문자가 없는 가장 긴 부분 문자열

🐭 이번주 시험은 뭘 봤어??

프로그래머스 시험

프로그래머스에서 제공하는 문제 중에 우리가 배웠던 과정이 포함된 문제를 2시간 동안 총 2문제를 풀었다 일단 결과적으로 첫 번째 문제는 코드 실행은 성공했으나 시간 초과를 한 건지 정확도가 27퍼가 나오면서 문제 통과는 실패했다 두 번째는 문제는 시간이 부족해 접근하는데 실패했다 왜 코딩 테스트 보는데 7문제 이러는데 시간을 5시간이나 주는 이유를 알았다.. 문제 이해하는데만 시간을 엄청 쓴다

프로그래머스 - Lv.2 기능개발

프로그래머스 - Lv.2 다리를 지나는 트럭