Array ↔ List

• 인덱스가 1부터 시작하는 구조에서는 Array를 사용한다.

  • List의 경우 쓰레기 값을 한 번 Add 해야 하는데 이게 많은 실수와 혼란을 유발한다.
  • 특히 다른 사람이 읽을 때는 더 헷갈린다.
  • 0-base와 1-base의 혼용은 구현과정에서 반드시 실수를 만들고 이는 절대 찾을 수 없다.

• 크기 고정이 보장된 경우에는 일차원 배열을 사용하고, 그렇지 않은 경우에는 List로 사용한다.

• 순회하면서 조건에 맞게 제거해야 하는 경우는 LINQ를 이용한다.

  var list = new List<int>(); 
  list = list.Where(x => x != t).ToList();
  

  • RemoveAt을 사용하면 list의 크기가 변하기 때문에 잦은 오류를 만들게 된다.

• List도 내부에 Array를 두기 때문에 메모리에서 연속적으로 존재한다.

Dictionary

• ContainsKey를 회피하기 위해 value(int)를 0으로 초기화 하는 방식은 매우 중요하다.

  void Main()
  {
  	var dict = new Dictionary<char,int>();
  	
  	for(char tmp = 'a'; tmp<='z'; tmp++)
  	{
  		dict[tmp] = 0; 
  	}
  	
  	dict['c'].Dump(); // result : 0
  }
  

  • 메모리는 낭비되고, Dictionary의 불연속성을 위배하기 때문에 좋은 방식은 아니지만 가독성(ContainsKey 없음)과 안전성에서 매우 뛰어나다.

• Dictionary<Key , Dictionary<k,v>>은 가독성 및 구현이 최악이므로 되도록 사용하지 않는다. 문제를 다시 읽고 재설계해라.

  • 일단 동작하자 마인드로 설계할 때 이런 자료구조를 선택한다.
  • dict에 dict는 변수 네이밍도 어렵고 순회 네이밍도 답 없다.

• 해시 기반이므로 조회한 Key의 이전 key 또는 다음 Key는 알 수 없다.

• 해시 기반이므로 정렬의 개념은 없다. 그러므로 LINQ의 OrderBy는 IEnumerable 타입의 시퀀스를 만들어 내는 거다.

• TryGetValue() 가 좋지만 ContainsKey()를 이용해서 값을 찾는다. ⇒ O(1) * 2

  
  if (dict.ContainsKey(key))
  {
      dict[key] += 1;
  }
  else
  {
      dict[key] = 1;
  }
  

  • 가독성에 더 좋다.
  • 까먹으면 Linq의 Any(kv ⇒ kv.Key == 2)도 가능하다

• Value로 Key를 조회하는 방법

  • 모든 Value에 중복이 없다고 가정하면 역방향 Dictionary를 한 개 더 만든다.
  • LINQ의 FirstOrDefault() → 복잡도 O(N)

• 문자열 LookUp의 경우 엄밀히 말하면 O(L) + O(1)이다.

  • 문자열의 GetHashCode()자체가 O(L)이기 때문이다.
  • 그러나 문자열의 길이가 20 이상이 되지 않으면 성능의 큰 이슈는 없다.