알고리즘216

• [프로그래머스] 신고 결과 받기 - 파이썬(python) 문제 설명 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다. 각 유저는 한 번에 한 명의 유저를 신고할 수 있습니다. 신고 횟수에 제한은 없습니다. 서로 다른 유저를 계속해서 신고할 수 있습니다. 한 유저를 여러 번 신고할 수도 있지만, 동일한 유저에 대한 신고 횟수는 1회로 처리됩니다. k번 이상 신고된 유저는 게시판 이용이 정지되며, 해당 유저를 신고한 모든 유저에게 정지 사실을 메일로 발송합니다. 유저가 신고한 모든 내용을 취합하여 마지막에 한꺼번에 게시판 이용 정지를 시키면서 정지 메일을 발송합니다. 다음은 전체 유저 목록이 ["muzi", "frodo", "apeach", "neo"]이고, k = 2.. 알고리즘/이것저것 2022. 9. 25.

• 

  [프로그래머스] 순위 - 파이썬(python) 나의 풀이 from collections import deque def find_person(winner, loser, node) : q = deque() visited = [False] * (len(winner)+1) for i in winner[node] : q.append(i) while q : x = q.popleft() for i in winner[x] : if not visited[i] : # 아직 탐색하지 않은 선수라면 visited[i] = True winner[node].add(i) # 내가 이길 수 있는 사람에 i를 추가 loser[i].add(node) # i가 지는 사람에 나를 추가 q.append(i) def solution(n, results): winner = [set([]) .. 알고리즘/Graph 그래프 2022. 9. 25.

• 

  [프로그래머스] 가장 먼 노드 - 파이썬(python) 나의 풀이 from collections import deque def solution(n, edge): visited = [-1] * (n+1) graph = [[] for _ in range(n+1)] q = deque() for x,y in edge : graph[x].append(y) graph[y].append(x) q.append(1) visited[1] = 0 while q : node = q.popleft() for i in graph[node] : if visited[i] == -1 : visited[i] = visited[node] + 1 q.append(i) max_cnt = max(visited) return visited.count(max_cnt) BFS 로 푼 문제이다. 1번 노.. 알고리즘/Graph 그래프 2022. 9. 25.

• 

  [프로그래머스] 징검다리 - 파이썬(python) 도저히 이분탐색으로 푸는 방법을 생각해내지 못해, 다른 분들의 풀이를 참고하여 아이디어를 얻은 채, 다시 코드를 작성하였다. 풀이 def solution(distance, rocks, n): answer = 0 start, end = 0, distance rocks.append(distance) # 맨 뒤 거리도 계산할 수 있도록 한다 rocks.sort() # 바위 정렬 #이분 탐색 while start 바위 간격의 최솟값 del_stones = 0 # 제거한 돌 개수 pre_stone = 0 # 기준이되는 돌(시작지점) min_dis = distance for rock in rocks: dis = rock - pre_stone # 현재 바위 - 이전 바위 사이 간격 if dis < mid: # 돌사이.. 알고리즘/이분탐색 2022. 9. 24.

• 

  [프로그래머스] 입국심사 - 파이썬(python) 나의 풀이 def binarySearch(left, right, n, times): answer = right while left = n : answer = min(answer, mid); right = mid - 1 else : left = mid + 1 return answer def solution(n, times): min_time = 0 max_time = max(times) * n answer = binarySearch(min_time, max_time, n, times) return answer 이분탐색은 탐색하는데 걸리는 시간이 O(log N) 이기 때문에, 탐색해야 하는 input 이 아주 큰 숫자일 때 사용하기 좋다. 따라서, 위 문제에서도 심사를 하는데 걸리는 시간을 기준으로 이분탐색.. 알고리즘/이분탐색 2022. 9. 24.

• 

  [프로그래머스] 퍼즐 조각 채우기 - 파이썬(python) 문제 설명 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양입니다. 이때, 다음 규칙에 따라 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채우면 됩니다. 조각은 한 번에 하나씩 채워 넣습니다. 조각을 회전시킬 수 있습니다. 조각을 뒤집을 수는 없습니다. 게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다. 다음은 퍼즐 조각을 채우는 예시입니다. 위 그림에서 왼쪽은 현재 게임 보드의 상태를, 오른쪽은 테이블 위에 놓인 퍼즐 조각들을 나타냅니다. 테이블 위에 놓인 퍼즐 조각들 또한 마찬가지로 [상,하,좌,우]로 인접해 붙어있는 경우는 없으며, 흰 칸은 퍼즐이 놓이지 않은 빈 공간을 .. 알고리즘/DFS, BFS 2022. 9. 23.

• 

  [프로그래머스] 아이템 줍기 - 파이썬(python) 문제 설명 다음과 같은 다각형 모양 지형에서 캐릭터가 아이템을 줍기 위해 이동하려 합니다. 지형은 각 변이 x축, y축과 평행한 직사각형이 겹쳐진 형태로 표현하며, 캐릭터는 이 다각형의 둘레(굵은 선)를 따라서 이동합니다. 만약 직사각형을 겹친 후 다음과 같이 중앙에 빈 공간이 생기는 경우, 다각형의 가장 바깥쪽 테두리가 캐릭터의 이동 경로가 됩니다. 단, 서로 다른 두 직사각형의 x축 좌표 또는 y축 좌표가 같은 경우는 없습니다. 즉, 위 그림처럼 서로 다른 두 직사각형이 꼭짓점에서 만나거나, 변이 겹치는 경우 등은 없습니다. 다음 그림과 같이 지형이 2개 이상으로 분리된 경우도 없습니다. 한 직사각형이 다른 직사각형 안에 완전히 포함되는 경우 또한 없습니다. 지형을 나타내는 직사각형이 담긴 2차원 배.. 알고리즘/DFS, BFS 2022. 9. 22.

• [프로그래머스] 여행경로 - 파이썬(python) 문제 설명 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3개 이상 10,000개 이하입니다. tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다. 주어진 항공권은 모두 사용해야 합니다. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다. 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다. [["ICN", "JFK"], ["HND", "IA.. 알고리즘/DFS, BFS 2022. 9. 22.

• 

  [프로그래머스] 단어 변환 - 파이썬(python) 나의 풀이 step = [] def dfs(begin, target, words, cnt): if begin == target : step.append(cnt) return for i in range(len(words)) : tmp = 0 for j in range(len(words[i])) : if begin[j] == words[i][j] : tmp += 1 if tmp == len(begin)-1 : lst = words[:] lst.remove(words[i]) dfs(words[i], target, lst, cnt+1) def solution(begin, target, words): dfs(begin, target, words, 0) if step == [] : return 0 else : st.. 알고리즘/DFS, BFS 2022. 9. 21.

• 

  [프로그래머스] 네트워크 - 파이썬(python) 문제 설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j].. 알고리즘/DFS, BFS 2022. 9. 20.

• 

  [프로그래머스] 게임 맵 최단거리 - 파이썬(python) 문제 설명 ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다. 지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다. 위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다. 아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다. 첫 번째 방법은 11.. 알고리즘/DFS, BFS 2022. 9. 20.

• 

  [프로그래머스] 타겟 넘버 - 파이썬(python) 나의 풀이 a = 0 def dfs(i, result, numbers, target) : global a if i == len(numbers) : if result == target : a+=1 return else : dfs(i+1, result+numbers[i], numbers, target) dfs(i+1, result-numbers[i], numbers, target) def solution(numbers, target): result = 0 dfs(0, result, numbers, target) return a 위 그림처럼 i번째 숫자에 대해 +부호 or -부호를 붙여 계산하는 모든 경우의 수를 따져보면 된다. 즉, DFS 로 모든 경우에 대해 깊이 우선 탐색을 한다. 그리고, i가 마지막원.. 알고리즘/DFS, BFS 2022. 9. 20.