본문 바로가기

알고리즘

[programmers] 폰켓몬 로직 종류를 나열시킨후, 반보다 갯수가 많으면 최대값은 반이고, 반보다 작으면 종류모두를 하나씩 가지면 되는 것이다. 코드 더보기
[programmers] 타겟넘버 로직 이렇게 진행된다고 생각하면, 처음에 1일 넣어두고, 1에서 +1, -1한 값을 넣는다. 이후 2, 0에서 +1, -1한 값을 넣는다. 코드 def solution(numbers, target): answers = [0] for number in numbers: temp = [] for answer in answers: temp.append(answer + number) temp.append(answer - number) answers = temp cnt = 0 for i in answers: if i == target: cnt += 1 return cnt 주의할 점 - 원래는 ['+', '-']조합으로 풀려고 했는데, 4개조합만 해도 5040개의 경우의 수가 나온다. 더보기
[programmers] 구명보트 로직 구명보트는 2명만 탈 수 있다. 사람이 결국 모두 다 보트를 타야하니까, 몸무게순으로 정렬한 후, 가장 몸무게 적은 사람(l)이랑 많은 사람(h)을 같이 태우려 해본다. 먄약 l + h가 limit보다 작으면 ok, 크면 h인덱스를 하나 줄여서 비교해본다. h인덱스가 l인덱스보다 클때 진행한다 코드 def solution(people, limit): # 최대 2명씩 탄다. people = sorted(people) # [40, 50, 60, 80] i = 0 j = len(people) - 1 cnt = 0 while i < j: if people[i] + people[j] 더보기
[programmers] 카펫 로직 brown + yellow로 가능한 곱 조합을 나타낸다. 이후 for문을 돌면서 양옆, 위아래 1개씩 (총 2개씩) 빼서 곱한 값이 yellow면 답이다 코드 def solution(brown, yellow): total = brown + yellow possible = [] for i in range(total, 2, -1): if total % i == 0 and i >= total // i: possible.append([i, total // i]) for i in possible: if (i[0] - 2) * (i[1] - 2) == yellow: return i 더보기
[programmers] 단속카메라 로직 - 경로가 큰거부터 둔 다음에 단속 카메라를 앞쪽에 두면 뒤에 경로랑 겹치는 것이 있다면, check에 표시한다 코드 def solution(routes): routes = sorted(routes, reverse=True) check = [0] * len(routes) cnt = 0 camera = 0 for i in range(len(routes)): if check[i] == 0: camera = routes[i][0] cnt += 1 for j in range(i + 1, len(routes)): if routes[j][0] 더보기
[programmers] 후보키 로직 1. 우선 가능한 열의 조합을 모두 만든다(itertools.combination) 2. 각각 유일하게 식별이 가능한지 확인한다. (unique함수 사용) 3. 유일한 것들 중에 최소성을 만족하는 것만 남긴다 -> 부분집합 사용 코드 from itertools import combinations from copy import deepcopy def solution(relation): def unique(row, co): check = [] for item in relation: check.append(tuple(item[idx] for idx in co)) if len(set(check)) == row: return True return False row = len(relation) column =.. 더보기
[programmers] 다리를 지나는 트럭 로직 다리를 건너는 트럭(bridge), 대기트럭(truck_weights)를 while문을 돌면서 초가 변할때 마다 변경해준다. 이때, bridge = [0] * bridge_length를 해서 이동하는 것을 하나씩 보여준다. bridge의 합이랑 truck_weights의 첫번째 값(=bridge에 들어갈 값)을 더했을 때, weight보다 작거나 같으면 bridge에 넣어준다. 이때 bridge의 칸을 한칸씩 옮긴다(pop(0)을 통해) bridge변화 과정 time bridge truck_weights 0초 [0, 0] [7, 4, 5, 6] 1초 [0, 7] [4, 5, 6] 2초 [7, 0] [4, 5, 6] 3초 [0, 4] [5, 6] 4초 [4, 5] [6] 5초 [5, 0] [6] 6초.. 더보기
[programmers] 네트워크 로직 문제가 처음에 잘 이해가 안갔다,,,(난 바보다.,,) n = 3 computers = [[1, 1, 0], [1, 1, 0], [0, 0, 1]] 답 : 2 -> why? 1,2가 하나의 네트워크, 3이 하나의 네트워크 n = 3 computers = [[1, 1, 0], [1, 1, 1], [0, 1, 1]] 답 : 1 -> why? 1,2,3이 하나의 네트워크 - visit으로 확인하면서 bfs를 사용한다. 방문한 곳(i)은 visit[i] = 1로 바꿔주고 bfs를 이용하면서 연결된 부분을 찾아낸다. bfs문에 들어간 횟수 = 네트워크 갯수이다. 따라서 while을 한번 다 돌면 cnt += 1을 해준다 코드 from collections import deque def solution(n, .. 더보기

티스토리툴바