본문 바로가기

알고리즘 공부/DS+알고리즘7

Hash Table key값은 불변! 이 글은 아래 유튜브 "코딩 국수" 님의 영상을 보고 생각한 점을 작성합니다. https://youtu.be/ET3iI5bNM80?si=B48M_fPSzaL3FKEI 언젠가 파이썬 딕셔너리를 활용하며 왜 안되지? 라는 생각을 한 적이 있다. 이러했던 경험을 논리적으로 풀어보려 한다. (자바에서는 HashMap과 동일하다) 딕셔너리는 아래와 같이, key와 해당 key에 해당하는 value값으로 구성되어 있다. dic = {"123": 12345} 이는 조금 더 풀어보면, "key의 해시값에 해당하는 위치에 value 값을 저장"하며 덕분에 key값을 알면, value값에 접근하는 시간을 O(1)의 시간으로 줄여준다. 이러한 구조를 해시 테이블(Hash Table)이라 칭한다. "key의 해시값" 이라는 .. 2024. 2. 22.
return Boolean과 return Function의 차이 return 함수 와 그냥 일반 return의 차이 아래 두 함수는 단순하게 생각해본다면, if 조건에 맞다면 return True를 하는 함수로 이해할 수 있겠지만, 실행결과는 다르게 나온다. def dfs1(): if 조건: return True for i in range(4): return dfs1() def dfs2(): if 조건: return True for i in range(4): if dfs2(): return True dfs1 함수는 for 문이 있기 때문에 자칫 4번 실행되지 않나? 라는 착각을 할 수 있다. (나다..) 그러나, i = 0일때만 for문을 스캔하고 해당 for문에서 return True가 되지 않는다면 함수가 끝나 return 되기 때문에 그 다음인 i=1, 2, 3.. 2024. 1. 30.
비트 연산으로 조합구하기 '1 ~ 10 의 수들 중 숫자 3개 뽑기' 와 같은 조합의 개념을 물어보는 문제들이 많은데, 이는 쉽게 백트래킹을 이용해서 구할 수 있다. 다만, 1 ~ 10 의 수들 중 뽑을 수 있는 카드의 경우의 수를 구해라 하면 조금 문제가 복잡해진다. 이런 경우에 쉽게 해당 경우의 수를 구할 수 있는 방법을 공부해보았다 비트 마스킹 이라는 기법이다. 예시로, 1, 2, 3 의 3가지 수에 대해서 모든 가능한 카드를 뽑는 방법은 2 * 2 * 2 이다. (2는 해당 카드를 뽑거나 안뽑을 경우의 수) 2 * 2 * 2를 조금 sparse하게 펼쳐보면 000 이라는 3개의 숫자로 표현이 가능하다. 예를 들어 1, 2번을 뽑을꺼다?! -> 110 3번만 뽑겠다? -> 001 그렇다면, 1, 2, 3의 3가지 수에 대해.. 2024. 1. 17.
그래프에서 SCC (Strongly Connected Component) 찾기 SCC에 대한 증명을 위한 글이 아님을 알려드립니다! SCC란 그래프에서 서로 다른 노드 u, v 2개를 뽑았을때, u->v로도 직간접적으로 갈 수 있고, v->u로도 역시 직간접적으로 갈 수 있는 노드들의 집합이다. 위의 그림에서 SCC를 추출해보자면, [1, 2, 3], [4, 5], [6] 으로 나뉠 것이다. 사람의 눈으로 직관적인 분리는 쉽지만, 이를 코드로 구현할 때를 생각해보자 그런데! SCC를 찾기 아주 조금 전에 우선적으로 생각해볼 문제가 있다. 1->2로 가는 그래프가 있다 가정해보자. 1번 노드에서 시작해 후위표기 즉 post number를 각 노드에 붙인다 하면, 1번 노드가 2번이 되고 2번 노드는 1번이 될 것이다. 2에서 시작하는 후위표기를 하면 이 역시 1번 노드가 2번, 2번.. 2023. 12. 7.

티스토리툴바