알고리즘 문제풀이/Python179 [백준] 2458 키 순서 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 학생의 키를 비교하기 위하여 DFS, BFS, 다익스트라 탐색을 고려하였으나, 학생들간 비교 정보에 대해서 모든 학생들을 기준으로 확인해야 했으므로 여러번 탐색이 필요하였습니다. 이러한 경우 제한 시간 문제가 발생하였습니다. 이후 플로이드 워셜을 고려하였으며, 처음에는 현재 학생보다 키가 큰 경우에는 배열의 값을 1, 작은 학생의 경우 -1 의 가중치를 주었습니다. 이후 판별에서는 탐색하는 학생과 같은 레벨에 있는 학생이 있는지 여부로 판별하려 하였으나, 예외 사항이 발생하였습니다. 가중치를 1과 -1로 주게 되어 같은 레벨에 존재하지 않지만, 키를 비교할 수 없는 경우가 발생하였습니다. 이러한 문제를 해결하기 위하여 -1 의 가중치를 제거하고, 학생.. 2022. 6. 7. [백준] 11404 플로이드 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 초기에 특정 노드에서 다른 노드로 가는 최단 거리를 구하기 위하여 다익스트라를 이용하여 구하였습니다. 그러나 모든 노드에서 다른 노드로 이동하는 최단 거리를 구하여야 했기에, N개에 노드에 대해서 다익스트라를 N번 이용하여야 했습니다. 이로 인하여 시간 초과가 발생하였습니다. 모든 노드에서 다른 모든 노드로 이동하는 최단 거리를 한번에 구하기 위하여 '플로이드 워셜' 알고리즘을 이용하였습니다. 다익스트라와 플로이드 워셜 알고리즘의 용도에 대해 비교를 간단하게 해보자면, 다익스트라는 특정 노드에서 출발하여 다른 노드들로 향하는 최단 거리를 빠르게 구할 수 있다면, 플로이드 워셜 알고리즘은 모든 노드에서 다른 노드들로 향하는 최단 거리를 구할 수 있습니다.. 2022. 6. 5. [백준] 2589 보물섬 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 문제를 처음 접했을때, 트리의 지름을 구하는 원리를 이용하였습니다. 여러 육지로 이루어진 하나의 대륙(덩어리)의 한 좌표에서 가장 멀리 있는 좌표를 구한 이후 다시 그 좌표에서 가장 멀리 있는 값을 구하였습니다. 그러나 육지가 트리와 같은 형태를 이루지 않는 경우가 존재하였습니다. 예를 들어 하나의 노드를 선택하여 루트노드로 지정하였다면 다른 노드들은 자식 노드가 되는데, 특정 경우에 어떤 좌표를 루트노드로 지정하였는데 리프노드가 다시 루트노드와 이어지는 순환하는 형태를 나타냈습니다. 이러한 경우에 올바른 정답을 찾을 수 없었습니다. 이후 모든 좌표들을 한번씩 BFS를 이용하여 탐색하며 가장 먼 거리를 구하였고, 그 거리들 중 가장 긴 값을 계속해서 .. 2022. 6. 3. [백준] 1766 문제집 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 어떤 문제들을 풀어야만 다음 문제를 풀 수 있으므로 위상 정렬을 이용하여 풀이하였습니다. 처음 문제를 접하였을 때, 세번째 조건인 쉬운 문제부터 풀어야 한다는 조건을 만족시키기 위하여 한문제를 풀이하고 문제 번호가 낮은 문제부터 다시 탐색하며 풀이를 진행하였습니다. 그러나 반복문을 이용하여 계속해서 앞쪽 문제부터 순서대로 탐색을 진행하여 불필요한 탐색이 많아졌고 시간초과가 발생하였습니다. 시간을 단축하기 위하여 한 문제를 풀이하고 계속 처음 앞쪽 문제부터 탐색을 진행하는 것이 아니라 최소힙을 이용하여 먼저 풀어야하는 문제를 다 푼 경우 최소힙에 추가하였습니다. 이로 인하여 가장 쉬운 문제부터 푸는 조건을 만족시키며 시간 단축이 가능했습니다. 2) 알고.. 2022. 5. 30. [백준] 1655 가운데를 말해요 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 숫자가 순서대로 입력되었을때, 숫자들이 계속해서 정렬을 유지해야합니다. 초기에 하나의 큐를 이용하여 값을 정렬하고, 새로운 값이 들어올때 새로운 큐를 만들어 순서를 정렬하였으나 입력의 개수가 많아지게 되어 시간 초과가 발생하였습니다. 이후 최소힙과 최대힙을 이용하여 중간값을 유지시키도록 하였습니다. 중간값이 있을때, 중간 값보다 큰 값이 들어오는 경우, 최소힙에 새로운 값을 넣었습니다. 이렇게 하면 중간 값보다 크지만, 그 이후 값들은 작은 값들을 우선적으로 꺼낼 수 있습니다. 중간 값 보다 작은 값은 최대힙에 넣어, 중간 값과 가까운 수를 먼저 꺼낼 수 있도록 하였습니다. 숫자가 짝수개의 길이라면 두개의 값 중 작은 값을 꺼내야 하기에, 중간값보다 .. 2022. 5. 26. [백준] 14890 경사로 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 지나갈 길의 경우를 모두 리스트에 담아 두었고, 이 길을 돌아가며 경사로를 이용하여 지나갈 수 있는지 확인하였습니다. 경사로 가능 여부 조건을 확인하며 구현하였습니다. 2) 알고리즘 구현 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def solution(c): prev = c.pop() # 이전 땅의 높이 stack = [prev] # 경사로를 놓을 수 있는 여분의 땅 while c: # 다음 땅이 남아있다면 next = c.pop() # 다음 땅의 높이 if prev == next: # 이전 땅과 높이가 같으면 스택에 경사로 stack.append(next) # 여분땅 추가 e.. 2022. 5. 23. [프로그래머스] 최고의 집합 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 수학적으로 접근하였을때, 곱을 최대한 높은 값을 가지기 위해서는 숫자들 간 차이가 적을수록 높은 곱의 결과를 갖게 됩니다. 첫번째 조건에서 특정 개수의 숫자들의 합은 동일해야하므로, 곱의 결과만 높게 만들어주는 숫자들의 조합을 찾으면 됬습니다. 숫자들의 합을 숫자의 개수로 나누어 몫을 구하였습니다. 이로인해 모든 숫자들의 차이가 동일하도록 만들어주었습니다. 나머지가 발생하는 경우에는 숫자들을 순서대로 돌며 1씩 더해주어 숫자들간 차이를 최소로 만들어주었습니다. 2) 알고리즘 수학 3) 풀이 코드 사용 언어 - Python def solution(n, s): answer = [] num = s // n remain = s % n if not num: #.. 2022. 5. 12. [프로그래머스] 파괴되지 않은 건물 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 적의 공격 또는 아군의 회복 스킬이 발동할때 마다 2차원 배열을 반복하며 값을 변경하는 방법은 2차원 배열을 너무 자주 반복하여 많은 시간이 소요됩니다. 2차원 배열을 반복을 줄여 효율성을 올리기 위하여, 누적합을 이용하였습니다. 스킬이 사용될때 2차원 배열을 반복하는것이 아니라 스킬의 영향이 미치는 영역의 4개의 모서리에 변화량을 기록하였습니다. 모든 스킬에 대한 변화량을 기록한 이후, 마지막에 2차원 배열을 반복하여 기록된 변화량에 따라 2차원 배열의 모든 좌표들의 값을 산정하였습니다. 2) 알고리즘 누적합 3) 풀이 코드 사용 언어 - Python def solution(board, skills): answer = 0 N = len(board) .. 2022. 5. 9. [프로그래머스] 베스트앨범 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 주어진 장르와 노래를 함께 반복시켜, 장르별로 노래를 모으고 총 재생시간을 기록하였습니다. 이후 장르별로 총 재생기간을 비교하여 가장 많이 재생된 장르순서대로 정렬하였습니다. 마지막으로 장르별로 가장 많이 재생된 노래를 2개씩 꺼내서 정답에 추가하였습니다. 2) 알고리즘 구현 3) 풀이 코드 사용 언어 - Python def solution(genres, plays): genre_dict = {} # 장르별 플레이 리스트, 장르: {플레이리스트, 총 플레이 시간} genre_plays = [] # 장르별 총 플레이 시간 answer = [] # 정답 리스트 for idx in range(len(genres)): # 입력으로 주어지는 모든 장르들 반복 .. 2022. 5. 4. [프로그래머스] 가사 검색 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 초기에 문제를 접하였을때, 가사를 하나씩 반복하며 나올 수 있는 모든 경우의 수를 키로 만들어서 카운트 하였습니다. 그러나 효율성의 5개 중 3개만 통과하고 2개를 통과하지 못하였습니다. Trie(트라이) 라는 자료 구조를 알게 되어, 딕셔너리를 이용하여 만들었습니다. 물음표가 앞 또는 뒤에서만 나오기 때문에 앞과 뒤를 저장해두는 두개의 딕셔너리를 생성하였습니다. 각 딕셔너리의 최상단에는 글자 수를 키로 가지는 딕셔너리입니다. 글자 수 안에는 내부에 다음 글자를 키로 가지는 딕셔너리가 존재하게 됩니다. 2) 알고리즘 Trie 3) 풀이 코드 사용 언어 - Python def solution(words, queries): start = {} # 앞에 ?.. 2022. 5. 3. [프로그래머스] 이중우선순위큐 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 이전에 백준에서 풀이한 이중우선순위큐와 동일한 문제로 이번에도 최소힙과 최대힙을 이용하여 풀이하였습니다. 최소힙과 최대힙을 이용하여 입력으로 들어온 숫자들을 두곳에 모두 기록하였습니다. 삭제가 발생하였을때 삭제된 숫자와 해당 숫자가 삭제된 횟수를 딕셔너리에 기록하였습니다. 삭제된 숫자와 삭제된 횟수를 기록한 덕분에 두개의 힙에서 값을 서로 동기화가 가능하였습니다. 2) 알고리즘 최소힙, 최대힙 3) 풀이 코드 사용 언어 - Python import heapq def solution(operations): deleted = {} # 삭제된 숫자들 목록 => 삭제된 숫자 : 삭제된 횟수 min_heap = [] # 최소힙 max_heap = [] # 최대.. 2022. 4. 30. [백준] 16235 나무 재테크 📖 문제 🧑🏻💻 풀이 과정 1) 문제 풀이 문제 제한 시간이 아주 적기 때문에 계절별 로직을 함수로 만드는 경우 시간 초과 문제가 발생할 수 있습니다. 계절별로 한번에 처리가 가능한 경우들을 모아서 처리하는 방식으로 진행하였습니다. 처음 문제를 접근했을때, 나무들을 리스트를 이용하여 관리하는 경우에 년도가 흐를때마다 정렬을 해주어야 하기 때문에 최소힙을 이용하여 나무의 나이가 적은 순서대로 뽑아서 로직을 수행하려고 하였습니다. 그러나 최소힙은 push 와 pop 하는 과정에서 매번 O(logN) 의 시간복잡도를 갖고 있었고, 풀이에 오랜시간이 소요되었습니다. 이후 시간 단축을 위해 deque 를 이용하였습니다. 기존의 나무들은 시간의 흐름에 따라 나이가 1년씩 증가하거나 죽어서 없어지는 경우만 존재하고.. 2022. 4. 29. 이전 1 2 3 4 5 6 7 8 ··· 15 다음
