파이문

더 맵게 programmers.co.kr/learn/courses/30/lessons/42626 숫자 목록이 주어지고 거기서 가장 낮은 숫자와, 그 다음 숫자 * 2를 더한 값을 다시 목록에 넣을 수 있는 횟수를 리턴하는 문제이다. 목록을 값에 추가하고, 나올 때 무조건 작은 값이 먼저 나와야 된다는 조건이 있기 때문에 min-heap 을 생각하면 그 다음엔 알맞은 자료구조를 선택하여 구현하면 된다. 파이썬에선 heap, 자바에선 PriorityQueue 를 사용할 수 있다. (만약 큰 수대로 나와야 한다면 값을 추가할 때 -1 을 곱해서 사용하면 된다.) heap 사용하여 풀이 (Python) from heapq import heappush, heappop def solution(scoville, K)..

가장 큰 수 programmers.co.kr/learn/courses/30/lessons/42746 number 배열이 주어졌을 때 원소 조합으로 가장 큰 숫자를 만들어 리턴하는 문제다. 비슷한 문제 / 풀이가 Geeks for Geeks 에 있다. 2가지 풀이 방법이 있는데 첫 번째는 숫자를 문자열로 바꾸는 custom compare 함수를 구현하여 언어에서 제공하는 정렬 함수를 사용하는 것이다. 두 번째는 가장 큰 숫자의 자릿 수 만큼 모든 숫자를 만든 다음에, 새롭게 만든 그 숫자들로 정렬하는 것이다. Custom compare 함수 만들어 풀이 www.geeksforgeeks.org/given-an-array-of-numbers-arrange-the-numbers-to-form-the-bigges..

주식가격 programmers.co.kr/learn/courses/30/lessons/42584 알고리즘 문제 풀이에 자주 보이는, next greater element 랑 비슷한 문제다. 주어진 배열에서 각 인덱스가 i < j 일때 A[i] 와 A[j] 간을 비교하여 j - i 만큼을 정답에 추가하는 문제다. 빠르게 하려고 파이썬으로 풀어보았다. (파이썬에서 list 는 스택과 동일하므로 list 를 사용하였다.) def solution(prices): # 정답의 전체 길이는 prices 와 동일하다. 그래서 prices 길이만큼 0 으로 초기화 시켜주었다. answer = [0 for _ in range(len(prices))] stack = list() # 0 번쨰 값은 미리 스택에 넣어두었다. s..

다리를 지나는 트럭 programmers.co.kr/learn/courses/30/lessons/42583?language=java 대기하는 트럭 리스트(값은 트럭의 무게)가 주어지고, 리스트에 있는 트럭이 다리를 모두 지나는 시간을 리턴하는 문제이다. 단, 다리를 지날 때 다리 위에 있는 트럭들의 무게 합산이 다리가 버틸 수 있는 무게(weight) 보다 적어야 하고 하나의 트럭이 다리를 지나는 시간은 bridge_length 와 같다. 큐와 스택 카테고리에 있어서, 큐로 풀었다. (구현체는 deque 쓰긴 함) import java.util.ArrayDeque; import java.util.Queue; class Solution { public int solution(int bridge_length..

단어 변환 https://programmers.co.kr/learn/courses/30/lessons/43163 DFS 풀이 begin 과 한 글자 차이가 나는 단어를 찾고 그 단어에서 부터 모든 words 와 (역시 한 글자 차이가 나는 ) 비교해 가며 구현한다. 이 때 정답은 가장 적은 변화로 target 을 찾는 경우의 수를 구하는 문제다. 우선 처음 for 문으로 모든 words 에 대해 비교한다. 즉 begin -> 1번 단어 -> .... -> 종료 와 begin -> 2번 단어 -> ... -> 종료 와 같이 begin 바로 다음에 비교할 단어를 words 의 모든 단어를 대상으로 하는 것이다. 이 구현대로 하면 1 번 단어 -> 2번 단어와 2번 단어 -> 1번 단어와 중복되는 계산이 있을..

네트워크 https://programmers.co.kr/learn/courses/30/lessons/43162 DFS 풀이 문제 설명이 길지만, 축약하자면 undirected graph 에서 연결 되지 않은 그룹이 몇개 있는지에 대한 문제다. DFS 로 그래프를 따라 가되, 이미 방문 했던 노드면 패스하고 방문하지 않았던 노드면 다시 계속 따라가게 구현하면 된다. 노드의 방문에 대한 여부는 미방문(0), 누군가가 방문 하고 있는 중 (1), 방문 완료(2) 로 확인할 수 있지만... 문제에선 사실 여기까진 필요없고 단순히 boolean 으로 확인하면 된다. (만약 directed graph 라면 이 알고리즘을 써야 한다. 참고) class Solution { public int dfs(int i, int..

타겟 넘버 숫자 배열이 주어지고, 각각을 더하거나 빼서 target 을 만들 수 있는 모든 경우의 수를 구하는 문제였다. 자바로 풀었다. https://programmers.co.kr/learn/courses/30/lessons/43165 DFS 풀이 재귀로 모든 경우의 수(더하고, 빼고) 로 다 넣어서 구한다. 만들어진 최종 값이 target 과 동일할 경우 1을 리턴하고 이 값을 누적한 것이 결과 값이다. class Solution { public int dfs(int prev, int index, int[] numbers, int target) { if (index >= numbers.length) { if (target == prev) { return 1; } return 0; } int cur1..

540. Single Element in a Sorted Array(https://leetcode.com/problems/single-element-in-a-sorted-array/#/description) 어떤 List에 int 값이 들어있는데 하나의 숫자만 한개가 있고, 나머지는 모두 두개씩 있을 때, 그 하나만 존재하는 숫자를 리턴하는 것입니다. for문 두번 돌리면 간단히 해결하지만 조건이 붙었습니다. 공간 복잡도 O(1)에, 시간 복잡도가 (logN)입니다. logN이기 때문에 분할해야 하는데, 저는 재귀로 나누어가면서 풀었습니다.List의 정 가운데를 자른다고 생각하면 현재 숫자를 기준으로 왼쪽이 홀수개의 리스트면 왼쪽에 찾고자 하는 숫자가 있을 것이고 오른쪽이 홀수개의 리스트면 오른쪽에 있을..

101. Symmetric Tree(https://leetcode.com/problems/symmetric-tree/#/description) 대칭이 되는 트리인지 아닌지를 판별하는 문제입니다.아래와 같이 가운데(?) 를 기준으로 접혀진다면(대칭이 된다면) True를 리턴하고 1 / \ 2 2 / \ / \ 3 4 4 3한쪽이 비거나, 다른 숫자가 들어가거나 등등 대칭이 되지 않는다면 False를 리턴합니다. 1 / \ 2 2 \ \ 3 3 Easy 문제이기 때문에 어렵게 생각할 필요가 없습니다.문제 그대로 맨 왼쪽은 맨 오른쪽과 같아야 하고, 가장 왼쪽의 오른쪽은 (형제 노드는) 가장 오른쪽의 왼쪽 노드 (형제 노드)와 같으면 됩니다. 재귀로 계속 체크해나가면서, None이면 가장 끝의 노드이니 그 때..