본문 바로가기

알고리즘/백준

 (22)
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(..
15591. Mootube 처음에 MST인가? 라는 생각을 가졌는데 결국 이문제는 탐색을 해야하는 문제이다. 주어진 노드 관점에서 bfs를 진행해야 유사도를 측정해서 개수를 셀 수 있다. 유사도라는 것을 모든 연결들의 유사도중의 최솟값으로 정했으므로 노드와 노드사이의 거리가 k보다 작다면 방문자체를 할 필요가 없다. import sys from collections import deque input = sys.stdin.readline INF = int(1e9) def bfs(start, k): global graph visited = [False] * (N+1) q = deque() q.append(start) count = 0 while q: now = q.popleft() visited[now] = True for n_n, ..
1914. 하노이 탑 옛날에 하노이 탑을 직접 해봐서 규칙이 있다는 것을 알았다. 하지만 코드로 구현하는데 어려움을 겪었다. 재귀 호출을 통해 구현할 수 있는데 재귀함수 하나를 정의해야한다. f(n,a,b,c) → n개의 원판이 a기둥에 있을 때, c기둥으로 모두 이동 시키는 함수 n-1개의 원판을 2번기둥으로 옮김 1번 기둥에 남아있는 한개의 원판을 3번으로 2번기둥에 있는 n-1개의 원판을 3번 기둥으로 def f(n, a, b, c): if(n == 1): print(a, c, sep = " ") else: f(n-1, a, c, b) f(1, a, b, c) f(n-1, b, a, c) n = int(input()) print(2**n-1) if(n
10819. 차이를 최대로 풀이 방법은 크게 2가지로 생각해 볼 수 있을 것 같다. 첫번째는 파이썬의 permutations를 이용. 두번째는 dfs 가장 직관 적인 풀이는 다음과 같다. import sys from itertools import permutations input = sys.stdin.readline n = int(input()) a = list(map(int, input().split())) cases = list(permutations(a)) answer = 0 for case in cases: mid_sum = 0 for i in range(n - 1): mid_sum += abs(case[i] - case[i + 1]) answer = max(mid_sum, answer) print(answer) 다음으로 ..

티스토리툴바