알고리즘 문제풀이210 [프로그래머스] 네트워크 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 각 컴퓨터를 반복하면서 DFS 탐색을 하여 연결 관계를 확인하였습니다. 컴퓨터를 반복하던 중 이미 네트워크가 속한것을 확인한 경우, 건너뛰며 아직 속하지 않은 컴퓨터들을 탐색하며 네트워크 개수를 확인하였습니다. 2) 알고리즘 DFS 3) 풀이 코드 사용 언어 - JavaScript function solution(n, computers) { let answer = 0 // 정답 변수 let visited = Array(n).fill(0) // 각 노드의 방문 여부를 저장 let linked = Array(n).fill(0).map(() => []) // 각 노드별 연결 관계 (2차원 배열) function dfs(start) { // DFS 탐색 le.. 2022. 5. 5. [프로그래머스] 타겟 넘버 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 DFS 탐색을 실시하여, 각 숫자를 더하거나 빼면서 재귀로 탐색하였습니다. 2) 알고리즘 DFS 재귀 3) 풀이 코드 사용 언어 - JavaScript function solution(numbers, target) { let answer = 0 // 정답 변수 function dfs(n, ans) { // dfs 탐색 함수 if (n >= numbers.length) { // numbers 길이만큼 탐색 했다면 if (ans === target) { // 현재까지 정답이 타겟 숫자와 동일하면 answer++ // 정답 증가 } return } dfs(n + 1, ans + numbers[n]) // 현재 숫자를 더하기 dfs(n + 1, ans - n.. 2022. 5. 5. [프로그래머스] 오픈채팅방 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 유저들의 기록에 대해서 forEach 를 이용하여 입장과 퇴장, 이름 변경에 대해 구분하여 로직을 수행하였습니다. 유저 아이디를 키값으로 갖고, 유저 이름을 값으로 하는 객체를 생성하여 관리하였습니다. 이후 로그를 map 을 이용하여 반복하였고, 유저 아이디를 유저 이름으로 변경하였습니다. 2) 알고리즘 문자열 3) 풀이 코드 사용 언어 - JavaScript function solution(record) { let answer = []; // 정답 리스트 let logs = []; // 들어가거나 나간 로그 기록들 let user = {}; // 유저 아이디 정보, 유저아이디: 이름 record.forEach(v => { let splited = v.. 2022. 5. 5. [프로그래머스] 기능개발 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 가장 앞에 있는 작업이 종료 되어야 이후 작업들도 순서대로 배포가 가능하므로, shift 를 이용하였습니다. shift 를 이용하여 앞의 작업부터 순서대로 확인을 하며 진행 시키고, 작업 진행도를 추가시킨 후 push 를 이용하여 뒤에 추가하는 방식을 이용하였습니다. 2) 알고리즘 큐 3) 풀이 코드 사용 언어 - JavaScript function solution(progresses, speeds) { let answer = [] // 정답 배열 let taskIdx = 0 // 가장 앞에 있는 작업의 인덱스 let progress = progresses.map((v, i) => [v, i]) // 프로세스 내역들을 인덱스와 함께 저장 while (.. 2022. 5. 4. [프로그래머스] 베스트앨범 📖 문제 🧑🏻💻 풀이 과정 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차원 배열의 각 좌표에 숫자 값이 적혀있고, 상하좌우로 인접한 좌표의 값의 차이에 따라 사다리를 사용하게 되는데, 사다리 이용하는 비용을 최소로 하는 방법을 구하여야 했습니다. 어느 한 좌표를 시작으로 하여 사다리 없이 이동이 가능한 좌표들을 모두 방문합니다. DFS 로 탐색하는 중에 인접한 좌표와 높이 차이가 있어 사다리가 필요한 경우에, 높이 차이의 값과 인접한 좌표를 최소힙에 기록하였습니다. 이후 모든 좌표를 방문하지 못하였을 경우, 최소힙에서 높이 차이가 가장 적은 다음 좌표를 이용하였습니다. 다음 좌표에서도 사다리 없이 이동 가능한 모든 좌표를 방문하며, 높이 차이를 최소힙에 기록하였습니다. 2) 알고리즘 DFS 최소힙 3) 풀이 코드 사용.. 2022. 4. 28. [프로그래머스] 다단계 칫솔 판매 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 수익을 벌어들인 노드(사람)에서 시작하여 부모 노드를 따라 올라가며 수익을 분배하는 문제였습니다. 수익을 벌어들인 노드를 시작으로 하여 최상위 노드까지 DFS 를 이용하여 탐색하였습니다. 2) 알고리즘 DFS 재귀 3) 풀이 코드 사용 언어 - Python import sys sys.setrecursionlimit(10000) def solution(enroll, referral, seller, amount): enroll_idx = {} # 사람 명단이 주어진 순서대로 출력이 필요하므로 '이름': '번호' 형태의 딕셔너리 필요 result = [0] * len(enroll) # 수익금 정답을 저장할 리스트 def setIdx(): # 사람들 번호를 .. 2022. 4. 27. [프로그래머스] 디스크 컨트롤러 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 작업의 평균 시간을 줄이기 위해서 현재 대기하는 작업들의 개수를 최대한 줄여주어야 합니다. 그래서 최소힙을 이용하여 작업이 시작되는 순서대로 작업을 가져왔습니다. 작업을 처리할 수 있는 경우에 대기 명단에 넣었고, 작업이 빨리 끝나는 순서대로 작업을 완료하였습니다. 2) 알고리즘 최소힙 3) 풀이 코드 사용 언어 - Python import heapq def solution(jobs): N = len(jobs) # 평균을 구하기 위한 작업의 개수 heapq.heapify(jobs) # 작업들을 최소힙으로 만듦 ms = 0 # 현재 작업의 시간 answer = 0 # 순수 작업한 시간 waiting = [] # 작업 대기 명단 while jobs or .. 2022. 4. 26. [프로그래머스] 가장 먼 노드 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 기준 노드에서 가장 멀리 떨어진 노드의 개수를 구하는 문제였습니다. 다익스트라를 이용하여 가장 멀리 있는 노드의 거리를 구한 이후 해당 거리에 있는 노드의 개수를 확인하였습니다. 2) 알고리즘 다익스트라 3) 풀이 코드 사용 언어 - Python import heapq def solution(n, edge): linked = [[] for _ in range(n+1)] # 노드의 연결 관계 distance = [0] * (n+1) # 노드들의 거리 for a, b in edge: # 노드 연결 관계 정리 (양방향) linked[a].append((1, b)) linked[b].append((1, a)) def dijkstra(start): # 다익스트.. 2022. 4. 25. 이전 1 ··· 3 4 5 6 7 8 9 ··· 18 다음
