본문 바로가기
728x90

분류 전체보기

 (180)
삽입정렬 vs 머지정렬 vs 퀵정렬 삽입정렬// 삽입정렬function insertionSort(arr) { for (let i = 1; i = 0 && arr[j] > currentVal; j--) { arr[j + 1] = arr[j]; } arr[j + 1] = currentVal; } return arr;}데이터 갯수가 10,000 일때데이터 갯수가 100,000 일때삽입 정렬로 구현했을때 걸리는 시간입니다.Data1은 순서대로 숫자가 저장된 배열입니다 Data2는 역순으로 숫자가 저장된 배열입니다Data3은 균등하게 석여있는 배열입니다.삽입 정렬에서 Data1 은 1, 2, 3, 4 … , 1000,0000 까지 순서대로 배열이 존재하기때문에 O(n)의 시간 복잡도를 가질것 같습니다.하지만 Data2 은 ..
프로그래머스 LV 3 여행경로 function solution(tickets) { var answer = []; let len = tickets.length // 알파벳순서 tickets.sort() // 방문 let visited = Array(len).fill(false) const dfs = (now,count,route) => { if(count === len){ answer.push(route) return } for(let i=0;i풀이 및 회고일단 알파벳 순으로 이동하기 때문에 정렬을 해줬습니다.그리고 방문 배열을 만들었습니다.DFS 함수를 만들어 방문하지 않고 출발지가 같은 티켓이면 방문을 하도록 했..
프로그래머스 LV 2 전력망을 둘로 나누기 function solution(n, wires) { let answer = Number.MAX_SAFE_INTEGER; // 최소값을 찾기 위함 // 인덱스는 0부터 전선은 1부터 시작하기 때문에 n + 1 const graph = Array.from(Array(n + 1), () => []); // 인덱스는 노드, 해당 인덱스에 연결된 노드들을 저장 // 각 전선을 연결된 노드들로 그래프에 추가 wires.forEach((wire) =>{ let [from, to] = wire; graph[from].push(to); graph[to].push(from); }) // 출발지점 과 가지않는곳 (연결이 끊긴곳) con..
프로그래머스 LV 1 최소직사각형 function solution(sizes) { let w = 0; let h = 0; for(let i = 0; i 풀이 및 회고sizes 배열을 순회 하면서 가장 큰 값을 한곳(w)에 작은 값을 한곳(h)에 에 모은 다음 가장 큰 값을 곱해줍니다.
프로그래머스 LV 3 단어 변환 from collections import deque def solution(begin, target, words): answer = 0 q = deque() q.append((begin,0)) # 단어 방문 visited = set() while q : w,idx = q.popleft() # 현재 단어랑 target 이랑 같으면 return idx if w == target : return idx for word in words : # 방문하지 않고 한글자만 다르면 q 에 삽입 if word not in visited and sum([w[i] != wor..
프로그래머스 LV 3 네트워크 def solution(n, computers): answer = 0 visited = [False for _ in range(n)] for i in range(n) : if visited[i] == False : dfs(n,computers,visited,i) answer += 1 return answerdef dfs(n,computers,visited,idx) : # 방문처리 visited[idx] = True for i in range(n) : # 다른 컴퓨터이자 연결된 컴퓨터 if i != idx and computers[idx][i] == 1 : # 방문을..
프로그래머스 LV 1 푸드 파이트 대회 def solution(food): answer = '' for i in range(1,len(food)) : for j in range(food[i] // 2) : answer += str(i) reversed_str = "".join(reversed(answer)) answer += '0' answer += reversed_str return answer풀이 및 회고food 배열을 순회해 해당하는 숫자를 추가해줍니다. 그 후 뒤집는 문자열을 준비하고 가운데 0 을 붙여줍니다.
프로그래머스 LV1 숫자 짝궁 def solution(X, Y): answer = '' a = [0,0,0,0,0,0,0,0,0,0] b = [0,0,0,0,0,0,0,0,0,0] for i in X : a[int(i)] += 1 for i in Y : b[int(i)] += 1 for i in range(9,-1,-1) : v = str(i) * min(a[i],b[i]) answer += v if len(answer) == 0 : return '-1' if answer[0] == '0' : return '0' return answer풀이 및 회고처음에는 정렬한 후 숫자를 비교해서 같으면 배열에..
728x90

티스토리툴바