본문 바로가기

전체 글

[백준][Python][17144][시뮬레이션] 미세먼지 안녕! 문제 : https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 왼쪽 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼 www.acmicpc.net 이 문제는 진짜 하라는 대로 하면된다. 내가 착각해서 고생했던 이유를 적는다. 미세먼지 확산 -> 공기청정기 작동 순.. 더보기
[백준][Python][12865][DP]평범한 배낭 문제 : https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다. www.acmicpc.net 0-1 Knapsack 문제다. 이 문제는 진짜 기본중에 기본이고 다른 DP는 잘만풀면서 맨날 이것만 나오면 틀리길래 각잡고 푼다. 0-1 Knapsack 문제는 가방 무게 K 한도 내에서 최대한 비싼 물건들을 챙겨나오는 문제다. 중요한 점은 다음과 같다. DP [물건 1.. 더보기
[백준][Python][17404][DP] RGB거리 2 문제 : https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집도 이웃이다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오. www.acmicpc.net DP 문제인데 정말 어려웠다. 이 문제는 RGB거리 와 비슷한데, 마지막 집과 첫번째 집이 인접한 원형 형태로 구성되어 있다고 한다. 그래서 마지막 답을 구할때, 첫번째에 어떤 집을 .. 더보기
[백준][11052번, 16194번][Python] 카드 구매하기 1,2 && 블로그 닉값의 위험성 주의! 이 문제는 블로그 닉네임 값을 한 문제이며 닉값하지 말자는 반성문입니다. 두 문제의 차이는 간단하다. 최대를 구하냐, 최소를 구하냐 정도뿐이다. dp문제에서 dp배열을 초기화할때는 (나는) 값을 0으로 한다. 별 의미도 모르는채로 초기화한다. 방법은 다음과 같다. dp[n] = n개의 카드를 샀을때의 최댓값, 최솟값을 구한다. for i in range(1,n+1): for j in range(1,i+1): dp[i] = max(dp[i], dp[i-j]+arr[j]) 이때, 이 문제는 i 개의 카드를 살때 최댓값을 구하는 첫번째 반복문과, 1 16149 은 i번째 까지 샀을때는 == j번째 카드팩을 샀을때 값이 최대/최소가 될까? 를 판별하는 식이다. 이건 간단한데, 여기서 닉값을 했다가 시간을.. 더보기
[프로그래머스 Programmers][Python] 위장 문제 : https://programmers.co.kr/learn/courses/30/lessons/42578 코딩테스트 연습 - 위장 | 프로그래머스 programmers.co.kr 이 문제도 역시 Dictionary, 해쉬맵을 써서 풀면 되는 문제다. 처음에는 ( 의상 종류, 의상 이름) 으로 dictionary에 넣는다. 그 다음이 중요한데, 각 의상중에 하나 이상만 쓰면 되니까, 어떤 의상 종류는 안쓸수 있다. 근데 또, 다 안쓸수는 없다. 따라서, (나같은 경우에는) "" 을 각 의상 종류에다 넣어서 안입는 null value 를 넣었다.(closet[k].append("") ) 이제 각 의상 종류를 모두 곱한 값이 총 방법의 갯수인데, 빼먹은게 하나있다. 1-2 에서 null value를 넣었.. 더보기
[백준][Python][10942][DP] 팰린드롬? 문제 : https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net DP 문제다. 문제의 핵심은 길이가 1,2, 그 이상일때의 경우를 각각 나누는 것이다. (1은 참 0은 거짓이라 하자) dp 배열은 dp[처음][끝] -> 처음 - 끝까지 했을 때 팰린드롬 인가? 이다. 길이가 1 = 무조건 1 길이가 2 = 두 문자가 같으면 1 길이가 3 이상 -> 처음 문자 == 끝 문자 && dp[처음+1][마지막-1] 이 1 import sys n = int(input()) d = [int(i) for.. 더보기
[백준][Python][1890][DP]점프 문제 : https://www.acmicpc.net/problem/1890 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 www.acmicpc.net DP 길 갯수 문제 변형이다. 입력받는 배열의 원소는 그 자리에 갔을 오른쪽이나 아래로 점프를 해야되는 칸 의 갯수이다. 이 문제는 .. 더보기
[백준][Python][3190][브루트포스] 뱀 문제 : https://www.acmicpc.net/problem/3190 3190번: 뱀 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따 www.acmicpc.net 최적화와 기타등등 아무것도 신경안쓴 누더기 코드를 보는 당신! 축하드립니다. 잘난 코드는 다들 비슷하지만 못난 코드는 개성있게 못났다는.. 더보기

티스토리툴바