IT 인터뷰와 자료구조. 큐와 스택

2016년 12월 15일

IT 인터뷰 볼 때 알고리듬과 자료구조 물어본다는 건 아마도 다 아시리라 믿는다. 그런데 왜? 왜 이걸 알아야 하지요? 라고 묻는 분들 있다. 이걸 꼭 잘 해야 개발자인가요라고 묻는 분들도 많다. 여기에 내 대답은 "자료 구조 엄청 중요합니다"(난 잘 모르지만). "알고리듬 기본 엄청 중요해요"(난 공부 안 했지만). 하지만 전 설명은 잘 합니다. 왜 중요한지 말씀드릴게요.

책방을 만들려고 할 때 찬장스타일의 가구나 옷장은 별로겠죠. 특히 비슷한 사이즈의 책이 대부분이라면 적당한 선반이 들어간 책장이 좋겠죠? 자료구조가 딱 그거입니다. 컴퓨터 프로그래밍 하면서, 작업 중인 데이터를 어떻게 어디에 저장할 건지가 자료구조라면, 어떻게 일처리를 할 것인지가 알고리듬입니다. 자, 서브웨이 가게를 생각해봅시다. 먼저 빵부터 하나 고르고 뭘 넣을까 물어보죠. 그렇게 고기랑 야채 넣고 나중에 소스 뿌려서 포장하고 계산합니다. 이게 딱 일렬로 늘어져 있잖아요? 그런데 고기와 야채를 락앤락에 각각 넣어둬서 하나 고를 때마다 뚜껑 열고 닫고 해야 한다면, 그리고 순서를 흩트려 놓았다면 샌드위치 만드는 속도가 훨씬 느려지겠죠. 그래서 용도에 따라 쓰는 자료구조, 알고리듬이 각각 다릅니다.

'선착순'은 큐를 씁니다. 큐가 뭐냐면 '줄서기'입니다. 먼저 도착하면 먼저 서비스받습니다. 대신에 '스택'은, 가장 최근 들어온 애가 제일 먼저 나갑니다. 은행에서 이러면 난리 나겠죠? 식당에서 이러면 칼부림 나겠죠? 그러면 스택은 도대체 어디에 쓸까요?

높게 쌓인 접시를 생각해봅시다. 만약 '선착순'으로 접시를 쓴다면 우리는 접시 하나 꺼내 쓸 때마다 제일 밑에 있는 접시를 꺼내야겠죠. 실제로는 우린 맨 위에 있는 것을 꺼내 씁니다. 새로 접시를 닦으면 맨 아래에 넣지 않고 그냥 위에 두죠. 이렇게 맨 위에 하나 더 얹는 것을 push \라고 하고, 맨 위의 접시 하나를 가지고 가면 pop입니다. 맨 마지막이 제일 먼저 나가니까 Last In First Out, LIFO라고 합니다.

그렇다면 큐는? 뭐 선착순이 필요한 모든 다른 상황에서 쓰시면 되겠습니다. 여기서는 처음 오면 먼저 나가니까 First In First Out, FIFO입니다. Enqueue하면 줄을 세우는 거니까 맨 뒤에 넣고요, dequeue하면 줄에서 빼는 거니까 맨 앞의 애를 뺍니다.

짧게 갑니다. 다음은 어레이와 해시테이블. 저도 컴사 전공 안 해서 복잡하고 어려운 건 잘 몰라요. 간단하게 설명할 수 있는 것만 갑니다.