Brise

프로그래머스의 문제 종류 중 그리디 문제타입으로 되어 있는 연습문제이다. 문제는 위와 같다. 문제를 풀 수 있는 가장 간단한 방법은 순열 조합을 이용하여 가능한 조합의 수를 구하고 조합으로 만들어 낼 수 있는 가장 큰 수를 찾으면 된다. from itertools import combinations def solution(number, k): c = combinations(list(number), len(number)-k) num_list = map(''.join, c) answer = max(num_list) return answer 하지만 해당 코드를 이용하여 문제를 풀게 되면 몇 개의 문제 이외에는 시간 초과 오류가 발생한다. 문제의 정의에서 number의 자릿수는 최대 100만 자리..

''' 2048 게임의 핵심 중의 하나는 방향키를 움직였을 때 숫자가 합쳐지는 부분입니다. 해당 부분을 reduce 함수로 분리하고, In/Out을 먼저 정의합니다. reduce 함수는 N길이의 l을 입력으로 받고, N길이의 리스트를 반환합니다. 내부 동작으로 숫자들을 한쪽에 모아 합친 뒤 반환하며 반환값은 N길이의 리스트를 반환합니다. 그 뒤로 mv_up/down/left/right함수를 작성하고 최종으로 함수를 활용하기위하여 DFS 를 작성하여 동작시킵니다. Depth는 문제에서 정의한 대로 5로 구현됩니다. ''' import sys # sys.stdin = open("12100.txt", "r") input = sys.stdin.readline N = i..

파이썬은 itertools 패키지를 통하여 순열과 조합 기능을 제공한다. itertools를 이용한 순열과 조합 사용 방법은 아래와 같다. from itertools import combinations, permutations arr = [1,2,3,4] print(list(combination(arr, 2))) print(list(permutations(arr,2))) 하지만 내장된 순열과 조합 기능을 사용할 수 없는 경우(i.e. 코딩 테스트)도 있기 때문에 직접 순열과 조합 기능을 구현하여 사용할 줄 알아야 한다. 직접 구현하는 경우 성는 자체를 올리는 것보다 발상을 이해하여 추후 다시 사용할 수 있도록 간편하는 것이 중요하다고 생각하여 아래와 같이 구현하였다. 아마도 성능 자체는 높지 않으나, 기..

파이썬을 이용하여 다시 풀어본 드래곤 커브 문제이다. 18년도 삼성전자 코딩 테스트에 기출되었던 문제이고, 보통은 스택을 이용하여 푸는 방식이 일반적인 것 같다. 일전에 풀었을 때는 미리 드래곤 커브를 모두 만들어 놓는 방식으로 만들려고 했다. 드래곤 커브에서는 end 기준으로 90도 회전하도록 되어 있어 아래와 같은 수도코드를 이용하여 최대 generation인 10에 맞추어 모든 행렬을 사전에 만들어 놓고 주어진 수에 합성하는 방식으로 짰었다. 거기다가 C로 짜니 코딩하는 시간이 많이 걸릴 수밖에... ARR1 = find end point and transition to [end_x, end_y] = 0 for all point: ARR2[nx; ny] = [cos sin; -sin -cos]*[x..

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요. 제한사항 삼각형의 높이는 1 이상 500 이하입니다. 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다. 입출력 예 triangle result [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 (0)7(0) \|\| (0..

DP문제는 아무래도 재귀 형식으로 표현하여 sub 문제들을 해결하여 큰 문제를 해결할 수있도록 하는 틀을 짜는 능력이 중요한것 같다. 이 문제의 경우에는 생각해보았지만, 해당 틀을 떠올리지 못해서 다른 소스코드를 참고하여 짠 코드이다. 발상 방법이야 여러개 있지만 내가 동작 시킨 코드는 아래와 같다. def calc(A, B): ret = set() for a in A: for b in B: ret.add(a + b) ret.add(a - b) ret.add(a * b) if b != 0: ret.add(a // b) return list(ret) def solution(N, number): answer = 0 # merge plus substract times divide result = dict() ..

그래프를 탐색하며 가장 먼 노드를 찾는 문제이다. 나는 BFS를 이용하여 거리를 구한 뒤 가장 먼노드를 찾았다. def solution(n, edge): answer = 0 v = [set() for _ in range(n+1)] visit = [-1] * (n+1) for e in edge: v[e[0]].add(e[1]) v[e[1]].add(e[0]) def bfs(root): from collections import deque queue = deque() queue.append((root, 0)) visit[root] = 0 while queue: n, l = queue.popleft() for e in v[n]: if visit[e] == -1: visit[e] = l+1 queue.appen..

문제 풀이 상 깊이/너비 우선 탐색 유형으로 풀이되는 문제이다. 내가 풀은 방법은 아래와 같다. def solution(n, computers): answer = 0 visited = [0] * n def dfs(i): nonlocal answer visited[i] = 1 for n, c in enumerate(computers[i]): if c == 1: if 0 == visited[n]: visited[n] = 1 dfs(n) for i in range(n): if visited[i] == 0: dfs(i) answer+= 1 return answer통상 깊이우선탐색을 사용할 때는 스택을 사용하고, 너비우선탐색을 사용할 때는 큐를 사용하는데 이 부분이 현재는 익숙하지가 않아 재귀문법으로 풀이하였다...