티스토리

나를 위한 기록

검색하기

블로그 홈

나를 위한 기록

cheols.tistory.com/m

김철현 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

[Programmers] 귤 고르기 - level 2 문제 설명 경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다. 예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다. 경화가 한 상자에 담으려는 귤의 개수 k와 귤의 크기를 담은 배열 tangerine이 매개변수로 주어집니다. 경화가 귤 k개를 고를 때 크기가.. 공감수 0 댓글수 0 2023. 1. 31.
[Programmers] 숫자 변환하기 - level 2 문제 설명 자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다. x에 n을 더합니다. x에 2를 곱합니다. x에 3을 곱합니다. 자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요. 제한사항 1 ≤ x ≤ y ≤ 1,000,000 1 ≤ n < y 입출력 예시 x y n result 10 40 50 2 10 40 30 1 2 5 4 -1 나의 풀이 from collections import deque def solution(x, y, n): # BFS를 통해 타겟 숫자 추적 q = deque() q.append(x) ch.. 공감수 0 댓글수 0 2023. 1. 29.
[Baekjoon] 괄호 추가하기 3(python) https://www.acmicpc.net/problem/16639 문제 접근 파일합치기 문제와 비슷한 방식으로 DP를 통해 해결하려고 시도했다. 내가 생각해내지 못했던 것은 연산자에 대한 인덱스 처리와 연산자에 따라 최솟값을 이용해서 최댓값을 만들 수 있는 경우가 있다는 것을 놓치고 있었고 검색을 통하여 힌트를 얻어 문제를 해결했다. 풀이 과정 문제를 푸는 핵심 개념은 Bottom-Up 방식으로 수식을 작은 범위부터 큰 범위로 확장해나가면서 계산하면 된다. 각 구간별 최댓값을 DP 배열에 저장하면서 구간을 확장하면 결국 DP[n][n]에 우리가 구하고자 하는 값이 저장될 것이다. 위의 그림을 코드로 표현하면 아래와 같을 것이다. n은 전체 수식에서 피연산자 갯수를 구한 것이고 (수식의 길이 + 1) /.. 공감수 0 댓글수 0 2022. 11. 27.
[Baekjoon] 우주 탐사선(python) https://www.acmicpc.net/problem/17182 문제 접근 이 문제는 플로이드 워셜 + 순열로 해결해야 하는 문제이다. 출발하는 행성에서 모든 행성을 탐사하는데 걸리는 시간을 구해야 하므로, 최단경로를 구할 때 출발 행성에서 다른 행성까지의 최단경로를 구하는 다익스트라나 밸만포드보다는 모든 행성 간 최단경로를 구할 수 있는 플로이드 워셜 알고리즘을 이용해야 한다. 모든 행성 간 최단경로를 구했으면 방문하는 순서를 결정해야 한다. permutations 함수를 통해 출발 행성을 제외한 나머지 행성들의 순열을 구하고 거리의 합이 가장 작은 경우를 구해주면 된다. 풀이 과정 1. 플로이드 워셜을 통한 모든 정점 간 최단경로 계산 for k in range(N): for i in range(.. 공감수 0 댓글수 0 2022. 11. 22.
[Baekjoon] 빙산(python) https://www.acmicpc.net/problem/2573 문제 접근 오랜만에 정답을 안보고 푼 문제이다. BFS를 이용한 구현문제였다. BFS를 통해 4방향에 인접한 빙산을 탐색하여 빙산의 그룹이 분리되었는지 확인하고 iceberg에 저장된 빙산들을 4방향에 인접한 물의 갯수만큼 빙산의 높이를 빼주면 된다. 풀이 과정 1. 빙산이 분리되었는지 확인 빙산의 위치에서 BFS를 통해 방문한 위치의 갯수와 미리 iceberg 배열에 저장해두었던 빙산의 위치의 갯수가 같으면 분리되지 않은 것이고 다르면 분리된 것이다. 하나의 빙산의 위치에서 BFS를 통해 탐색하면 모든 빙산을 방문할 것이기 때문에 위치의 갯수가 다르면 분리된 것으로 판단한다. def bfs(x, y): visited = [[False] .. 공감수 0 댓글수 0 2022. 11. 20.
[Baekjoon] 타임머신(python) https://www.acmicpc.net/problem/11657 문제 접근 시작 노드에서 각 노드별로 최단경로를 구하는 문제이다. 최단경로를 구하는 알고리즘은 다익스트라와 벨만포드가 있다. 이 문제는 Edge의 음수 가중치가 존재하므로 다익스트라를 이용해서 최단경로를 구하면 제대로된 거리를 구할 수 없다. 따라서 음수 가중치가 있어도 최적해를 찾을 수 있는 벨만포드 알고리즘을 이용해서 문제를 해결해야 한다. 풀이 과정 벨만포드 알고리즘 순서 출발 노드 설정 dist 배열 초기화 모든 간선에 대해 각 간선을 거쳐 다른 노드로 가는 최단 거리 갱신 -> (정점의 갯수 - 1)번 수행 3번이 끝난 후에도 최단 거리가 갱신된다면 음수 사이클이 존재하는 것이다. 이 과정을 코드로 구현해보자. def bellm.. 공감수 0 댓글수 0 2022. 11. 18.
[Baekjoon] 집합의 표현(python) https://www.acmicpc.net/problem/1717 문제 접근 분리집합 문제이다. 분리집합문제는 Union-Find를 이용하여 해결할 수 있다. 이 문제는 문제 입력에 따라 Union연산을 하거나 같은 집합인지 확인하면 되는 문제였다. 주의할 점은 find 함수 작성할 때 최적화를 하지 않으면 시간 초과가 발생할 수 있다. 풀이 과정 1. 합집합 연산 def union(u, v): u = find(u) v = find(v) if u < v: parent[v] = u else: parent[u] = v 2. 최상위 부모 검색 최상위 부모를 검색할 때 루트가 제대로 저장되지 않은 경우는 검색하면서 다시 저장해주어야 시간 초과를 해결할 수 있다. 그냥 재귀를 호출하여 최상위 부모를 검색하면 시간.. 공감수 0 댓글수 0 2022. 10. 29.
[Baekjoon] 숨바꼭질 4(python) https://www.acmicpc.net/problem/13913 문제 접근 BFS를 이용하여 목적지에 도달할 때까지 계속해서 탐색하는 방식으로 문제를 접근했다. 무조건 current - 1, current + 1, current * 2에 해당하는 좌표와 지금까지의 경로를 같이 큐에 삽입하도록 했는데 메모리 초과가 발생했다. 이미 방문한 위치를 또 방문할 뿐더러 중복되는 모든 경로까지 큐에 삽입하게 되기 때문이다. 따라서 dist배열을 통해 이미 방문한 위치를 체크하면서 해당 위치까지 도달하는데 걸리는 시간을 같이 저장했다. 또 경로를 트래킹하기 위해서 foot_print배열에 해당 위치에 이전 위치를 저장하도록 문제를 해결했다. 틀린 코드 ... def bfs(): q = deque() q.appen.. 공감수 0 댓글수 0 2022. 10. 29.
[Baekjoon] 최소비용 구하기 2(python) https://www.acmicpc.net/problem/11779 문제 접근 다익스트라를 이용한 최단경로를 찾는 문제이다. 풀이 과정 다익스트라 알고리즘을 통해 start와 end 사이의 최단경로를 구하도록 한다. 경로도 같이 저장해야 하므로 dist배열을 갱신할 때 부모 노드를 parent배열에 저장하도록 한다. 정답 코드 """ 백준 11779번 최소비용 구하기2 """ import sys import heapq def dijkstra(): dist[start] = 0 queue = [] heapq.heappush(queue, [dist[start], start]) while queue: cost, node = heapq.heappop(queue) if dist[node] < cost: contin.. 공감수 0 댓글수 0 2022. 10. 29.
[Baekjoon] 줄 세우기(python) https://www.acmicpc.net/problem/2252 문제 접근 위상 정렬(Topological Sorting)을 이용하는 문제이다. 위상 정렬은 순서가 정해져 있는 작업들을 차례대로 수행할 때 사용할 수 있는 알고리즘이다. 위상 정렬에 대한 자세한 설명은 풀이 과정을 통해 다루도록 한다. 풀이 과정 1. 위상 정렬이란? -> 순서가 정해져 있는 작업을 차례로 수행해야할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. 위상 정렬은 다음의 조건을 만족해야 적용될 수 있다. 그래프는 방향성을 가진 그래프여야 한다. 그래프에 Cycle이 없어야 한다. 위 두 조건을 한 문장으로 표현하면 위상 정렬은 DAG(Directed Acyclic Graph)인 경우에만 적용이 가능하다는 것이다. 2. .. 공감수 2 댓글수 0 2022. 10. 23.
[Baekjoon] 가장 가까운 공통 조상(python) https://www.acmicpc.net/problem/3584 문제 접근 처음에는 DFS를 통해 자식 노드를 모두 찾으면 해당 노드 번호를 반환하도록 구현했다. 따라서 부모 노드의 자식을 저장하도록 트리를 만들었다. 하지만 결과는... 사실 노드의 갯수가 최대 10000개이기 때문에 메모리 초과가 나올 줄 몰랐다... 고민 끝에 최근 풀었던 Union-Find 문제를 풀었던 기억을 되살려 트리를 만들 때 부모의 자식을 저장하는 것이 아니라 자식의 부모를 저장하도록 하여 문제를 해결하였다. DFS를 이용할 때는 탐색하지 않아도 될 노드를 탐색했는데 트리를 저장하는 방식을 바꾸니까 찾고자 하는 자식의 노드만 탐색하므로 시간 복잡도도 O(logN)으로 해결할 수 있었다. 풀이 과정 문제 풀이 과정을 그림으.. 공감수 0 댓글수 0 2022. 10. 22.
[Baekjoon] 개미굴(python) https://www.acmicpc.net/problem/14725 문제 접근 트리를 생성하면 풀 수 있는 문제이다. 트리를 만들 때 딕셔너리나 리스트를 이용해서 만들 수 있는데 이 문제는 노드의 값이 정수형이 아닌 문자열이므로 Dictionary를 이용하여 트리를 생성하도록 한다. 풀이 과정 1. 트리를 생성한다. 주어진 입력에서 depth별 노드의 정보를 받을 수 있다. 재귀를 통해 입력받은 리스트를 하나씩 트리에 추가한다. def add_tree(tree, nodes): if not nodes: return if nodes[0] not in tree: tree[nodes[0]] = {} add_tree(tree[nodes[0]], nodes[1:]) 2. 트리를 출력한다. 트리를 출력할 때 DFS를.. 공감수 0 댓글수 0 2022. 10. 22.
[Baekjoon] 움직이는 미로 탈출(python) https://www.acmicpc.net/problem/16954 문제 접근 BFS를 이용하여 시작점부터 도착점까지 이동할 수 있는지 판별하는 문제이다. 일반적인 BFS 문제와 다른점은 4방향 탐색이 아닌 현재위치를 포함하여 9방향 탐색을 하는 것이고 탐색을 하는 중간에 배열의 상태가 바뀐다는 것이다. 풀이 과정 9방향 BFS를 구현해주면 된다. 일반적으로 BFS를 구현하면 아래처럼 구현할 것이다. def bfs(x, y): while q: x, y = q.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if ( nx = 8 or ny = 8 or chess[nx][ny] == "#" or visited[n.. 공감수 0 댓글수 0 2022. 10. 18.
[Baekjoon] 로고(python) https://www.acmicpc.net/problem/3108 문제 접근 이 문제를 풀기 위한 아이디어는 사각형끼리 교점이 있으면 같은 그룹으로 묶을 수 있고 같은 그룹이면 연필을 올리는 연산인 PU를 하지 않고도 한번에 그릴 수 있다는 것이었다. 또 시작 위치는 원점이고 방향은 위쪽을 보고 있으므로 사각형 그룹이 원점에서 바로 그릴 수 있으면 PU 명령을 할 필요가 없으나 그렇지 않은 경우는 반드시 PU 명령을 해야한다. 하지만 사각형을 그룹핑하기 위한 방법이 떠오르지 않아 풀이를 참조하여 Union-Find(합집합 찾기)를 이용하면 된다는 것을 알았다. 즉 Union-Find를 통해 사각형을 그룹핑하고 그룹의 갯수를 구하면 PU 명령을 실행해야할 횟수를 알 수 있다. 풀이 과정 이 문제의 풀이 코.. 공감수 0 댓글수 0 2022. 10. 17.
[Baekjoon] 파일 합치기(python) https://www.acmicpc.net/problem/11066 문제 접근 DP 문제이다. i~j까지의 파일을 합치는데 드는 최소 비용을 dp배열에 저장하면서 문제를 해결했다. 풀이 과정 앞서 말한 것처럼 i~j까지의 파일을 합치는데 드는 최소 비용을 dp배열에 저장하면 된다. 예를 들어, 0~2까지의 파일을 합치는 데 드는 최소 비용은 [0, 1~2]와 [0~1, 2] 중 작은 값이 될 것이다. 0~3까지의 파일을 합치는 경우는 [0, 1~3], [0~1, 2~3], [0~2, 3] 중 작은 값이다. 이렇게 최소 비용이 드는 임시 파일의 케이스를 찾고 실제 파일을 합치는데 드는 비용을 더해주면 파일을 합칠 때 드는 최소 비용을 구할 수 있다. 1. 임시 파일의 크기 조합을 구한다 for j in r.. 공감수 0 댓글수 0 2022. 10. 17.
[Programmers] 자연수 뒤집어 배열로 만들기 - level 1 문제 설명 자연수 n을 뒤집어 각 자리 숫자를 원소로 가지는 배열 형태로 리턴해주세요. 예를들어 n이 12345이면 [5,4,3,2,1]을 리턴합니다. 제한사항 n은 10,000,000,000이하인 자연수입니다. 입출력 예시 n return 12345 [5,4,3,2,1] 나의 풀이 리스트의 역순을 구할 때는 인덱스 슬라이싱을 이용하면 좀 더 pythonic한 코드를 작성할 수 있다. def solution(n): return list(map(int, str(n)))[::-1] 공감수 0 댓글수 0 2022. 10. 13.
[Baekjoon] 배열에서 이동(python) https://www.acmicpc.net/problem/1981 문제 접근 풀이 방법이 떠오르지 않아 문제의 알고리즘 힌트와 질문 검색을 통해 문제를 해결하였다. 이 문제는 이분탐색 + BFS로 해결할 수 있다. 최댓값과 최솟값의 차이를 이분탐색을 통해 찾고 BFS를 통해 그 값이 가능한지 탐색하면 된다. 풀이 과정 이분 탐색을 통해 가능한 값을 찾는 것이 핵심! while left end: continue if bfs(start, end): return True return False 마지막으로 BFS를 통해 (0, 0)에서 (n-1, n-1)까지 도달할 수 있는지 검사하면 된다. def bfs(start, end): dx = [-1, 0, 0, 1] dy = [0, -1, 1, 0] visited .. 공감수 0 댓글수 0 2022. 10. 9.
[Baekjoon] 로봇 청소기(python) https://www.acmicpc.net/problem/4991 문제 접근 이 문제는 BFS + 순열을 이용한 문제였다. 더러운 칸의 갯수가 10개를 넘지 않기 때문에 최대 10! 만큼만 연산하면 되었기 때문이다. 그래서 탐색할 더러운 칸의 순서를 permutations 연산을 통해 순열을 구하고 BFS를 통해 하나씩 탐색하면서 지나치는 칸의 갯수를 세어주었다. 하지만 BFS를 통해 매번 칸의 갯수를 연산하는 방식은 시간초과를 해결할 수 없었고, 메모이제이션(Memoization)을 통해 각 더러운 칸 사이를 탐색할 때 지나치는 칸의 갯수를 저장하여 매번 연산하지 않도록 수정했다. 오답 코드 import sys from itertools import permutations from collections.. 공감수 1 댓글수 0 2022. 10. 9.
[Baekjoon] 앱(python) https://www.acmicpc.net/problem/7579 문제 접근 최근에 풀었던 평범한 배낭과 똑같은 문제이다. 평범한 배낭에서 N개의 물품을 합해서 K만큼의 무게를 확보했던 것과 매칭하면 이 문제에서는 N개의 앱을 합해서 M만큼의 메모리를 확보해야 하는 것이다. 단, 이 문제에서는 앱을 비활성화했을 경우의 비용을 최소화하도록 해야 한다. 그렇다면 앱들을 비활성화했을 경우의 비용별 최대 메모리 바이트 수를 dp 배열에 저장하여 문제를 풀도록 하면 된다. 풀이 과정 dp 점화식은 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i]] + memory[i])이다. 테스트 케이스를 기준으로 모든 앱들을 비활성화할 경우 총 비용은 15이다. dp[N][Cost] .. 공감수 1 댓글수 1 2022. 10. 5.
[Baekjoon] 미네랄(python) https://www.acmicpc.net/problem/2933 문제 접근 시뮬레이션 + BFS로 구현하는 문제이다. 전체적으로 문제풀이 과정은 문제에서 제시하는대로 따라서 구현하면 된다. 문제의 핵심 로직은 미네랄 클러스터가 막대기를 던질 때 미네랄이 파괴되면서 클러스터가 분리되는지 확인하는 것이다. 미네랄 클러스터는 동서남북으로 인접한 경우만 클러스터로 인정되므로 가장 밑줄의 미네랄들을 BFS나 DFS로 인접한 4방향을 탐색하고 탐색이 종료된 후에 아직 탐색되지 않은 미네랄이 존재하는 경우는 막대기에 의해 분리된 클러스터로 간주하면 된다. 풀이 과정 문제 풀이 과정은 미네랄 파괴 -> 클러스터 체크 -> 분리된 클러스터 낙하를 구현하면 된다. 1. 미네랄 파괴 for i, height in enum.. 공감수 1 댓글수 0 2022. 10. 2.
[Baekjoon] 피보나치 수 3(python) https://www.acmicpc.net/problem/2749 문제 접근 지금까지 피보나치 수열을 구하는 문제를 풀었을 때는 다음과 같은 방법으로 풀었다. 1. 재귀를 이용한 방법 def fibonacci(N): if N 공감수 0 댓글수 0 2022. 10. 1.
[Programmers] 자릿수 더하기 - level 1 문제 설명 자연수 N이 주어지면, N의 각 자릿수의 합을 구해서 return 하는 solution 함수를 만들어 주세요. 예를들어 N = 123이면 1 + 2 + 3 = 6을 return 하면 됩니다. 제한사항 N의 범위 : 100,000,000 이하의 자연수 입출력 예시 N answer 123 6 987 24 나의 풀이 123 -> "123" -> 1 + 2 + 3 파이썬은 int형 변수의 각 자리 숫자를 str 타입으로 변환하면 아주 간단하게 구할 수 있다. 자릿수를 구하고 싶다면 len(str(n))과 같이 한줄 코딩으로 가능하다. def solution(n): return sum(list(map(int, str(n)))) 공감수 0 댓글수 0 2022. 10. 1.
[Baekjoon] 행렬 제곱(python) https://www.acmicpc.net/problem/10830 문제 접근 N x N 행렬의 곱셈을 구하는 코드는 보통 아래처럼 구현할 것이다. for i in range(N): for j in range(N): for k in range(N): matrix[i][j] += a[i][k] * b[k][j] 시간 복잡도는 O(N^3)이고 N x N 행렬의 B 제곱을 구하는 것이니 O(BN^3)이 될 것이다. 당연히 시간 초과가 날 것이다... 그렇다면 어떻게 효율적으로 행렬의 제곱을 할 수 있을까? 행렬 제곱은 N x N x N... x N처럼 순서대로 처리할 필요는 없다. N x N x N = N x N^2 N x N x N x N x N = N^2 x N^3 와 같이 전체 제곱 수를 반으로 분할하여.. 공감수 0 댓글수 0 2022. 9. 28.
[Programmers] 약수의 합 - level 1 문제 설명 정수 n을 입력받아 n의 약수를 모두 더한 값을 리턴하는 함수, solution을 완성해주세요. 제한사항 n은 0 이상 3000이하인 정수입니다. 입출력 예시 n return 12 28 5 6 나의 풀이 전형적인 약수를 구하는 문제이다. 약수를 구하는 문제는 항상 시간초과에 대비하여 그 수의 제곱근까지만 계산하도록 하자. def solution(n): answer = 0 for i in range(1, int(n ** 0.5) + 1): if n % i != 0: continue answer += i if i == n // i else sum([i, n // i]) return answer 공감수 3 댓글수 0 2022. 9. 28.
[Programmers] 서울에서 김서방 찾기 - level 1 문제 설명 String형 배열 seoul의 element중 "Kim"의 위치 x를 찾아, "김서방은 x에 있다"는 String을 반환하는 함수, solution을 완성하세요. seoul에 "Kim"은 오직 한 번만 나타나며 잘못된 값이 입력되는 경우는 없습니다. 제한사항 seoul은 길이 1 이상, 1000 이하인 배열입니다. seoul의 원소는 길이 1 이상, 20 이하인 문자열입니다. "Kim"은 반드시 seoul 안에 포함되어 있습니다. 입출력 예시 seoul return ["Jane", "Kim"] "김서방은 1에 있다" 나의 풀이 def solution(seoul): answer = seoul.index("Kim") return f"김서방은 {answer}에 있다" 공감수 0 댓글수 0 2022. 9. 26.
[Baekjoon] 백조의 호수(python) https://www.acmicpc.net/problem/3197 문제 접근 아주 단순한 구현문제인 줄 알았다. 그래서 백조끼리 만날 수 있는지 검사하는 함수와 물의 가장자리에 붙어있는 얼음을 녹이는 함수 두 개만 짜면 되는 줄 알았다. 문제에 테스트케이스가 모두 정답이 되어 제출해봤는데 역시는 역시인가.. 처음 문제를 풀었던 방식은 이렇다. 1) 백조끼리 만날 수 있는지 BFS를 통해 검사 2) lake 배열을 매번 체크하면서 물의 가장자리에 있는 얼음을 녹임 def is_can_meet_swan(): visited = [[False] * C for _ in range(R)] start_x, start_y = swans[0] end_x, end_y = swans[1] q = deque() q.appen.. 공감수 1 댓글수 1 2022. 9. 25.
[Baekjoon] 가운데를 말해요(python) https://www.acmicpc.net/problem/1655 문제 접근 이 문제를 접근할 때 가장 단순하게 생각하면 리스트에 숫자를 넣으면서 Sorting 후 중간값을 출력하면 된다고 생각할 것이다. 하지만 제한 시간은 0.1초이고 파이썬 정렬의 시간 복잡도는 O(NlogN)이므로 시간 초과가 나올 것이다. 또 생각했던 방법은 중간값을 저장하는 변수 Center를 두고 Left, Right라는 리스트를 통해 Center보다 작으면 Left에 크면 Right에 넣는 방법을 생각했었다. 하지만 그렇게 되면 중간값을 갱신할 방법이 없었고 다른 사람의 풀이를 통해 Left와 Right를 단순 리스트가 아닌 Heap을 이용하면 중간값을 갱신할 수 있는 솔루션이 될 수 있었다. 따라서 Left를 Max Hea.. 공감수 1 댓글수 1 2022. 9. 24.
[Baekjoon] 평범한 배낭(python) https://www.acmicpc.net/problem/12865 문제 접근 처음 이 문제를 봤을 때는 BackTracking을 이용해 해당 물건을 넣는 경우와 안 넣는 경우를 모두 구하려고 시도했다. 그렇게 되면 시간 복잡도가 O(2^N)이 되므로 최대 2^100번 연산을 해야 하므로 시간 초과가 날 수 밖에 없었다. 검색을 통해 이 문제는 다이나믹 프로그래밍을 통해 해결해야 했고 Knapsack 문제라고 불리는 아주 유명한 문제였다. 풀이 과정 N은 물품의 수이고 K는 배낭 무게이다. 물건을 하나씩 넣는 경우와 안 넣는 경우를 배열에 저장하면서 처리하면 된다. 그렇게 되면 O(NK)이 되고 최대 연산량은 10,000,000이므로 제한 시간을 통과할 수 있다. DP 점화식을 표현하면, dp[i][j].. 공감수 1 댓글수 0 2022. 9. 24.
[Programmers] 문자열을 정수로 바꾸기 - level 1 문제 설명 문자열 s를 숫자로 변환한 결과를 반환하는 함수, solution을 완성하세요. 제한사항 s의 길이는 1 이상 5이하입니다. s의 맨앞에는 부호(+, -)가 올 수 있습니다. s는 부호와 숫자로만 이루어져있습니다. s는 "0"으로 시작하지 않습니다. 입출력 예시 s answer "1234" 1234 "-1234" -1234 나의 풀이 def solution(s): return int(s) 공감수 0 댓글수 0 2022. 9. 21.
[Programmers] 문자열 내 p와 y의 개수 - level 1 문제 설명 대문자와 소문자가 섞여있는 문자열 s가 주어집니다. s에 'p'의 개수와 'y'의 개수를 비교해 같으면 True, 다르면 False를 return 하는 solution를 완성하세요. 'p', 'y' 모두 하나도 없는 경우는 항상 True를 리턴합니다. 단, 개수를 비교할 때 대문자와 소문자는 구별하지 않습니다. 예를 들어 s가 "pPoooyY"면 true를 return하고 "Pyy"라면 false를 return합니다. 제한사항 문자열 s의 길이 : 50 이하의 자연수 문자열 s는 알파벳으로만 이루어져 있습니다. 입출력 예시 s answer "pPoooyY" true "Pyy" false 나의 풀이 이 문제는 아주 간단하게 풀 수 있는 손에 꼽는 문제이다. 대소문자 구분없이 문자열 안에서 p와 .. 공감수 0 댓글수 0 2022. 9. 19.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.