본문 바로가기

구현4

[구현] 백준 17140 : 이차워 배열과 연산 - 파이썬 Python https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net R 연산과 C 연산을 나누어서 생각했다 각 연산에서의 진행 과정은 아래와 같다 모든 row (R연산) 혹은 col (C연산)에 대해 각 수의 개수 카운팅 하면서 dictionary에 추가 dictionary를 tuple로 풀어서 sort (1 idx 우선, 2 idx 다음) sort된 튜플을 풀어서 새로운 A로 생성 col_cnt (C연산) 혹은 row_cnt (R연산)을 갱신 R,C.. 2022. 3. 7.
[구현] 백준 17143 : 낚시왕 - 파이썬 https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 생각하기 상어의 정보 저장? 리스트에 각 상어의 r, c, s, d, z(위치, 크기, 방향, 속도)를 저장 shark[r][c] 는 (r,c)에 있는 상어 -> 상어의 위치가 변하고 위치가 중요하기 때문에 현재 문제에는 이러한 접근이 구현하기 편함 상어의 같은 위치에 여러마리 모든 상어를 이동 시키고 모든 칸을 살펴 보면서 2마리 이상이면 한마리로 -> 배열이 여러차원으로 형.. 2022. 2. 14.
[구현] 백준 16235 : 나무 재테크 - 파이썬 Python https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 생각하기 각 칸에 나무가 있고 봄, 여름, 가을, 겨울에 따라 각 칸에 대한 이벤트를 수행 시간복잡도 최대 1000년이므로 1000년동안 N*N의 칸을 돌아다닐 예정 N의 최대는 10이므로 100개의 칸을 돌아다닌다 각 칸에서는 최대 100개의 나무가 있을수 있다 1000 * 100 * 100 < 10^9이므로 충분히 시간 복잡도 안에 해결 가능 N, M, K = map(int, .. 2022. 2. 8.
[구현] 백준 16234 : 인구이동 - 파이썬 Python https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 생각하기 문제에서 제시된 기준을 기반으로 인구가 각 날에 이동할 수 있는 블락들을 bfs를 이용하여 묶어본다 묶을 수 있다면 계속 이동해도 된다는 얘기 -> 묶지 못할 때까지 계속 day를 증가시켜가면서 이동해보자 시간복잡도 모든 칸에 대해서 조사 : O(N^2) 최대 인구 이동 가능 : 2000 2000 x ( N^2 ) 구현하기 united - bfs를 돌면서 묶을 수 있는 박스.. 2022. 1. 31.

티스토리툴바