알고리즘 문제풀이210 [백준] 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. [프로그래머스] 입국심사 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 특정 시간 내에 인원을 모두 심사가 가능한지 여부 판별을 위해 이분 탐색을 이용하였습니다. 시간을 기준으로 필요한 최소 시간과 최대 시간을 우선적으로 구한 이후, 최소 시간을 탐색했습니다. 중간 시간을 적용하여 n명 이상 심사가 가능하면, 더 적은 시간으로 가능한지 탐색하였습니다. n명 심사가 불가능하다면, 더 많은 시간을 적용하여 탐색하였습니다. 2) 알고리즘 이분탐색 3) 풀이 코드 사용 언어 - JavaScript function solution(n, times) { let answer = 0 // 정답 변수 let min_time = 1 // 심사를 모두 마치는 최소 시간 let max_time = n * Math.max(...times) //.. 2022. 5. 27. [백준] 1655 가운데를 말해요 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 숫자가 순서대로 입력되었을때, 숫자들이 계속해서 정렬을 유지해야합니다. 초기에 하나의 큐를 이용하여 값을 정렬하고, 새로운 값이 들어올때 새로운 큐를 만들어 순서를 정렬하였으나 입력의 개수가 많아지게 되어 시간 초과가 발생하였습니다. 이후 최소힙과 최대힙을 이용하여 중간값을 유지시키도록 하였습니다. 중간값이 있을때, 중간 값보다 큰 값이 들어오는 경우, 최소힙에 새로운 값을 넣었습니다. 이렇게 하면 중간 값보다 크지만, 그 이후 값들은 작은 값들을 우선적으로 꺼낼 수 있습니다. 중간 값 보다 작은 값은 최대힙에 넣어, 중간 값과 가까운 수를 먼저 꺼낼 수 있도록 하였습니다. 숫자가 짝수개의 길이라면 두개의 값 중 작은 값을 꺼내야 하기에, 중간값보다 .. 2022. 5. 26. [프로그래머스] 추석트래픽 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 입력으로 들어온 문자열 형태의 시간 정보를 서로 계산하기 쉽게 하기 위하여 밀리초로 변경하였습니다. 변경된 밀리초를 하나의 객체의 키값으로 저장하였고, 시작시간인 경우 +1 을, 종료 시간인 경우 -1 을 연산하였습니다. 이후 객체의 키들을 오름차순으로 정렬하였고, 키값들을 순환하며 초당 최대 처리량을 구하였습니다. 2) 알고리즘 문자열 3) 풀이 코드 사용 언어 - JavaScript function solution(lines) { let answer = 0 // 정답 const timeline = {} // 타임라인을 저장할 객체 lines.map(v => v.split(' ')).forEach(v => { const hour = parseInt(.. 2022. 5. 24. [백준] 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) 문제 접근 및 이해 해당 조건을 만족하면서 재귀를 이용하여 완전탐색으로 접근하였습니다. 2) 알고리즘 완전탐색 재귀 3) 풀이 코드 사용 언어 - JavaScript function solution(begin, target, words) { let answer = 1e10 // 최솟값을 구해야하므로 초기에 가장 높은 값으로 초기화 const N = words.length // 변환 가능한 단어의 개수 const visited = Array(N).fill(false) // 해당 단어로 변환을 했었는지 확인을 위함 function sol(n, now, ans) { // 남은 변환 가능 단어 개수, 현재 단어, 변경한 횟수 if (now === target) { // 타겟과 .. 2022. 5. 13. [프로그래머스] 최고의 집합 📖 문제 🧑🏻💻 풀이 과정 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) 알고리즘 스택 3) 풀이 코드 사용 언어 - JavaScript function solution(s) { let stack = [] // 문자열 하나하나 저장할 스택 Array.from(s).forEach(v => { // 문자열을 배열로 변경하여 알파벳 하나씩 반복 if (stack.length === 0) { // 스택이 비어있으면, 문자 추가 stack.push(v) } else if (stack[stack.length-1] === v) { // 스택의 가장 최근 값이 현재 문자랑 동일하면, 짝지.. 2022. 5. 9. 이전 1 2 3 4 5 6 7 8 ··· 18 다음
