본문 바로가기

취준

[프로그래머스 Programmers][Python] 자물쇠와 열쇠 문제 : https://programmers.co.kr/learn/courses/30/lessons/60059 코딩테스트 연습 - 자물쇠와 열쇠 | 프로그래머스 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 깡으로 구현해야한다. 우선 맵을 2*len(key) + len(lock) 으로 확장한 뒤에 arr[M][M] 에서부터 lock을 복사해 놓는다. 이제부터는 순서가 중요하다. 아까의 arr 맵을 복사해 tmparr 에 넣는다. key + lock 사이즈 동안 for문을 돌린다. key를 tmpkey에 복사해놓는다. tmpkey를 90도씩 4번 돌릴 수 있게 for문을 만든다. 각 tmpa.. 더보기
[백준][Python][1931][그리디] 회의실배정 문제 : https://www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 회의실/강의실/화장실 배정같은 이런 문제는 유명하고, 코테에도 나오고 하는 문제다. 이런 문제는 끝나는 시간을 기준으로 정렬하라고만 알고있는데 왜 그런지 알아보자 1. 회의가 짧은 순서대로 배정하면? |--------1------| |--------2-------| |----3----| 이런 순서가 나올 수 있으니까 안된다 2. 회의가 긴 순서대로 배정하면...은 의미없다 3. 회의가 일찍 시작하는 순으로 배정하면? |-1-| |-2-| |----3--| |---------------4-----------.. 더보기
[백준][Python][1780][분할정복] 종이의 개수 문제 : https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으 www.acmicpc.net 분할정복 문제다. 종이를 -1,0,1로 나눴으니 +1 을 하면 리스트의 인덱스로 쓸수 있겠다 싶었다. 이 문제는 두개의 함수.. 더보기
[백준][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를 넣었.. 더보기

티스토리툴바