유형별 문제풀이 tony - 트라이

문자열 집합

• 문제
• 코드
• 트라이 자료구조를 써야 할 줄 알았는데 그냥 set으로 푸니까 풀렸다

유형별 문제풀이 tony - 최소스패닝트리(신장트리)

백준 1197번 최소 스패닝 트리 골드4

• 문제
• 코드-파이썬

최소스패닝트리

• 문제
• 코드
• 동빈북에서 신장트리(복습) : 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프
  • 크루스칼 알고리즘 : 최소한의 비용으로 신장 트리 찾을 때 사용하는 알고리즘
  • 그래프에 간선을 담을 그래프를 만들고 비용이 낮은 순으로 정렬한다음에 간선을 순차적으로 탐색하면서 간선에 연결된 두 점이 연결되어 있지 않다면(처음에는 모든 점은 각각의 노드로 설정) 연결하고 그 비용을 전체 비용에 포함시키는 방법으로 전체 비용을 계산한다

카카오 lev2 프로그래머스

압축

• 문제
• 코드
• 카카오풀이

푼 것, 배운 것

알파벳 모두 포함하는 리스트 만들기

• 만들고 싶던 것은 이런 딕셔너리 였다.
  {'A': 1, 'B': 2, 'C': 3, 'D': 4, 'E': ...}
• 알파벳을 매번 다 치기 귀찮아서 파이썬은 알파벳을 상수로 갖고 있다는 것을 알게 되었다.
• string 모듈에 있어서 대문자로 A~Z까지 출력하고 싶다면 

import string

print(string.ascii_uppercase) ## ABCDEFGHIJKLMNOPQRSTUVWXYZ

• 똑똑이들의 풀이를 보니까 아스키 번호를 이용해서 이렇게 간단하게 풀기도 한다

  tmp = {chr(e + 64): e for e in range(1, 27)}

• 자바에서는 이 방법으로 쓰면 된다

     Map<String, Integer> dic = new HashMap<>();
     for (int i = 1; i < 27; i++) {
          dic.put((char)(64+i) + "", i);
     }
     System.out.println(dic);

• 편한 방법을 쓰자