파이문

더 맵게 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..

문제 설명 링크드 리스트가 주어지는데, 상수의 공간 복잡도와 O(nlogn) 의 시간 복잡도로 정렬하는 문제다. 코드는 여기서 확인 가능하다. 솔루션 꼼수 가장 쉬운 방법은 링크드 리스트를 배열로 만들어서 언어에 built-in 된 sort 함수를 사용하는 것이다. 참고로 python 은 timsort 라는 알고리즘으로 sort 가 구현되어 있다. 아니면 sort 함수 말고 직접 정렬을 구현하면 될 것 같다. 하지만 이러면 constant space complexity 를 만족할 수가 없다. 두뇌 풀가동 merge sort 로 하면 될 것 같았다. 이때 절반을 divide 해야 하는데 배열이랑 다르게 사이즈를 알 수가 없다. 이를 위해 fast-slow 로 노드를 순회한다. 이는 tortoise-hare..

문제 설명 HashMap 을 구현하는 문제다. Python 으로 풀었다. 전체 코드는 여기서 볼 수 있다. 솔루션 Java의 HashTable 구현과 비슷하게 풀었다. 리스트를 두고 key 와 리스트 사이즈간의 hash 값을 구해서 리스트의 인덱스로 사용하였다. 인덱스가 겹칠 경우 (hash collision) 링크드리스트로 노드를 만들어서 넣어두었다. class Node: def __init__(self, key=None, value=None): self.key = key self.value = value self.next = None def __str__(self): return "Node(key:%s, value:%s, next:%s)" % (self.key, self.value, self.next..

NQueen 문제 전형적인 DFS 문제다. 놓을 수 있는 자리에 퀸을 놓고 그 다음 자리(다음 row 혹은 다음 col) 에 퀸을 놓을 수 있는지, 재귀로 확인한다.N*N 보드에는 무조건 N개의 퀸이 와야 하는데, 그러려면 한 줄 (row 는 물론이고 col) 에 무조건 퀸이 하나 있어야 한다. 그러니, 즉 줄 단위로 확인해 가면서 퀸을 놓는지 확인하고, 놓을 수 있다면 그 다음 줄로 넘어가는 DFS 인 것이다. 물론 모든 칸을 다 확인해가면서 자리를 찾을 필요는 없고, 퀸이 절대로 있을 수 없는 자리를 가지치기 하면 된다. 퀸은 다른 퀸이 있는 자리에서 세로/가로/좌 대각선/우 대각선에 해당 하는 곳은 위치할 수 없다.그러니, 처음에 퀸이 있을 수 있는 자리에 임의의 값 1을 대입하고, 그 다음 줄로 ..