항해99와 함께하는 TIL
Hash의 사용법
알고리즘 문제를 풀며 Hash에 대해 간략하게 알게되었다.
key : value쌍으로 가지고 있고 핵심은 더 빠르게 찾기 위해 고안되었다는 것이다.
오늘의 학습 키워드
해쉬란?
공부한 내용 본인의 언어로 정리하기
해쉬는 저장된 데이터를 빠르게 찾을 때 사용한다. 잊지 말자
C++의 unorderd_map = O(n)의 시간복잡도를 가진다. map은 바이너리 서치 트리를 사용해서 O(nlogN)의 복잡도를 가진다.
알고리즘을 풀 때 새로운 자료구조를 알아냈다. Hash 필요한 상황에 적재적소해서 사용하도록 하자.(c++ 같은 경우는 map, unorderd_map이다.)
오늘의 회고
String은 사전순으로 정렬하고 int형은 길이 순으로 정렬한다. 잊지말자
새로운 자료구조 Hash에 대해 알게되었다. 어떤 상황에 써야하는지 익히도록 하자
언제나 최악의 상황을 대비하자
오늘 문제의 조건에서 1이상 10^7이하였다. 이는 O(n)만에 문제를 풀었어야 했는데 내가 처음에 낸 알고리즘은 O(n^2)의 시간 복잡도를 가졌었다. 문제의 제한을 잊지 않도록 하자
언제나 예외를 생각하자
처음에 코드를 틀린게 없다고 생각이 들었다.(항상 틀리면서도 어딘지 알지 못하는 것에 좀 더 가까운듯 하다…)
어떤 문제가 있었고, 나는 어떤 시도를 했는지
프로그래머스의 전화번호 목록을 풀면서 발생했다.
처음 내 시도는 brute force를 이용해 모든 요소를 전부 다 검사했었다. 몇몇 테스트케이스와 효율성 테스트를 통과하지 못했었다.
어떻게 해결했는지
기존 요소를 모두 체크하는 방안에서 해쉬를 이용해 풀었다.
1번째 해결안(효율성 테스트 실패)
일단 처음에는 배열을 정렬해보았다. 그랬더니 테스트케이스는 모두 통과했었다.
처음에 모든 요소를 검사하기 전에 sort알고리즘을 이용해 배열에 있는 요소를 사전순(String형태로 저장되어 있어 길이순이 아니라 사전순으로 정렬된다.) 으로 정렬했다.
정렬된 요소들을 전부 짝을 맞춰가면서 결과를 도출했었다. 테스트케이스는 통과했지만 효울성 테스트에서 떨어졌다.
2번째 해결안
해쉬테이블을 이용한 방안
위에서 말했다 싶이 해쉬는 더 빠르게 찾기 위해 사용한다.
해쉬에 데이터들을 저장하고 인덱싱해서 찾는 방안으로 바꿨다.
효울성 테스트를 통과한 방안이다!
무엇을 새롭게 알았는지
코딩테스트문제에서 언제나 자료형은 배열에 담아주거나, vector에 담아준다. 지금까지는 언제나 주어진 배열, vector에서만 최대한 활용하려고 했다. (누가봐도 stack, queue를 사용해야 하는 문제를 제외하곤)
오늘 hash를 활용하는 법을 알았으니 이젠 stack, queue 처럼 hash도 사용할 차례이다.
내일 학습할 것은 무엇인지
- 경험정리
현재 프로젝트가 완성되고 유지보수하고 있으니 프로젝트를 수행하며 내가 겪은 일들을 정리할 것이다. - 프로젝트 수행…
현재 프로젝트에서 git을 통해 test브랜치를 나눠 사용해야 하는 방법을 고안해야한다.(기한이 꼴랑 24시간 밖에 안남아서 빨리해야됨) ㅠㅠ - 알고리즘
꾸준하게 알고리즘… 잊지않기
후기?
오늘 코테 스터디를 하면서 막상 집중을 잘 못한것 같다 ㅋㅋㅋ 사실 나는 미들러 레벨로 들어갔는데 챌린저 문제도 풀어보고싶어서 풀어보는 시간에 챌린저 문제를 풀었다.
그래도 제한시간?...을 약 30분 정도 넘겼지만
챌린저 문제를 내스스로 풀어보니 기분은 좋았다. (물론 처음에 개틀림)
예전엔 손도 못댔었던 문제들인데 이제 손이라도 대보고 틀리면 고쳐볼 수라도 있는 게 얼마나 다행인지 모른다...
스터디는 게더타운에서 이뤄졌는데 사람이 너무 많아서 렉걸렸었다 ㅋㅋ 다같이 하는 발표시간도 재밌었고 현직자분이 코드리뷰해주시는 것도 참신한 방법이 보여서 즐거웠다. 6주 뒤에 훨씬 더 성장해있을 나를 기약하며 여기서 마친다.
#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL
