알고리즘 문제풀이210 [프로그래머스] 네트워크 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 컴퓨터들을 연결하여 네트워크가 만들어지고, 서로 다른 네트워크가 몇개인지 확인이 필요하므로 서로소 집합 알고리즘을 이용하여 네트워크 개수를 확인하였습니다. 2) 알고리즘 서로소 집합 3) 풀이 코드 사용 언어 - Python def solution(n, computers): network = list(range(n)) # 컴퓨터들 서로간 연결 정보 def union(x, y): # 컴퓨터 두대 연결 network[find(y)] = find(x) # 각 연결된 컴퓨터의 대표 컴퓨터를 연결 def find(x): # 해당 컴퓨터 네트워크의 대표 컴퓨터 검색 if x != network[x]: # 현재 컴퓨터가 대표 컴퓨터가 아니라면 network[x] .. 2022. 3. 20. [백준] 11052 카드 구매하기 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 필요한 카드의 개수가 1개부터 최고의 금액을 구하며, N개일때까지 구하였습니다. 2) 알고리즘 다이나믹 프로그래밍 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') N = int(sys.stdin.readline()) # 필요한 카드의 개수 price = list(map(int, sys.stdin.readline().split())) # 입력으로 주어지는 카드팩별 금액 dp = [0] * (N+1) # 카드의 개수별 최고 금액 for i in range(1, N+1): # 카드 N개까지 인덱스 반복 cases = {price[i-1]} # 카드 i개가 들어있는 팩을 하나 샀을 경우 fo.. 2022. 3. 19. [프로그래머스] 삼각 달팽이 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 2차원 배열에서 대각선으로 반을 채운다고 생각하였습니다. 그리하여 가장 왼쪽위의 좌표에서 시작하여 아래, 오른쪽, 왼쪽위 의 세가지 방향으로만 나아갔습니다. 2) 알고리즘 구현 3) 풀이 코드 사용 언어 - Python import sys from collections import deque sys.setrecursionlimit(10000) dr = [1, 0, -1] # 아래, 오른쪽, 왼쪽위 dc = [0, 1, -1] def solution(n): answer = [] # 정답 리스트 pyramid = [[0] * n for _ in range(n)] # 2차원 배열 direction = 0 # 진행 방향, 초기 아래 방향 def make_py.. 2022. 3. 16. [프로그래머스] 구명보트 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 탑승 가능한 인원이 최대 2명이므로, 무게가 가장 작은 사람과 가장 큰 사람이 함께 탐승하게 하는 방법이 최선의 방법입니다. 2) 알고리즘 탐욕법 3) 풀이 코드 사용 언어 - Python from collections import deque def solution(people, limit): answer = 0 q = deque(sorted(people, reverse=True)) # 사람의 무게를 내림차순으로 정렬 while q: # 사람이 남아있으면 answer += 1 # 보트 한개 추가 if len(q) < 2: # 한명만 남았으면, 혼자 사용 q.pop() elif q[0] + q[-1] 2022. 3. 16. [프로그래머스] 캐시 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 문제에서 제시한 LRU 알고리즘을 이용하여 풀이하였습니다. 2) 알고리즘 LRU (Least Recently Used) 3) 풀이 코드 사용 언어 - Python from collections import deque def solution(cacheSize, cities): answer = 0 # 정답 변수 q = deque() # 캐시 공간 if not cacheSize: # 캐시 사이즈가 0인 경우, 입력마다 항상 5초가 소요 됨 return len(cities) * 5 for city in cities: city = str(city).lower() # 대소문자 구분을 안함 if city not in q: # 현재 도시가 캐시 공간에 저장되어 있지.. 2022. 3. 15. [프로그래머스] 양궁대회 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 재귀로 높은 점수부터 시작하여 탐색하였습니다. 각 점수는 이길때는 딱 한발만 더 쏘도록 하였고, 질때는 한발도 쏘지 않도록 하였습니다. 2) 알고리즘 재귀 3) 풀이 코드 사용 언어 - Python def solution(n, info): answer = [] # 점수 받는 정답 리스트 max_difference = 0 # 가장 많이 차이 나는 점수차 def sol(idx, remain, apeach, ryan, ans): # 인덱스, 남은 화살 수, 어피치 점수, 라이언 점수, 점수별 라이언이 쏜 화살 수 nonlocal answer, max_difference if idx > 10 and remain >= 0: # 모두 반복했고, 화살이 남거나 다.. 2022. 3. 14. [백준] 2644 촌수계산 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 두 노드간의 거리를 구해야 하므로 BFS를 이용하여 풀이했습니다. 2) 알고리즘 BFS 3) 풀이 코드 사용 언어 - Python import sys from collections import deque sys.stdin = open('input.txt') def solution(): q = deque([p1]) visited[p1] = 0 # 본인 촌수는 0부터 시작 while q: node = q.popleft() for e in linked[node]: # 연결된 다음 노드 if visited[e] == -1: visited[e] = visited[node] + 1 # 촌수 증가 q.append(e) N = int(sys.stdin.readlin.. 2022. 3. 13. [백준] 1051 숫자 정사각형 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 가장 큰 정사각형을 찾아야하므로 초기에 변의 길이를 가장 길게 시작하여 줄여가며 정답을 찾았습니다. 2) 알고리즘 구현 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') N, M = map(int, sys.stdin.readline().split()) # 행, 열 square = [list(sys.stdin.readline().rstrip()) for _ in range(N)] # 입력으로 받은 사각형 answer = min(N, M) # 정사각형이므로 열과 행 중 짧은 변의 길이를 구함 end = False # 정답을 찾았는지 유무 while not end: for i in range.. 2022. 3. 11. [프로그래머스] 괄호 변환 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 주어진 문자열을 계속하여 분할하면서 재귀적 호출이 필요하여 함수를 만들어 접근하였습니다. 2) 알고리즘 재귀 구현 3) 풀이 코드 사용 언어 - Python def solution(p): # 올바른 괄호 문자열인지 판별 def is_right(s): stack = [] # 괄호를 쌓아놓 리스트 for c in s: if c == '(': # 현재 괄호가 여는 괄호라면 stack.append('(') # 리스트에 저장 elif not stack: # 닫는 괄호인데, 이전에 여는 괄호가 없었다면 return False # 올바른 괄호가 아님 elif stack[-1] == '(': # 현재 괄호가 닫는 괄호인데, 바로 이전 괄호가 여는 괄호였으면 stac.. 2022. 3. 10. [백준] 1774 우주신과의 교감 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 최소신장트리에 관한 문제로 프림 알고리즘을 이용하여 풀이했습니다. 이미 연결되어 있는 노드들 간에는 가중치를 0으로 두어 경로를 추가해주었습니다. 2) 알고리즘 프림 알고리즘 3) 풀이 코드 사용 언어 - Python import sys import heapq sys.stdin = open('input.txt') def solution(start): global answer heap = [(0, start)] while heap: node = heapq.heappop(heap) if not visited[node[1]]: # 도착 노드를 아직 연결하지 않았으면 visited[node[1]] = 1 # 연결 처리 answer += node[0] # 가중.. 2022. 3. 9. [백준] 12015 가장 긴 증가하는 부분 수열 2 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 초기에 2중 반복문을 이용하여 풀이하였으나, 시간 초과 문제가 발생하였습니다. 시간 단축을 위해 고민하던중 '최장 증가 부분 수열 (LIS)' 를 새롭게 학습하여 해결하였습니다. 2) 알고리즘 최장 증가 부분 수열 (LIS) 3) 풀이 코드 사용 언어 - Python import sys import bisect sys.stdin = open('input.txt') N = int(sys.stdin.readline()) # 수열의 길이 A = list(map(int, sys.stdin.readline().split())) # 수열 lis = [0] # 최장 증가 부분 수열(LIS) for num in A: # 수열 하나씩 확인 if num > lis[-1.. 2022. 3. 8. [프로그래머스] 기둥과 보 설치 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 초기에 2차원 배열을 생성하여 구조물을 설치하려 하였습니다. 그리하여 설치 또는 제거시 구조물들이 모든 조건에 해당하는지 확인하려 하였으나, 조건이 너무 까다로워 어려움을 겪었습니다. 조금 더 간단한 방법을 생각하여 집합을 이용하여 설치한 구조물들만 반복하며 조건을 확인하도록 하였습니다. 2) 알고리즘 구현 3) 풀이 코드 사용 언어 - Python def solution(n, build_frame): built = set() def is_right(): for b in built: # 모든 구조물 탐색 x, y, a = b # x, y 좌표, a-0: 기둥, 1: 보 if not a: # 현재 구조물이 기둥이라면 if y and (x, y-1, 0).. 2022. 3. 7. 이전 1 ··· 6 7 8 9 10 11 12 ··· 18 다음
