처음으로 릿코드 문제를 풀어보았다. 어떤 정수 배열이 주어졌을 때, 이 배열을 '합이 동일한 2개의 부분 집합으로 나눌 수 있는지' 를 판단하는 문제였다. dp를 이용해 풀었다. 아래 알고리즘은 직접 손으로 따라가며 풀면 금방 이해할 수 있을만한 코드이다. TIP! 배열의 합이 22일 때, 배열에 속한 몇가지의 수를 선택해 배열의 합의 절반인 11을 만들 수 있으면 자연스레 선택받지 못한 나머지 수들의 합도 11이 된다. (배열의 합이 짝수인 경우만 2개의 부분 집합으로 나눌 수 있기 때문!) 혹시 이런 문제가 백준에도 있다면 댓글 남겨주세요,, class Solution: def canPartition(self, nums: List[int]) -> bool: total = sum(nums) if tot..
https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 진짜 순수 구현문제다.. 방향벡터를 이용해야하는 정도?만 제외하면.. 오랜만에 푸는 문제라 많이 어지러웠지만, 그래도 풀었다..! 문제의 해결방법은 다음과 같다 1. 미세먼지가 확산한다. 2. 공기청정기가 작동한다. 3. 위 과정을 T번 반복한다. 사실 2번은 정말 노가다..라고 할 수 있다. 그냥 값들을 앞으로 옮기기만 하면 되는데, for문이든 while문이든 취향껏 골라서 풀면 된다. 이제..
https://school.programmers.co.kr/learn/courses/30/lessons/150368 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 독해 능력이 중요한 구현 문제이다 ㅋㅋ 읽어보면 알겠지만, 모든 가능한 할인율의 경우의 수를 전부 대입하여 풀어봐야한다. 즉 브루트 포스 + 백트래킹 구현 문제 정도로 생각할 수 있다. 문제 풀이는 다음과 같다. 1. 필요한 변수들을 선언해주고 dfs를 시작한다 2. 할인율의 경우의 수를 기록하는 배열을 sale_board라 할 때, 이 배열이 다 채워지면 cal() 함수를 호출해서 각 경..
https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 기본적인 백트래킹 + 브루트포스 문제이다. 가능한 모든 경우의 수를 해보면서 최댓값을 찾으면 된다. 순열 구하는 문제와 동일하다. 만일 아직 백트래킹이 잘 이해가 되지 않는다면, 아주 작은 테스트 케이스를 하나 만들어서 직접 손으로 코드를 따라가보면 된다. 물론 당연히, 시스템 스택을 알고있어야 한다. import sys #sys.setrecursionlimit(10**6) input = sys.stdin.re..
https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 생각보다 까다로웠던 dp 문제이다. (사실 dp문제는 다 까다롭지만,,) dp[1], dp[2], dp[3]까지는 손쉽게 생각할 수 있다. dp[i]가 의미하는 바는 i번째 와인까지 마셨을 때 최대로 마실 수 있는 와인의 양이다. 1. 전전 와인 먹지 않고 전 와인과, 현재 와인 마시기 + 전전전 와인까지의 최댓값 2. 전 와인 먹지 않고 현재 와인 마시기 + 전전 와인까지의 최댓값 3. 전 와인까..
https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 백트래킹을 이용한 브루트 포싱이다. 단어의 앞뒤가 항상 anti, tica로 이루어져 있으므로 최소 5개의 글자 (a,c,i,n,t) 는 알고 있어야 한다. 그리고 이제 남은 알파벳 21개 중에서 추가로 학습을 진행한다. 이 때 알고 있는 글자의 수가 k개가 될 때 까지만 진행한다. 만약 depth가 k에 도달한다면, 입력으로 주어진 단어를 탐색하면서 모르는 글자가 나올 경우 탐색을 종료하..
