출처 : 백준, https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net # 주어진 끈 들은 동일한 길이로 잘라 목표 개수만큼 만들어야한다. # 길이와 목표 개수가 주어질 때, 목표 개수로 만들 수 있는 잘린 길이의 최대 길이를 구하시오. # 가진 랜선의 개수 1
출처 : 백준, https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 www.acmicpc.net 수열 시리즈.... 더보기 먼저, 생각해야 할 부분 1. 습관적으로 dp 배열을 0으로 초기화했는데 과연 0으로 초기화하는게 맞는지 생각해보자. 풀이 def solution(n, num_list): dp = num_list[:] for i in range(n): for j in range(i): if num_list[j]..
출처 : 백준, https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 더보기 풀이 def solution(n, num_list): # 이전에 있는 것들 중 나보다 크면서 최대 길이가 가장 큰 것 dp = [1 for _ in range(n)] for i in range(1, n): # 나보다 작은 idx 중에 # 가장 긴 길이를 찾아서 + 1 for j in range(i):..
출처 : 백준, https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 더보기 풀이 def solution(n, num_list): # 이전에 있는 것들 중 나보다 작으면서 최대 길이가 가장 큰 것 dp_inc = [1 for _ in range(n)] for i in range(1, n): # 나보다 작은 idx 중에 # 가장 긴 길이를 찾아서 + 1 for j in range(i): if num_list[j] < num_list[i]: dp_inc[i] = max(d..
출처 : 백준, https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net # 병사의 전투력 리스트가 주어진다 # 가장 긴 감소하는 부분 수열을 만들 수 있는 열외 병사의 수 더보기 먼저, 생각해야 할 부분 1. 가장 긴 감소하는 부분 수열을 만들 수 있는 병사의 수는 전체 병사의 수에서 가장 긴 감소하는 부분수열의 길이를 빼면 된다. 풀이 def solution(n, num_list): # 이전에 있는 것들 중 나보다 크면서 최대 길이가 가장..
출처 : 백준, https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net # 숫자 리스트가 주어진다 # 가장 긴 증가하는 부분 수열의 길이를 출력 더보기 풀이 def solution(n, num_list): # 이전에 있는 것들 중 나보다 작으면서 최대 길이가 가장 큰 것 dp = [1 for _ in range(n)] for i in range(1, n): # 나보다 작은 ..
출처 : 프로그래머스, https://programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr # 오른쪽과 아래로만 움직임 # 물웅덩이의 좌표가 주어짐 # 좌상단 집, 우하단 학교 # 집에서 학교까지 갈 수 있는 최단 거리의 개수 % 1000000007 더보기 먼저, 생각해야 할 부분 1. m x n 좌표가 바뀌어있다. 이건.....알았는데..........문제 내의 모든 좌표가 바뀌어 있다. 그러니까 물웅덩이 좌표도 바뀌어 있다. 하필 예제가 [2, 2]인걸 보면 그냥 당하라고..
출처 : 이것이 취업을 위한 코딩테스트다 with Python 이것이 취업을 위한 코딩 테스트다 with 파이썬 IT 취준생이라면 누구나 가고 싶어 하는 카카오, 라인, 삼성전자의 2016년부터 2020년까지의 코딩 테스트와 알고리즘 대회의 기출문제를 엄선하여 수록하였다. hanbit.co.kr 더보기 먼저, 생각해야 할 부분 1. DP 유형에서 핵심은 현재 -> 다음이 아니라, 이전 -> 현재이다. 다시 말해, 내가 현재 상태에 있을 때 이전에 내가 있을 수 있는 곳들의 후보를 찾는 것이 핵심이다. 문제에서 나는 현재 위치에서 우상, 우, 우하로 이동할 수 있다고 적혀있지만, 점화식을 추론하기 위해서는 현재 위치일 때, 이전에 내가 있을 수 있는 곳을 추론해야한다. 이 경우, 좌상, 좌, 좌하에서 현재..
출처 : 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/42628 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 백준에도 동일한 문제가 있다. # I 숫자 -> 큐에 숫자 삽입 # D 1 -> 최댓값 삭제 # D -1 -> 최솟값 삭제 # 큐가 비어있다면 삭제 명령 무시 # [최댓값, 최솟값] return # 만약 큐가 비어있다면 [0, 0] return 더보기 먼저, 생각해야 할 부분 1. min_heap, max_heap 2개가 필요하다는 것까진 생각했을 것이다. 그렇다면 max_..
출처 : 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/42627 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr # 작업들이 (요청 시간, 작업 소요 시간) 리스트로 들어온다. # 디스크는 1개에 1개의 작업만 가능 # 평균 (요청 시간 ~ 작업 종료) 시간이 가장 짧게 프로세싱할 경우 평균 (요청 시간 ~ 작업 종료) 시간을 return 더보기 먼저, 생각해야 할 부분 1. jobs가 정렬되어 들어온다는 말이 없다. 진짜 치사한데, 맞는 말이다. 정렬되어 들어온다는 말이 없으므로 정..
비트 마스킹 (Bit Masking) 0b10 # 2 0b11 # 3 0b110 # 4 정수의 이진수 표현을 자료구조로 사용하는 방법 컴퓨터는 모든 데이터를 0과 1로 가지고 있기 때문에 정수 역시 0과 1로 표현됩니다. 이러한 비트를 이용해 자료구조로 활용하는 방법을 비트 마스킹이라고 합니다. 파이썬에서 2진수는 앞에 '0b'를 붙여 나타낼 수 있습니다. 비트 연산자 비트 연산은 AND, OR, XOR, NOT, LEFT SHIFT, RIGHT SHIFT 연산이 있습니다. AND & 0b110 & 0b010 # 0b010 0b110 & ) 0b010 ----- 0b010 AND 연산자 &는 두 이진수에서 동일한 위치에 1을 가진 것만 1로 만듭니다. OR | 0b001 | 0b010 # 0b011 0b..
출처 : 백준, https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 더보기 먼저, 생각해야 할 부분 1. 메모리 제한이 4MB로 굉장히 작다 -> 비트마스킹 2. 반복문을 통해 입력 받을 수 있는 명령어의 개수가 최대 3,000,000개이다. -> sys.stdin.readline().rstrip() 풀이 import sys n = int(input()) my_set = 0b0 for _ in range(n): instrction = sys.stdin.readline().rstrip..
