본문 바로가기

코딩테스트/백준 알고리즘 풀이30

[백준 알고리즘/Python] 백준 14503번 로봇 청소기, 파이썬 설명 1. 문제 출처 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 2. 생각정리 - 현재방향을 기준으로 다음 방향을 반환해주는 함수 작성하기 - 현재방향 기준으로 뒤쪽 위치를 반환해주는 함수 작성하기 - 나머지는 그냥 하라는대로 하면 될 듯 함 3. 조각코드 현재방향 기준으로 다음 방향 반환해주는 함수 dx = [-1,0,1,0] dy = [0,1,0,-1] def rotate(cd): nd = 0 if cd == 0: # d가 북이면 nd는 .. 2022. 3. 27.
[백준 알고리즘/Python] 백준 15686번 치킨 배달, 파이썬 설명 1. 문제 출처 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 2. 생각정리 - 최대 m개를 어떻게 살릴지 구하는 조합이 필요함 - 거리를 체크하는 함수를 따로 빼놓기 - 나머지는 반복문으로 체크하면 될 듯 3. 조각코드 #거리 체크 def cal_bbq(hx,hy, bx,by): return abs(hx-bx) + abs(hy-by) # m개 구하는 조합 from itertools import combinations g.. 2022. 3. 27.
[백준 알고리즘/Python] 백준 112100번 2048 (Easy), 파이썬 설명 1. 문제 출처 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 2. 생각 정리 - 오른쪽, 왼쪽, 위쪽, 아래쪽 이동을 전부 다 구현하기는 너무 복잡함. - 따라서, 행렬을 회전시켜서 하나의 이동(왼쪽)으로만 구현할 것임. - 최대 5번 이동은 중복 순열을 사용하면 될 듯 함. 3. 조각 코드 - 행렬을 시계, 반시계 방향으로 회전하는 코드. 기억해두면 유용하게 쓰일 때가 많음 # 행렬 시계방향 90도 회전 def.. 2022. 3. 23.
[백준 알고리즘/python] 백준 1931번 회의실배정, 파이썬 설명 백준 알고리즘의 그리디 파트, 1931번 회의실배정 문제를 파이썬코드와 함께 내가 이해한대로 설명해보려 한다. 문제 출처 https://www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 먼저 그리디라는 알고리즘은 그냥 당장 단순하게 좋은것만 생각하는 알고리즘이다. 따라서 이후의 상황은 그냥 고려하지 않는 알고리즘이다. 문제를 잘 읽어 보고, 그리디를 써야겠다는 생각이 들 때 까지 익숙해져야 한다. 문제 해석 #1. N개의 회의에 대해 회의실 사용표를 만들려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고 각회의가 겹치지 않게 회의실 사용 표를 만들어라 #2. 단 .. 2020. 9. 27.
[백준 알고리즘/python] 백준 11047번 동전 0, 파이썬 설명 백준 알고리즘의 그리디 파터 11047번 동전 0 문제를 파이썬으로 풀고, 내가 생각했던 점을 글로 남겨 보려고 한다. 문제 출처 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 먼저 그리디 알고리즘은 단순하게, 뒷 일은 생각하지 않고 지금 당장 좋은 것만 선택하는 알고리즘이다. 이 동전 0 문제의 경우, 특이한 조건이 하나 있어서 그리디 알고리즘을 적용 할 수 있다. 바로, 입력.. 2020. 9. 27.

티스토리툴바