백준-풀이

오답 여부: o 편집 시간: 2022년 3월 14일 오후 1:21 코드 Algorithm/11053.py at main · Junroot/Algorithm Algorithm/11053-2.py at main · Junroot/Algorithm 풀이 느린 풀이 처음에는 함수 f(index, current_number)를 만들어 점화식을 만들었다. f(index, current_number): 수열 A의 index부터 n - 1번째 까지 중에서 current_number보다 큰 수들로 이루어진 부분 수열의 최대 길이 a[index] > current_number 인 경우: f(index, current_number) = max( 1 + f(index+1, a[index]), f(index+1, current_number) ) a[index] ≤ current_number 인 경우: f(index, current_number = f(index+1, current_number)...

편집 시간: 2022년 2월 7일 오후 8:48 코드 Algorithm/11050.py at main · Junroot/Algorithm 풀이 팩토리얼을 계산하는 함수를 만들면된다. 중복되는 팩토리얼 계산이 있어서 dp를 사용했다.

오답 여부: o 편집 시간: 2022년 3월 28일 오후 3:55 코드 Algorithm/11049.py at main · Junroot/Algorithm 풀이 잘못된 풀이 i번째에서 j번째 행렬 연산의 최소값은 (i번째에서 j-1번째 행렬 연산의 최소값) + (j번째 행렬 연산) 과 (i+1번째에서 j번째 행렬 연산의 최소값) + (i번째 행렬의 연산) 이라고 착각해서 풀었다. 실제로는 양 끝에 추가하는 경우 뿐만 아니라 i번째에서 j번째 행렬 사이에 끊을 수 있는 모든 경우를 다 비교해봐야된다. 맞는 풀이 위 잘못된 풀이를 수정하여, i번째에서 j번째 행렬 연산의 최소값은...

오답 여부: o 편집 시간: 2022년 3월 15일 오후 2:35 코드 Algorithm/10942.py at main · Junroot/Algorithm 풀이 질문의 개수가 최대 1,000,000개이므로 질문하는 순간 팰린드롬을 계산하면 시간 초과가 발생한다는 것을 알 수 있다. 그러면 미리 팰린드롬을 계산해둬야 되는데 수열의 크기가 최대 2,000이므로 O(N^2)내로 해결해야된다. 어떤 팰린드롬이 있을 때 이 수열의 왼쪽, 오른쪽에 같은 수를 붙이면 계속 팰린드롬이라는 성질을 이용해 문제를 접근했다. 잘못된 풀이 나는 위의 성질을 이용해서 길이가 1, 2인 팰린드롬들을 구하고 이 팰린드롬에서 왼쪽과 오른쪽을 늘리면서 구할 수 있는 모든 팰린드롬을 구했다....

편집 시간: 2022년 2월 7일 오후 8:38 코드 Algorithm/10866.py at main · Junroot/Algorithm 풀이 양방향 링크드 리스트를 이용해서 덱을 만들었다.

편집 시간: 2022년 1월 31일 오후 6:35 코드 Algorithm/10845.py at main · Junroot/Algorithm Algorithm/10845-2.py at main · Junroot/Algorithm 풀이 큐를 사용할 수 있는 라이브러리인 deque를 사용하면 쉽게 해결이 가능하다. 만약 라이브러리를 사용하고 문제플 해결하고 쉽다면 두 번째 코드를 확인하면된다.

편집 시간: 2022년 1월 31일 오후 5:52 코드 Algorithm/10828.py at main · Junroot/Algorithm 풀이 배열을 이용해서 쉽게 스택을 구현할 수 있다. 하지만 입력에 대한 주의점이 있다. input() 함수는 느리기 때문에, 많은 수의 입력이 있을 경우에는 input() 함수보다는 sys.stdin.readline() 을 사용하는 것이 좋다. 각 명령어를 입려할 때마다 출력을 하는 것 보다 출력할 값을 배열 형태로 모아둔 다음 “\n”.join(answers) 형태로 출력하는 것이 더 효율적이다.

편집 시간: 2022년 2월 7일 오후 9:04 코드 Algorithm/10816.py at main · Junroot/Algorithm 풀이 lower bound, upper bound 이진 탐색을 이용해서 각 숫자의 개수를 구했다. 다른 사람 풀이 해쉬맵을 이용한 방법도 있다. from sys import stdin _ = int(input()) n = [int(i) for i in stdin.readline().split()] _ = int(input()) m = [int(i) for i in stdin.readline().split()] hashmap = {} for i in n: if i in hashmap: hashmap[i] += 1 else: hashmap[i] = 1 print(' '....

편집 시간: 2022년 2월 7일 오후 8:36 코드 Algorithm/10814.py at main · Junroot/Algorithm 풀이 입력된 순서를 데이터로 함께 저장하고 있으면 정렬하기 쉽다. 이 때, 입력으로 받은 age 가 문자열인지 숫자인지 확인할 필요가 있다. 다른 사람 풀이 딕셔너리를 이용해서 푸는 방법도 있다. 키를 나이로 하는 딕셔너리에 입력순으로 추가하면 순서를 보장한채로 정렬이 가능하다. import sys input = sys.stdin.readline print = sys.stdout.write N = int(input()) people = {} for n in range(N): age, name = map(str, input()....

편집 시간: 2022년 2월 12일 오후 9:51 코드 Algorithm/1074.py at main · Junroot/Algorithm 풀이 재귀로 분할 정복을 하면 쉽게 해결할 수 있다. 이 때, 굳이 모든 구역을 하나씩 셀필요 없이 찾고자 하는 위치가 포함된 구역만 재귀로 확인하면된다. 현재 정사각형의 1 / 4 크기의 칸의 개수는 구할 수 있기 때문이다.

편집 시간: 2022년 1월 31일 오후 6:05 코드 Algorithm/10250.py at main · Junroot/Algorithm 풀이 X와 Y부분을 분리해서 생각해보자. H = 6, W = 12인 경우 아래를 만족한다. N이 1 ~ 6 → X = 1 7 ~ 12 → X = 2 13 ~ 18 → X = 3 … 따라서 X는 값이 H를 주기로 값이 1씩 증가한다. N이 1부터 시작하고 X도 1부터 시작하므로 다음의 공식이 만들어진다. X = (N - 1) // H + 1...

편집 시간: 2022년 2월 7일 오후 8:30 코드 Algorithm/1018.py at main · Junroot/Algorithm 풀이 모든 경우를 탐색하면거 최소값을 구하면된다. 계산할 때, 제일 왼쪽위가 흰색인 경우와 검은색인 경우 두 가지로 나누어서 계산할 필요가 없다. 체스판의 크기가 64기 때문에 min(result, 64 - result) 로 구할 수 있다.

편집 시간: 2022년 2월 9일 오후 6:44 코드 Algorithm/1012.py at main · Junroot/Algorithm 풀이 bfs또는 dfs로 인접한 배추들의 그룹의 개수를 구하면 된다.

편집 시간: 2022년 3월 4일 오후 2:39 코드 Algorithm/1005.py at main · Junroot/Algorithm 풀이 내 풀이 건물 사이의 건축 선후 관계가 존재하기 때문에 위상 정렬을 사용하면 된다고 생각했다. 기본적으로 위상 정렬로 문제를 푸는데 다음 현재까지의 건축 시간을 자신보다 한 단계 앞의 건물 중에 가장 오래 걸린 건물을 기준으로 ㅅ계산을 해야되므로 이를 저장하는 리스트를 하나 만들었다.(dp) 마지막에 목적지 건물에 도착하면 (목적지 건물에 도착하는데 걸리는 시간) + (목적지 건물을 짓는데 걸리는 시간)을 출력하면 된다....

편집 시간: 2022년 2월 9일 오후 6:13 코드 Algorithm/1003.py at main · Junroot/Algorithm 풀이 (n일 때 0의 개수) = (n-1일 때 0의 개수) + (n -2일 때 0의 개수) (n일 때 1의 개수) = (n-1일 때 1의 개수) + (n -2일 때 1의 개수) 위의 점화식을 찾아내면 풀 수 있다.