아침-10시-코테-스터디-2주차

정 승 연·2023년 2월 16일
0

k0ding ㅌest

목록 보기
11/15

아침10시코테스터디

2주차

update. 2023-03-28

타겟 넘버

순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다.
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return
dfs 함수 인자를 줄였으면 좋았을텐데 .. 줄이려면 global 전역변수 사용해야함.
depth와 len(numbers) 비교하고 target과 넘어오는 더하기 합 이용해 재귀 끝내기

def solution(numbers, target):
     answer = 0
     answer += dfs(0,numbers,0,target)
     return answer

 def dfs(depth, numbers,num,target):
     answer = 0
     if depth == len(numbers): 
         if target==num:
             return 1
         else : return 0

     else :
         answer += dfs(depth+1,numbers,num+numbers[depth],target) 
         answer += dfs(depth+1,numbers,num-numbers[depth],target)
         return answer

입국심사

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.
입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.
데이터가 오지게 크면 이분 탐색.

  • 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
  • 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
  • 심사관은 1명 이상 100,000명 이하입니다.
def solution(n,times):

     times.sort()
     start=1
     end=times[len(times)-1]*n # 최대
     mid = 0

     # start,end,mid=1,times[len(times)-1]*n,0

     while start <= end:
         mid = (start+end)//2 # 최소 시간 후보

         person = 0
         for time in times:
             person += mid // time 
							# 최소시간 후보 동안 상담 가능한 사람의 수
							# 

         if person < n:
             start = mid + 1
         else:
             end = mid - 1

     return start

  1. start = 1, end = 심사하는데 가장 오래 걸리는 시간 * n

  2. mid = ( start + end ) // 2

    → 심사하는 데 걸리는 중간 시간. 이분 탐색

  3. for time in times : person += mid // time

    → 심사하는데 걸리는 중간시간동안, 심사 가능한 사람 times로 나눴을 때 수가, 최소시간 후보동안 상담 가능한 사람의 수?

    → 최소 시간 후보(mid) 동안 상담 가능한 사람의 수 의 비교를 통해 start,end 다시 구성. start > end 이면 끝!

가장 먼 노드

가장 멀리 있는 노드를 최단 경로로 이동

bfs(또는 dfs)는 "최소" , "가장빠른" 이라는 단어가 나오면 사용하면 좋다

  • 가중치가 적용되지 않을 때, BFS의 부가 효과를 이용한다면, 최소 이동 횟수도 계산 가능
from collections import deque
def main():
    print(solution(6,[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]))

def solution(n,edge):
    answer = 0

    arr = [[]  for i in range (n+1)]
    visited = [0] *( n+1)

    for i , j in edge:
        arr[i].append(j)
        arr[j].append(i)
    
    visited[1] = 1

    bfs(1,arr,visited)

    for i in visited:
        if i == max(visited):
                answer += 1
    return answer


def bfs(start,arr,visited):
    que = deque([start]) # 양방향 큐

    while que:
        v = que.popleft() # Pop element from the start
        for i in arr[v]:
            if not visited[i]:
                visited[i] = visited[v] + 1
                que.append(i)
    
if __name__ == "__main__":
    main()

  1. 인접행렬 만들기

  2. 초기값 설정
    visited[1] = 1

  3. bfs(start,adj,visited) → start에서 시작해 갈 수 있는 모든 정점

    que = deque([start]).

    • deque(데크)
      1. 양방향 큐
      1. popleft() : pop from the start

  4. que가 비어있지 않은동안. pop해서. 방문하지 않았다면 pop한 값 인접한 곳 방문 방문해서 또 que에 넣기 .

전화번호 목록

String.startwith(String)

def solution(phone_book):
     phone_book.sort() # 정렬해서 앞뒤 비교 가능한 자원들이 위치하도록 한다.
     for i in range(len(phone_book)-1):
             # j가 접두어가 맞다면 : return false
             if phone_book[i+1].startswith(phone_book[i]): return False
     return True

기능 개발

to be continued ..

def solution(progresses, speeds):
     stack=[]
     progresses.reverse()

     for i in range(len(progresses)):
         stack.append(((100-progresses[i])//speeds[i])+(1 if 100-progresses[i] > 0 else 0))

     answer=[]

     while(stack):
         cnt = 1
         top=stack.pop()
         print(cnt, stack)
         while(stack and stack[-1] <= top): 
             print("here")
             cnt+=1
             stack.pop()
         answer.append(cnt)

     return answer

디스크 컨트롤러

to be continued ..

def solution(jobs):
     answer = 0
     arr = []
     k,start,end=0,-1,0
     while len(jobs) > k:
         for i in range(len(jobs)):
             if start < jobs[i][0] <= end:
                 heapq.heappush(arr, [jobs[i][1],jobs[i][0]])
         if len(arr)>0:
             now = heapq.heappop(arr)
             start = end
             end += now[0]
             answer += (end-now[1])
             k += 1
         else:
             end += 1

     return answer//(len(jobs))

완주하지 못한 선수

to be continued ..

def solution(participant,completion):
     participant.sort()
     completion.sort()
     for i in range (len(completion)):
         if participant[i] != completion[i]:
             return participant[i]
				 return participant[-1]

H-Index

정렬해서, 가장 큰 것부터 접근해서 논문 인용 횟수 비교하기
to be continued ..

def solution(citations):
     # citations.sort()
     # return citations[(len(citations)-1)//2]

     citations.sort()
     n = len(citations)
     for i in range (n):
         if citations[i] >= n-i:
             return n-i
     return 0

큰 수 만들기

to be continued ..

def solution(number, k):
     stack=[]
     for num in number:
         while stack and stack[-1] < num and k > 0: # ***
             stack.pop()
             k -= 1
         stack.append(num)
     return ''.join(stack)

정수 삼각형

to be continued ..

def solution(triangle):
     answer = 0
     n = len(triangle)

     dp = [[0 for j in range(n)] for i in range(n)]

     dp[0][0] = triangle[0][0]

     for i in range(n):
         for j in range(i):
             if j == 0:
                 dp[i][j] = dp[i-1][j] + triangle[i][j]
             elif j == i:
                 dp[i][j] = dp[i-1][j-1] + triangle[i][j]
             else:
                 dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]) + triangle[i][j]

             answer = max(answer,dp[i][j])
     return answer

모의고사

to be continued ..

def solution(answers):
     answer = [0,0,0]
     patterns=[[1,2,3,4,5],[2,1,2,3,2,4,2,5],[3,3,1,1,2,2,4,4,5,5]]

     for i in range(len(answers)):
         if answers[i] == patterns[0][i%5]:
             answer[0]+=1
         if answers[i] == patterns[1][i%8]:
             answer[1]+=1
         if answers[i] == patterns[2][i%10]:
             answer[2]+=1
     max = 0
     result=[]
     for i in range(3):
         if answer[i] > max:
             max = answer[i]
     for i in range(3):
         if answer[i] == max:
             result.append(i+1)

     return result

구명보트

to be continued ..

def solution(people, limit):
     answer = 0
     people.sort()

     left, right = 0, len(people) - 1

     while left <= right:
         answer += 1
         if people[left] + people[right] <= limit:
             left += 1
         right -= 1

     return answer

게임 맵 최단거리

to be continued ..

profile
정 승 연
이전 포스트

아침-10시-코테-스터디-1주차

다음 포스트

아침10시코테스터디-3주차

0개의 댓글