본문 바로가기

알고리즘

 (54)
무식하게 풀기 알고리즘 문제를 풀 때 공부를 열심히 할수록 복잡하지만 우아한 답안을 만들고 싶은 마음이 커지기 마련이고, 그래서 바로 앞에 보이는 쉽고 간단하며 틀릴 가능성이 낮은 답안을 간과하기 쉽다. 이런 실수를 피하기 위해 문제를 마주하고 나면 가장 먼저 스스로에게 물어보자. 무식하게 풀 수 있을까? 흔히 전산학에서 무식하게 푼다 (brute force)라는 말은 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미한다. 이렇게 가능한 방법을 전부 만들어 보는 알고리즘을 가리켜 흔히 완전탐색(exhaustiive search)라고 부른다. 완전 탐색은 사실 컴퓨터의 장점을 가장 잘 이용하는 방법이다. 컴퓨터의 최대 장점은 결국 속도가 빠르다는 것이기 때문이다. 특히 현실세..
1268. 임시 반장 정하기 문제 보러가기 🅰 설계 반의 정보를 입력으로 받고, N명이 같은 반이었던 사람의 수를 카운팅하기 위해서 cnt 라는 리스트를 선언한다. cnt = [0] * N 그 후엔, N명을 순환해야하는데, 이때 5개의 학년에 대해서 순환해야하고, 그리고 순환할 때 자기 자신과는 비교하면 안된다. 비교의 기준이 되는 학생과 나머지 학생과 같은 반 이었던 적이 있으면 visited 를 True 로 바꾼다. 마지막에는 visited 의 True 값의 합을 cnt 의 각 학생에 해당하는 곳의 인덱스에 저장한다. ✅ 후기 // 새롭게 알게되거나 공유해서 알게된 점 세로로 나열된 변수들을 관리하기 위해서 새로운 리스트를 만들었고 그 리스트에 변수들을 넣었다.(몇 반이었는지) 어떠한 학년에서 같은 반이 었던 아이들은 반복문을 ..
12865. 평범한 배낭 (with 시온) 오늘 소마 발표가 끝나고 회의실에서 시간이 남아서 평범한 배낭 문제를 풀었다. 옛날에 답지를 보면서 풀었었는데 오늘 제대로 이해했다. (시온이가 제대로 이해시켜줌) 시온이가 말한 접근 방법은 다음과 같다. 우선 dp에는 base case와 점화식이 존재한다. 또한 부분 문제 -> 전체문제로 확장시켜나가는 접근이 좋다고 한다. 배낭문제에서는 단순하게 O(2^n)의 (n은 물건의 개수) 시간 복잡도로 답을 구할 수 있다. 하지만 문제에서 물품의 수는 100개이기 때문에 이렇게 풀면 안된다. 다이나믹 프로그래밍으로 접근하는 방법은 다음과 같다. 물건 하나씩 하나씩 테이블에 기록하며 접근한다. 이 때 점화식은 다음과 같다. dp[here][capacity] = max(dp[here-1][capacity], dp..
13334. 철로 h,o의 범위가 매우 크기 때문에 완전 탐색은 배제한다. 이 문제는 heap 자료구조를 사용한다. 입력을 받을 때 주의할 점은 정렬되어서 입력을 주지 않아서 sorted로 정렬 시켜줘야한다. 그 후에, 끝 위치 기준으로 정렬을 해준다. -> 끝 위치에서 d만큼 앞으로 가서 포함되는것 체크 할 것이므로 가장 가까운 끝 부터 찾는다. 정렬된 구간에서 d만큼 거슬러 올라간 부분을 lim으로 두고, lim보다 start가 이상이면 힙에 넣어준다. 즉 포함되는 구간이다. 그리고 마지막 조건으로 힙이 존재하고 힙의 첫번째 원소가 lim보다 작다면 구간에 포함되지 않으므로 모두 빼준다. 힙을 생각하는 과정이 어려운 문제 같다. 하지만 비슷한 느낌의 문제를 풀어본적이 있어서 생각해 낼 수 있었다. import sys,..
1195. 킥다운 문제의 상황을 고려하려면 작은 부분이 큰 부분을 일직선으로 통과하면 된다. 혹은 반대도 가능하지만 나는 작은거를 기준으로 생각했다. 통과하면서 체크를 해주고 조건에 부합하면 길이를 계산해고 조건에 부합하지 않으면 한칸 옮긴다. 한 칸씩 전진하는 것을 그림으로 나타내보면 다음과 같다. a 배열과 b배열의 숫자의 합이 3이하가 된다면 두개를 조립할 수 있으므로 조건에 부합한다. 이를 바탕으로 코드를 작성하면 다음과 같다. a = input() a = [int(i) for i in a] b = input() b = [int(i) for i in b] ans = [] if len(a) < len(b): a, b = b, a for i in range(len(a) + len(b) + 1): c = [0] * (l..
16968. 배열 복원하기 문제에서는 원본 배열을 줬고, 배열을 x축 y축으로 이동한 후의 배열까지 줬다. 그렇다면 기본 논리는 이동후의 배열에서 왔던 곳으로 다시 돌아가는 것이다. 그런데 이동후 겹쳤으면 그 수를 더하므로 겹쳤는지 겹치지 않았는지가 매우 중요하다. 문제의 첫번째 예제를 그림으로 표현하면 다음과 같이 겹치는 부분이 생긴다. 이 겹치는 부분은 다르게 관리를 해야 문제를 풀 수 있다. import sys input = sys.stdin.readline h, w, x, y = map(int,input().split()) board = [list(map(int,input().split())) for _ in range(h + x)] prototype = [[0 for _ in range(w)] for _ in range(..
139. Word Break 두가지 컨셉으로 접근할 수 있다. 첫째. BFS 인덱스 0부터 시작해서 특정 단어의 마지막 인덱스보다 1큰값을 큐에 넣어주면서 bfs진행 const wordBreak = function(s, wordDict) { const set = new Set(wordDict); const visited = new Set() const q = [0] while (q.length) { const start = q.shift() if (!visited.has(start)) { for (let end = start + 1; end { if (wordDict == null || wordDict.length === 0) return false; const set = new Set(wordDict); const dp = Arr..
[2021 KAKAO BLIND RECURITMENT] 메뉴 리뉴얼 코스개수를 순회하면서 주문할 수 있는 개수에 따른 combination을 만들어주고 가장 많이 나온 아이를 answer에 넣어주는 방법. from itertools import combinations from collections import Counter def solution(orders, course): answer = [] for c in course: temp = [] for order in orders: combi = combinations(sorted(order), c) temp += combi counter = Counter(temp) if len(counter) != 0 and max(counter.values()) != 1: answer += [''.join(f) for ..

티스토리툴바