[프로그래머스💯] 코딩테스트 연습 > (DFS/BFS) > 여행경로 / Python 문제풀이
해답) from collections import defaultdict def solution(tickets): START = "ICN" citiesDests = defaultdict(list) for ticket in tickets: # 한도시당 edge 수를 계산 citiesDests[ticket[0]].append(ticket[1]) for city in citiesDests.keys(): citiesDests[city].sort() # print(citiesDests) stack = [] res = [] def Go(start): stack = [] stack.append(start) if len(citiesDests[start]) == 0: # print("현재 stack => ", stack)..
2020. 3. 4.
[프로그래머스💯] 코딩테스트 연습 > 동적 계획법 > 카드 게임
해답) import sys sys.setrecursionlimit(10**6) global cached cached = [[-1 for _ in range(2000)] for _ in range(2000)] def dump(l, r, L, R, lA, rA): global cached if l == L or r == R: return 0 if cached[l][r] != -1: return cached[l][r] if rA[r] < lA[l]: cached[l][r] = max(dump(l+1, r, L, R, lA, rA), dump(l+1, r+1, L, R, lA, rA), (dump(l, r+1, L, R, lA, rA) + rA[r])) else: cached[l][r] = max(dump(l+..
2020. 3. 2.
[프로그래머스💯] 코딩테스트 연습 > 동적 계획법 > N으로 표현 (JavaScript)
해답) const cached = Array(10) .fill(null) .map(() => Array()) function N_n(N, n) { let answer = 0 for (let i = 0; i { if (v1 !== 0) Nn.push(parseInt(v2 / v1, 10)) if (..
2020. 2. 28.
[프로그래머스💯][JS] 코딩테스트 연습 > 탐욕법(Greedy) > 섬 연결하기
해답) const makeDisjointSet = (islandList, n) => { for (let i = 0; i { if (island.pi === island.me) return island else { return findSet(islandList, islandList[island.pi]) } } const link = (island1, island2) => { if (island1.rank > island2.rank) island2.pi = island1.me else island1.pi = island2.me if ..
2020. 2. 9.
[프로그래머스💯] 코딩테스트 연습 > 힙(HEAP) > 이중우선순위큐
해답) def solution(operations): q = [] for i in operations: if i[0] == "I": q.append(int(i[2:])) elif i == "D 1" and len(q)!=0: q.pop(q.index(max(q))) elif i == "D -1" and len(q)!=0: q.pop(q.index(min(q))) if len(q) == 0 : return [0,0] return [max(q), min(q)] 풀이) 그냥 문제 말 그대로 조건문만 걸고 풀었습니다. 이중순위 뭐시기로 머리쓰기 귀찮아서 혹시나 하고 해봤는데 바로 되더라구요... 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
2020. 1. 26.
[프로그래머스💯] 코딩테스트 연습 > 완전탐색 > 카펫
해답) def solution(brown, red): answer = [] wid_hei_sum = int(brown/2 + 2) for height in range(1,wid_hei_sum): width = wid_hei_sum-height redsum = (width-2)*(height-2) if redsum == red : answer.append(width) answer.append(height) break return answer red는 안에 직사각형이고 brown 은 직사각형을 감싸는 테두리입니다. 수학적으로 생각해본다면 테두리 가로세로에서 각각 -2 를 한 길이가 직사각형의 가로세로 입니다. 세로의 길이를 1부터 높여가며 완전탐색을 돌면서 red 타일 개수가 일치하는지를 찾습니다. 출처: ..
2020. 1. 25.
[프로그래머스💯] 코딩테스트 연습 > (DFS/BFS) > 여행경로 / Python 문제풀이
해답) from collections import defaultdict def solution(tickets): START = "ICN" citiesDests = defaultdict(list) for ticket in tickets: # 한도시당 edge 수를 계산 citiesDests[ticket[0]].append(ticket[1]) for city in citiesDests.keys(): citiesDests[city].sort() # print(citiesDests) stack = [] res = [] def Go(start): stack = [] stack.append(start) if len(citiesDests[start]) == 0: # print("현재 stack => ", stack)..
[프로그래머스💯] 코딩테스트 연습 > 동적 계획법 > 카드 게임
해답) import sys sys.setrecursionlimit(10**6) global cached cached = [[-1 for _ in range(2000)] for _ in range(2000)] def dump(l, r, L, R, lA, rA): global cached if l == L or r == R: return 0 if cached[l][r] != -1: return cached[l][r] if rA[r] < lA[l]: cached[l][r] = max(dump(l+1, r, L, R, lA, rA), dump(l+1, r+1, L, R, lA, rA), (dump(l, r+1, L, R, lA, rA) + rA[r])) else: cached[l][r] = max(dump(l+..
[프로그래머스💯] 코딩테스트 연습 > 동적 계획법 > N으로 표현 (JavaScript)
해답) const cached = Array(10) .fill(null) .map(() => Array()) function N_n(N, n) { let answer = 0 for (let i = 0; i { if (v1 !== 0) Nn.push(parseInt(v2 / v1, 10)) if (..
[프로그래머스💯][JS] 코딩테스트 연습 > 탐욕법(Greedy) > 섬 연결하기
해답) const makeDisjointSet = (islandList, n) => { for (let i = 0; i { if (island.pi === island.me) return island else { return findSet(islandList, islandList[island.pi]) } } const link = (island1, island2) => { if (island1.rank > island2.rank) island2.pi = island1.me else island1.pi = island2.me if ..
[프로그래머스💯] 코딩테스트 연습 > 힙(HEAP) > 이중우선순위큐
해답) def solution(operations): q = [] for i in operations: if i[0] == "I": q.append(int(i[2:])) elif i == "D 1" and len(q)!=0: q.pop(q.index(max(q))) elif i == "D -1" and len(q)!=0: q.pop(q.index(min(q))) if len(q) == 0 : return [0,0] return [max(q), min(q)] 풀이) 그냥 문제 말 그대로 조건문만 걸고 풀었습니다. 이중순위 뭐시기로 머리쓰기 귀찮아서 혹시나 하고 해봤는데 바로 되더라구요... 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
[프로그래머스💯] 코딩테스트 연습 > 완전탐색 > 카펫
해답) def solution(brown, red): answer = [] wid_hei_sum = int(brown/2 + 2) for height in range(1,wid_hei_sum): width = wid_hei_sum-height redsum = (width-2)*(height-2) if redsum == red : answer.append(width) answer.append(height) break return answer red는 안에 직사각형이고 brown 은 직사각형을 감싸는 테두리입니다. 수학적으로 생각해본다면 테두리 가로세로에서 각각 -2 를 한 길이가 직사각형의 가로세로 입니다. 세로의 길이를 1부터 높여가며 완전탐색을 돌면서 red 타일 개수가 일치하는지를 찾습니다. 출처: ..