일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 |
Tags
- 백엔드
- 4기
- P Stage
- 대회
- cs50
- 백준
- Naver boostcamp
- QNA 봇
- BOJ
- AI Tech
- 장고
- Customer service 구현
- 웹 프로그래밍
- sts
- Naver boostcourse
- 풀스택
- 프로그래밍
- 서블릿
- Django
- 웹
- 2021 Dev-matching 웹 백엔드 개발자
- 레벨2
- 구현
- boostcourse
- 서버
- AI Tech 4기
- 부스트캠프
- 프로그래머스
- 네이버
- 파이썬
Archives
- Today
- Total
daniel7481의 개발일지
[프로그래머스]쿼드 압축 후 개수 세기 본문
반응형
https://school.programmers.co.kr/learn/courses/30/lessons/68936
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
풀이
쿼드 압축 문제는 전형적인 분할 정복 문제인 것 같다. 비슷한 유형의 문제를 풀어본 적이 있어 분할정복을 바로 떠올렸다. 쿼드 압축에서 n의 값은 2의 배수이기 때문에 2의 단위로 끊어가며 정복해가면 되겠다. 일단 quadzip이라는 함수를 만들고, 이중 for문으로 처음에 시작한 이진수(1, 0)이랑 다른 값이 나오면 입력으로 받은 시작 행, 끝나는 행, 시작 열, 끝나는 열 값을 4개로 나눈다음 각각 재귀로 다시 한번 quadzip함수를 호출하면 된다. 만약 모든 요소가 다 같은 값일 경우 압축이 된 것이므로 맨 처음에 이진수에 따라 answer의 인덱스에 더해주면 되겠다.
def quadzip(r1, r2, c1, c2):
global image
global answer
binary = image[r1][c1]
flag = False
for i in range(r1, r2):
for j in range(c1, c2):
if image[i][j] != binary:
flag = True
quadzip(r1, (r1+r2)//2, c1, (c1+c2)//2)
quadzip(r1, (r1+r2)//2, (c1+c2)//2, c2)
quadzip((r1+r2)//2, r2, c1, (c1+c2)//2)
quadzip((r1+r2)//2, r2, (c1+c2)//2, c2)
break
if flag:
break
if not flag:
answer[binary] += 1
def solution(arr):
global answer
answer = [0, 0]
global image
image = arr
quadzip(0, len(arr), 0, len(arr[0]))
return answer
반응형
'프로그래머스' 카테고리의 다른 글
[프로그래머스]n^2 배열 자르기 (0) | 2022.08.16 |
---|---|
[프로그래머스]키패드 누르기(2020 카카오 인턴쉽) (0) | 2022.08.12 |
[프로그래머스]후보키 (0) | 2022.08.02 |
[프로그래머스]섬 연결하기 (0) | 2022.07.31 |
[프로그래머스]소수 찾기 (0) | 2022.07.31 |