알고리즘 면접질문
-
[ CS 기술면접 ] 알고리즘 예상질문 모음 !공부 !/Computer Science 2022. 5. 22. 01:01
알고리즘 질문 모음 # Adjacency Matrix, Adjacency List, UnionFind, LIS ✅ 인접 행렬과 인접 리스트의 장단점을 서로 비교하며 설명해 주세요. 어떤 경우에 무엇을 사용하는 것이 더 유리한지를 중점으로 설명해주시면 됩니다. 인접행렬의 경우 구현하기 쉬우며 빽빽한 그래프를 구현할때 좋습니다. 어떤 정점과 어떤 정점 사이 간선이 존재하는지 확인하기도 쉽습니다. 하짐나 어떤 점과 연결된 모든 노드를 방문하려면 O(V) 시간만큼이 걸립니다. 또한 공간복잡도가 O(V^2) 로 정점의 개수 V가 커질수록 메모리가 더 많이 필요합니다. 인접리스트의 경우 듬성듬성한 그래프로 구현할때 좋습니다. 어떤 정점에 연결된 다른 모든 정점들을 쉽게 방문할 수 있습니다. 하지만 어떤 정점과 어떤..
-
[ Algorithm ] BitMask 비트마스크공부 !/Computer Science 2022. 4. 20. 21:55
비트마스크 알고리즘 문제를 풀다보면 비트마스크의 개념을 알고 있으면 도움이 될 때가 있다 ! 그렇다면 비트마스크는 무엇일까 ?! 컴퓨터의 최소 연산 단위는 bit 이다 내부적으로 모든 자료를 이진수로 표현한다 bit 는 이진수를 나타내기 위해 0과 1로 이루어져 있고 정수의 이진수 표현을 자료구조로 쓰는 기법을 비트 마스크라 한다 비트연산자 비트연산자에는 AND, OR, XOR, NOT, SHIFT 가 존재한다 AND (&) # 대응하는 두 비트가 모두 1일 때 1을 반환한다 1010 & 1111 = 1010 OR (|) # 대응하는 두 비트가 모두 1 또는 하나라도 1인 경우 1을 반환한다 1010 | 1111 = 1111 XOR (^) # 대응하는 두 비트가 서로 다르면 1을 반환한다 1010^111..