키워드 : 힙, 정렬(버블, 선택, 삽입, 퀵, 머지, 힙)
공부하면서 정리해둔 몇 안되는 것들에 적중률이 90%라서 스스로가 자랑스러웠다!
미리 하길 잘했어!
힙(heap)과 힙큐(heapq)
자료구조 heap
https://heung-bae-lee.github.io/2020/05/17/data_structure_07/
트리 -> 완전이진트리 -> 힙!
힙은 완전 이진 트리의 한 종류이다!
힙을 사용하는 이유
배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이지만 힙에 데이터를 넣고 최대값과 최소값을 찾으면 O(logn)이면 된다!
우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 할때 쓰인다.
완전이진트리와의 차이
자식노드 간 대소비교를 하지 않는다!
힙에 데이터가 추가될때
왼쪽 하단부터 추가된다(트리이므로)
힙에서 데이터를 삭제할때
힙의 목적 : 최대값 또는 최소값을 root 노드에 놓아서 값을 바로 꺼내 쓸 수 있도록 하는 것이므로 언제나 루트노드부터 삭제된다.
힙에서 노드번호 찾기
힙 구현의 편의를 위해, root 노드 인덱스 번호를 1로 지정하면, 구현이 좀더 수월하다.
- 부모 노드 인덱스 = 자식 노드 인덱스 // 2
- 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2
- 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2 + 1
다음 3가지의 공식 기억하기
예제 : 노드번호를 찾아보자
- 힙에서 부모노드 찾기
4 // 2 # 2
5 // 2 # 2
2 // 2 # 1
3 // 2 # 1- 힙에서 자식노드 찾기
2 * 2 # 4
2 * 2 + 1 # 5
1 * 2 # 2
1 * 2 + 1 # 3파이썬의 힙큐!
미리 정리해두었다! 운이 좋았다!
https://velog.io/@matt2550/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%A0%95%EB%A0%AC-%ED%95%84%EC%88%98-heapq
정렬들!
역시 운이 좋았다!
버블, 선택, 삽입, 퀵, 머지, 힙
https://velog.io/@matt2550/%EB%B0%B0%EC%97%B4-%EC%A0%95%EB%A6%AC
배운것 / 느낀것 / 내게 아쉬웠던 것
배운 것 : 야간모드랑 눈보호모드는 필수라는거!
문제가 있다면 문제를 만든 이유가 존재한다는거!
느낀 것 :
어떤 현자님이 하시는 파이썬 특강을 들었는데 무척 흥미로웠다!
컴퓨터가 빨리 왔으면 좋겠다.
파이썬은 다른 프로그래밍 언어에 비해 무척 인간친화적이다. 인간 기준으로는 빠르고 편하지만 컴퓨터 기준으로는 무척 복잡하고 느린 언어이다. 아마 그래서 사랑받는게 아닐까.
3시간의 스트레이트 강의를 통해 파이썬이 어떤 마음으로, 어떤 의도로 만들어졌는지 조금이나마 이해하게 되었다.
파이썬의 모든 함수와 변수는 재정의될 수 있으며 사용자가 조작하는건 그냥 표면에 덮어씌워진 커스텀스킨 같은거였다. 존재하지 않는 것을 존재하는 것처럼 만들어주는게 꼭 잘 만들어진 게임 같다.
뭐라고 해야할까...
내가 게임을 만든다고 했을때, 이전에는 단순히 칼을 들어서 몬스터를 잡는 모션을 만든다 정도라고 생각했다면.
이제는 칼을 몬스터와 겹치는 좌표에 휘두르면 몬스터가 피격모션을 띄우게 해줘서 마치 맞은것처럼 보이게 한다! 라는 느낌인데... 몬스터와 캐릭터는 같은 차원에 있는 것 같지만 사실 둘 다 창고 안에 있고 플레이어가 프로그램의 도움을 받아서 조작하는 건 일러스트로 그럴듯하게 만든 레플리카다!
설명은 잘 못하겠지만 사고에 있어서 조금 더 자유로워진 것은 확실하다.
내게 아쉬웠던 것 :
한동안 문제를 풀다가 또 답만 보고 넘기려고 하는 나쁜 습관이 계속 나온다. 답을 보더라도 그걸 처음부터 끝까지 내 손으로 쳐봐야하는데 음... 하고 넘어가버린다. 사실 에디터를 켜면 렉걸려서 컴퓨터가 멈춰서 그런 것도 있지만 귀찮아서 그런 것도 있다.
뭐든지 각이 나왔다 싶으면 손을 놓는 이 습관이 문제다. 습관을 고쳐야 해 ㅠㅠ 내 원래 목적은 자료구조를 깊게 이해하고 자료구조에 대해 물어봤을때 자신있게 대답할 수 있는 사람이 되는 거였는데
알고리즘 하다 보니까... 기출 문제은행 or 목차 받아서 예제랑 공식 따다가 정리해두면 문제를 이해한다는 전제 하에 레벨2까지는 구현 없이 복붙만으로도 충분할 것 같은 느낌이
들면 안되지! 노력하자! 원래 회고 키워드들 쓰다보면 소감쓸때쯤엔 이미 지쳐서 소감에 쓸 에너지가 안남았었는데 오늘 너무 날먹이었다.
하루에 스터디 2~3개씩 하시면서 몸이 부서져라 노력하시는 분들도 있는데 인생에 가장 열정적으로 보내기로 한 4달을 이렇게 느긋하게 흘려보내서는 안된다. 아, 근데 누가 그랬는데 뇌에는 부정이란 개념이 없어서 oo하면 안돼! 라고 하면 oo밖에 머릿속에 안남는다고 한다. 그리고 oo를 해버린다고.
이제부턴 안돼를 그만해야겠다. 열심히 해야 해! 열심히! 화이팅!
