2023 팀네이버 신입 공채 준비 (12) 이분탐색 & 그래프

오늘 한 리스트

1. 프로그래머스 이분탐색 1문제
2. 프로그래머스 그래프 2문제

프로그래머스 이분탐색 입국심사

• 문제 유형 : 이분탐색
  입국심사

  def solution(n, times):
    answer = 0
    length=len(times)
    init_n=n-length
    num_index=[0]*length
    while n>0:
        n-=1
        if n==0:
            break
        new_list=[]
        for i,j in zip(times,num_index):
            new_list.append(i*(j+1))
        num_index[new_list.index(min(new_list))]+=1
          
    new_list=[]
    for i,j in zip(times,num_index):
        new_list.append(i*(j+1))
    return min(new_list)
  

  처음 진행항 코드 => 결과는 맞지만 속도가 안나옴

  def solution(n, times):
    answer = 0
    start, end, mid = 1, times[-1] * n, 0
  
    while start < end:
        mid = (start + end) // 2
        total = 0
        for time in times:
            total += mid // time
        if total >= n:
            end = mid
        else:
            start = mid + 1
      
    answer = start
    return answer
  

  다른 사람이 만든 코드를 가져옴
  이 코드를 보면서 해석하면서 이분 탐색이 어떤 건지 알게 됬는데
  Ex => 0 ~ 60, => 0 ~ 30, => 15 ~ 30, => … 이런식으로 진행해 범위를 줄이는 작업을 함. 이 알고리즘을 이분탐색이라고 함

프로그래머스 그래프 가장 먼 노드

• 문제 유형 : 그래프
  가장 먼 노드

  from collections import deque
  def solution(n, edge):
    answer = 0
    visited=[False]*n
    num=[0]*n
    st=deque([(1,0)])
    visited[0]=True
    while st:
        end, d=st.popleft()
        for i in edge:
            #if (i[0]==end or i[1]==end) and visited[i[1]-1]==False:
            if i[0]==end and visited[i[1]-1]==False:
                st.append((i[1],d+1))
                visited[i[1]-1]=True
                num[i[1]-1]=d+1
            elif i[1]==end and visited[i[0]-1]==False:
                st.append((i[0],d+1))
                visited[i[1]-1]=True
                num[i[0]-1]=d+1
    num.sort(reverse=True)
    answer = num.count(num[0])
    return answer
  

  처음 dfs로 풀려 했으나 제대로 안풀림 다른 사람 코드를 참고해보니 Dijkstra라고 알고리즘을 사용했었음

  from collections import deque
  def solution(n, edge):
    d=[0]*n
    visited=[False]*n
    graph={}
    for i in edge:
        if i[0] in graph:
            graph[i[0]].append(i[1])
        else:
            graph[i[0]]=[]
            graph[i[0]].append(i[1])
        if i[1] in graph:
            graph[i[1]].append(i[0])
        else:
            graph[i[1]]=[]
            graph[i[1]].append(i[0])
    st=deque([(1,0)])
    visited[0]=True
    while st:
        st_p,dep=st.popleft()
        child_list=graph[st_p]
        for i in child_list:
            if visited[i-1]==False:
                d[i-1]=dep+1
                st.append((i,dep+1))
                visited[i-1]=True
    return d.count(sorted(d,reverse=True)[0])
  

  프로그래머스 그래프 순위

• 문제 유형 : 그래프
  순위

  def solution(n, results):
    total = [['?' for i in range(n)] for j in range(n)]
    for i in range(n):
        total[i][i]="SELF"
    for i in results:
        total[i[0]-1][i[1]-1]="WIN"
        total[i[1]-1][i[0]-1]="LOSE"
    for k in range(n): # 찾을 선수
        for i in range(n): # 찾을 선수와 매칭 경기가 있던 선수
            for j in range(n): # 매칭 경기가 있던 선수와 대결한 선수
                if total[i][k] == 'WIN' and total[k][j] == 'WIN':
                    total[i][j] = 'WIN'
                elif total[i][k] == 'LOSE' and total[k][j] == 'LOSE':
                    total[i][j] = 'LOSE'
    answer=0
    for i in total:
        if not "?" in i: 
            answer+=1
    return answer
  

  이건 손도 못대서 다른 사람 코드를 참고했는데 플로이드-워셜 알고리즘을 사용했다고 한다.

후기

그래프 쪽은 알고리즘을 좀 더 명확하게 알고 있어야겠다는 느낌을 강하게 받았다. 내일부터는 내가 풀면서 약했던 재귀 함수 쪽이나 dfs쪽을 복습을 해야할 것 같다.