Haribo Blog

• 가짜 해밀토니안

  2021-01-15

  Haribo

  프로그래머스  월간_코드_챌린지_시즌1

  Tree  DP  DFS/BFS  Lv.5
  • 가짜 해밀토니안
    • 코드

  가짜 해밀토니안

  다시 쓸예정. 참고ㄴㄴ

  코드

  import sys
  sys.setrecursionlimit(400000)
  from collections import defaultdict
  def set_depth_subtree(node, prev) :
      sub_trees, depths = [], []
      for child in graph[node] :
          if child == prev : continue
          set_depth_subtree(child, node)
          sub_trees.append((sub_tree[child], child))
          depths.append((depth[child], child))
          depth[node] = max(depth[node], depth[child] + 1)
      sub_trees.sort(reverse=True)
      depths.sort(reverse=True)
      if len(sub_trees) >= 2 :
          if sub_trees[0][1] != depths[0][1] : sub_tree[node] = sub_trees[0][0] + depths[0][0] + 1
          else : sub_tree[node] = max(sub_trees[0][0] + depths[1][0] + 1, sub_trees[1][0]+depths[0][0] + 1)
      elif len(sub_trees) == 1 : sub_tree[node] = sub_trees[0][0] + 1
  
  
  def DFS(node, prev, height) :
      global answer
      sub_trees, depths = [], []
      for child in graph[node] :
          if child == prev : continue
          sub_trees.append((sub_tree[child], child))
          depths.append((depth[child], child))
      sub_trees.sort(reverse=True)
      depths.sort(reverse=True)
      for child in graph[node] :
          if child == prev : continue
          next_height = height + 1
          if depths[0][1] != child :
              next_height = max(next_height, depths[0][0] + 2)
          elif len(depths) >= 2 and depths[0][1] == child :
              next_height = max(next_height, depths[1][0] + 2)
          DFS(child, node, next_height)
      if (len(sub_trees) >= 3) :
          answer = max(answer,
                       sub_trees[0][0]+sub_trees[1][0]+height,
                       sub_trees[0][0]+sub_trees[2][0]+depths[1][0]+1,
                       sub_trees[0][0]+sub_trees[1][0]+depths[2][0]+1)
      elif (len(sub_trees) == 2) :
          answer = max(answer, sub_trees[0][0]+sub_trees[1][0]+height)
  
  def solution(t):
      global  answer, N, graph, sub_tree, depth
      N = len(t) + 1
      graph = defaultdict(list)
      sub_tree, depth = [1]*N, [1]*N
      answer = 0
      for v1, v2 in t:
          graph[v1].append(v2)
          graph[v2].append(v1)
      set_depth_subtree(0, -1)
      DFS(0, -1, 1)
      return answer
  

  ---

  Read All

  ---

• 방의 갯수

  2020-12-29

  Haribo

  프로그래머스

  Lv.5
  • 방의 갯수
    • 코드

  방의 갯수

  계속 시간초과가 뜨길래 list말고 dictionary를 쓰니 허무하게 바로 통과되었습니다. 정적인 자료구조는 list를 쓰고 동적인 자료구조는 dictionary를 쓰는것이 훨씬 이득인것 같습니다.

  ---

  코드

  from collections import defaultdict
  
  def add(x, y) :
      return [(x[0]+y[0]/2, x[1]+y[1]/2), (x[0]+y[0], x[1]+y[1])]
  def check(point, next_, arrow) :
      return next_ in points and arrow not in points[point] and (arrow+4)%8 not in points[next_]
  def solution(arrows):
      global points
      answer = 0
      move = [(-1,  0), (-1,  1), (0,  1), (1,  1), (1,  0), (1, -1), (0, -1), (-1, -1)]
      points = defaultdict(set)
      point = (0, 0)
      for arrow in arrows :
          for next_ in add(point, move[arrow]) :
              answer += 1 if check(point, next_, arrow) else 0
              points[point].add(arrow)
              point = next_
      return answer
  

  ---

  Read All

  ---

• 편집 거리

  2020-12-20

  Haribo

  Algorithm

  DP
  • 편집 거리(Edit Distance)

  편집 거리(Edit Distance)

  ---

  정확하게 기억은 나지 않지만 카카오 2020 겨울 인턴 코딩테스트에 편집거리에 관한 문제가 있었습니다.

  편집거리는 두 단어의 유사도의 크기를 측정하는 단위입니다. 제 예상이지만 검색엔진에 잘못된 단어를 검색 했을 때, 단어를 추천해주는 알고리즘이 바로 편집거리 알고리즘이 아닐까 생각합니다.

  

  두 단어 economy 와 yummy 를 한번 보겠습니다. 두 단어는 길이도 틀리고, 시작 알파벳도 틀립니다.

  ---

  Read All

  ---

• 블록 이동하기

  2020-11-26

  Haribo

  프로그래머스  2020_KAKAO_BLIND_RECRUITMENT

  DFS/BFS  Graph  Lv.3
  • 블록 이동하기 풀이
  • 코드

  블록 이동하기 문제 바로가기

  블록 이동하기 풀이

  코드

  import numpy as np
  from collections import deque
  def sort_(state) : return sorted(state, key=lambda x : (x[0], x[1]))
  def add(x, y) : return (x[0]+y[0], x[1]+y[1])
  def check(head, tail) : return Board[head[0], head[1]] == 0 and Board[tail[0], tail[1]] == 0
  def check_(state, move, cord) : return cord != state and cord not in move
  def moving(head, tail) :
      state = sort_([head, tail])
      moving = [[1, 0], [-1, 0], [0, 1], [0, -1]]
      move = [sort_([add(head,x), add(tail, x)]) for x in moving if check(add(head, x), add(tail, x))]
      rotate = [sort_([head, add(head, x)]) for x in moving  if check(head, add(head, x)) and check(tail, add(tail, x)) and check_(state, move, sort_([head, add(head, x)]))] +\
               [sort_([tail, add(tail, x)]) for x in moving  if check(head, add(head, x)) and check(tail, add(tail, x)) and check_(state, move, sort_([head, add(head, x)]))]
      return move+rotate
  def solution(board):
      global Board, N
      N = len(board)
      Board = np.pad(board, ((1,1),(1,1)), 'constant', constant_values=1)
      que = deque([[(1, 1), (1, 2), 0]])
      visted = [[(1, 1), (1, 2)]]
      while que:
          head, tail, cost  = que.popleft()
          if head == (N, N) or tail == (N, N):
              return cost
          for child in moving(head, tail):
              if child not in visted:
                  que.append([*child, cost+1])
                  visted.append(child)
  

  ---

  Read All

  ---

• 자물쇠와 열쇠

  2020-11-26

  Haribo

  프로그래머스  2020_KAKAO_BLIND_RECRUITMENT

  Lv.3
  • 자물쇠와 열쇠 풀이
    • 코드

  자물쇠와 열쇠 문제 바로가기

  자물쇠와 열쇠 풀이

  코드

  import numpy as np
  def solution(key, lock):
      N, M = len(lock), len(key)
      lock = np.pad(lock, ((M-1,M-1),(M-1,M-1)), 'constant', constant_values=0)
      for _ in range(4) :
          key = rotate(key)
          for i in range(M+N-1) :
              for j in range(M+N-1) :
                  lock_ = np.array(lock)
                  lock_[i:i+M, j:j+M] ^= key
                  if lock_[M-1 : N + M-1, M-1 : N + M-1].sum() == N**2 :
                      return True
      return False
  
  def rotate(key):
      return np.array(list(zip(*key[::-1])))
  

  ---

  Read All

  ---

• 외벽 점검

  2020-11-26

  Haribo

  프로그래머스  2020_KAKAO_BLIND_RECRUITMENT

  Lv.3
  • 외벽 점검 풀이
    • 코드

  외벽 점검 문제 바로가기

  외벽 점검 풀이

  코드

  from itertools import permutations
  def solution(n, weak, dist):
      answer = []
      dists = [list(x) for x in permutations(dist)]
      weaks = [weak] + [weak[i+1:]+[x+n for x in weak[:i+1]] for i, _ in enumerate(weak[:-1])]
      for weak in weaks :
          for dist in dists :
              check = weak[0]
              for i, d in enumerate(dist) :
                  check += d
                  if check >= weak[-1] :
                      answer.append(i)
                      break
                  else :
                      check = [x for x in weak if x > check][0]
      return min(answer)+1 if answer else -1
  

  ---

  Read All

  ---

• 문자열 압축

  2020-11-26

  Haribo

  프로그래머스  2020_KAKAO_BLIND_RECRUITMENT

  Lv.2
  • 문자열 압축 풀이
    • 코드

  문자열 압축 문제 바로가기

  문자열 압축 풀이

  코드

  def solution(s):
      return min(press(s, index) for index in list(range(1, int(len(s)/2) + 1)) + [len(s)])
  
  def press(s, index) :
      result = ''
      coef = 1
      while(len(s) > index) :
          piv, s = s[:index]
          s = s[index:]
          if piv != s[:index] :
              result += str(coef) + piv if coef != 1 else piv
              coef = 0
          coef += 1
      result += str(coef)+ s if coef != 1 else s
      return len(result)
  

  랜덤여신 , Yang Sang-Ho 님의 코드를 조금 참고하였습니다.

  ---

  Read All

  ---

• 기둥과 보 설치

  2020-11-26

  Haribo

  프로그래머스  2020_KAKAO_BLIND_RECRUITMENT

  Lv.3
  • 기둥과 보 설치 풀이
    • 코드

  기둥과 보 설치 문제 바로가기

  기둥과 보 설치 풀이

  너무 어려워서 5명 정도 다른사람이 푼 코드를 보고 공부해서 다시 짰습니다. 머리가 멍청하면 몸이 고생한다는 말이 괜히 있는게 아니었습니다. 문제에서 알려주는 제한사항은 꼭 꼼꼼하게 3~4번 읽고 코드를 작성해야 한다는 사실을 깨달았습니다.

  코드

  def solution(n, build_frame):
      global N
      N = n
      answer = []
      for frame in build_frame :
          if frame[3] == 1 : # 설치
              answer.append(frame[:-1])
              if not check_rule(answer) : answer.pop() # 설치 규칙에 위배되면 넣은거 pop
          else : # 삭제
              del answer[answer.index(frame[:-1])]
              if not check_rule(answer) : answer.append(frame[:-1]) # 삭제 규칙에 위배되면 다시 삽입
      answer.sort()
      return answer
  def check_rule(answer) :
      for frame in answer :
          x, y, structure = frame
          if x < 0 or y < 0 or x > N or y > N : return False
          if structure == 0 :
              if y == 0 or [x, y, 1] in answer or [x-1, y, 1] in answer or [x, y-1, 0] in answer : continue
              else : return False
          else :
              if [x, y-1, 0] in answer or [x+1, y-1, 0] in answer or ([x-1, y, 1] in answer and [x+1, y, 1] in answer) : continue
              else : return False
      return True
  

  ---

  Read All

  ---

• 괄호 변환

  2020-11-26

  Haribo

  프로그래머스  2020_KAKAO_BLIND_RECRUITMENT

  Lv.2
  • 괄호 변환 풀이
    • 코드

  괄호 변환 문제 바로가기

  괄호 변환 풀이

  코드

  def solution(p):
      if p == '' : return ''
      u, v = split(p)
      return u + solution(v) if check_right(u) else '('+ solution(v) + ')' + reverse(u[1:-1])
  def check_balance(p) :
      return str.count('(') == str.count(')')
  def check_right(p) :
      count = 0
      for i in p :
          count += 1 if i == '(' else -1
          if count < 0 : return False
      return True
  def split(p) :
      for i in range(1, len(p)+1) :
          if check_balance(p[:i]) :
              return p[:i], p[i:]
  def reverse(p) :
      return ''.join(['(' if x==')' else ')' for x in p])
  

  ---

  Read All

  ---

• 가사 검색

  2020-11-26

  Haribo

  프로그래머스  2020_KAKAO_BLIND_RECRUITMENT

  Tree  Lv.4
  • 가사 검색 풀이
    • 코드

  가사 검색 문제 바로가기

  가사 검색 풀이

  처음보는 트라이 구조 자료구조를 이용해 문제를 풀어야해서 매우 감이 안잡혔었습니다. 역시 이런문제는 한번 맞아봐야 다음부터 제대로 풀 수 있습니다. 제 기억으로 2021 공채 시험에서도 트라이 구조를 이용한 문제가 3번인가 4번으로 나왔었는데 꼭 이해하고 넘어 가시길 바랍니다.

  코드

  import re
  
  def solution(words, queries):
      answer = []
      trees = [Trie() for _ in range(10000)]
      inv_trees = [Trie() for _ in range(10000)]
      for word in words :
          trees[len(word)-1].insert(word)
          inv_trees[len(word)-1].insert(word[::-1])
      for query in queries :
          if query[0] == '?' :
              answer.append(inv_trees[len(query)-1].query(re.sub('[^a-z]', '', query[::-1])))
          else :
              answer.append(trees[len(query)-1].query(re.sub('[^a-z]', '', query)))
      return answer
  
  class TrieNode:
      def __init__(self, char):
          self.char = char
          self.counter = 0
          self.children = {}
  
  class Trie(object):
      def __init__(self):
          self.root = TrieNode("")
  
      def insert(self, word):
          node = self.root
          for char in word:
              node.counter += 1
              if char in node.children:
                  node = node.children[char]
              else:
                  new_node = TrieNode(char)
                  node.children[char] = new_node
                  node = new_node
          node.counter += 1
      def query(self, word) :
          node = self.root
          for char in word :
              if char not in node.children : return 0
              node = node.children[char]
          return node.counter
  

  ---

  Read All

  ---