전체 글
![[Python] 백준 17822번: 원판 돌리기](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbgdSgz%2FbtqDF0akIEA%2Fa6mxD90tsm6vhIXJ9YJfbk%2Fimg.png)
[Python] 백준 17822번: 원판 돌리기
출처 : https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다. (i, 1)은 (i, 2), (i, M)과 인접하다. (i, M)은 (i, M-1), (i, 1)과 인접하다. (i, j)는 (i, j-1), (i, j www.acmicpc.net # 정리 인접한 곳에 같은 숫자가 존재하는지, 존재할경우 이를 제거하는 일을 간단한 dfs를 이용해서 풀었는데 문제는, ..
![[Python] 백준 17837번: 새로운 게임 2](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FMzxFj%2FbtqDDYj6gEg%2Fi2N4I7nAniSKBfTz2bkgG1%2Fimg.png)
[Python] 백준 17837번: 새로운 게임 2
출처 : https://www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다. 게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 www.acmicpc.net # 정리 k개의 말을 입력받는다. 각 말들을 1번부터 k번 말까지 순서대로 주어진 규칙에 따라 이동시킨다. 값이 리턴되..
![[Python] 백준 17140번: 이차원 배열과 연산](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2F9eYFk%2FbtqDwDVbxav%2FRxgMf35ZteE1YtO5SgegJ1%2Fimg.png)
[Python] 백준 17140번: 이차원 배열과 연산
출처 : https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net R연산과 C연산을 따로 만들 필요가 없다. C 연산 : 2차원 배열을 Transpose → R 연산 → Transpose r, c, k 를 입력받으면 board[r-1][c-1] = k 인지 확인한다. 혹은 시간이 100을 넘어서는지 확인한다. Python으로 2차원 배열을 Transpose하는 것은 쉽다. list(map(list, zip(*board))) 를 해보자. (b..
![[Python] 백준 1987번: 알파벳](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FSUCe5%2FbtqDxupQx3X%2FRgoahWkUfmaBP5OwfM5W20%2Fimg.png)
[Python] 백준 1987번: 알파벳
출처 : https://www.acmicpc.net/problem/1987 1987번: 알파벳 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 www.acmicpc.net # code ## import sys ## input = sys.stdin.readline def bfs(): mx = 0 queu..
[Python/내장함수] zip함수와 *args, **kwargs 란?
[Python] zip함수와 파라미터 앞에 *, **는 어떤 의미인가?¶ zip함수는 동일한 개수로 이루어진 자료형을 묶어주는 역할을 한다. 동일한 위치에 있는 요소들을 가져와서 함께 묶어주는 것 같다. 나중에, 2차원 배열과 관련해서 열(=col)들을 가져올때 zip을 사용하면 유용할 것 같다. [이유] 2차원 배열에서 각 행(=row)들은 인덱스를 통해서 가져오는 것이 쉽지만, 일반적인 방법으로 열(=col)을 가져오기 위해서는 for문이 필요하다. ex) 서로 다른 2개의 자료형을 묶어보자. In [1]: A = [1,2,3] B = [4,5,6] In [2]: for node in zip(A, B): print(node, type(node)) (1, 4) (2, 5) (3, 6) In [3]: f..
[Python/내장함수] lambda, map, filter, reduce 함수 사용법
[Python] lambda 함수, map 함수, filter 함수, reduce 함수 사용법¶ 1. lambda 함수 사용법¶ lambda 함수 - lambda 매개변수 : 표현식 - 함수명 필요 없음 - 한줄로 표현 가능한 함수 - 일반적인 함수처럼 정의해두고 필요할때마다 가져와서 쓰는것이 아니라, 필요한 곳에서 즉시 사용하고 버리는 일시적인 함수 - filter(), map(), reduce()등과 함께 사용하면 많은 응용이 가능해진다. 일반적인 함수 In [5]: def multiply(a, b): return a*b multiply(2, 3) Out[5]: 6 함수 대신 lambda 사용 In [6]: (lambda a,b : a*b)(2, 3) Out[6]: 6 lambda를 변수에 넣어서 재..
(Python) 백준 17143번: 낚시왕
출처 : https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다. 낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하 www.acmicpc.net # Code from collections import deque def move(): ## 상어의 위치를 파악한다. loca..
(Python) 백준 18809번: Gaaaaaaaaaarden
출처 : https://www.acmicpc.net/problem/18809 18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두고 주어진다. 그 다음 N개의 줄에는 각 줄마다 정원의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0, 1, 2이다. 0은 호수, 1은 배양액을 뿌릴 수 없는 땅, 2는 배양 www.acmicpc.net pypy3로 제출하면 통과된다. 처음엔 pypy3로도 시간을 맞추기가 어려워서, 바킹독님의 코드를 참고했..
(Python) 백준 18808번: 스티커 붙이기
출처 : https://www.acmicpc.net/problem/18808 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연결되어 있다. 또한 모눈종이의 크기는 스티커의 크기에 꼭 맞아서, 상하좌우에 스티커가 포함되지 않는 불필요한 행이나 열이 존재하지 않는다. 아래는 올바른 모눈종이의 예시이다. 주황색 칸은 스티커가 붙은 칸을, 하얀색 칸은 스티커가 붙지 않은 칸을 나타낸다. 반면 아래는 올바 www.acmicpc.net # Code ## import sys ## input = sys.stdin.readline # 시계방향으로 90도 회전..
(Python) 백준 16235번: 나무 재테크
출처 : https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 떨어진 칸의 개수, c는 가장 왼쪽으로부터 떨어진 칸의 개수이다. r과 c는 1부터 시작한다. 상도는 전자통신공학과 출신답게 땅의 양분을 조사하는 로봇 S2D2를 만들었다. S2D2는 1×1 크기의 칸에 들어있는 양분을 조사해 상도에게 전송하고, 모든 www.acmicpc.net 이 문제는 정말 여러번 풀어봤다. 문제 자체는 어렵지 않지만, 시간초과때문에 다소 빡셌다. 결국엔 시간때문에 다른 사람들의..
(Python) 백준 16234: 인구이동
출처 : https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명 www.acmicpc.net pypy3로는 통과했지만, 시간초과 문제로 python은 통과되지 못했다. 아직 시간초과문제에 많이 취약하다는 것이겠지.. ..
[Python/기타] 알고리즘(set을 이용한) 시간초과에 도움이 되는 팁
[Python] 알고리즘 문제 시간초과 발생했을때 팁 (bfs관련)¶ 백준의 인구이동 문제를 풀다가 시간초과 문제를 해결하기 위해 많은 방법을 써봤지만 늘 쓰던 방법들로는 시간초과문제를 해결할 수 없었다. 그와 관련해서 어떤 방식이 시간에 영향을 주는지 알아보기위해 간단한 테스트를 해봤다. bfs같은 문제를 풀때 if node not in visited:처럼 해당 원소가 어떤 저장공간(ex. 리스트, 집합 등등)에 존재하는가? 이런 문제를 다뤄야 할때, 어떻게 해야 시간초과를 해결할 수 있을까? In [11]: ## 1번 set ## a의 요소들을 (x, y)와 같이 저장하자. a = set() for i in range(500): for j in range(500): a.add((i, j)) In [1..
(Python) 백준 5373번: 큐빙
출처 : https://www.acmicpc.net/problem/5373 5373번: 큐빙 문제 루빅스 큐브는 삼차원 퍼즐이다. 보통 루빅스 큐브는 3×3×3개의 작은 정육면체로 이루어져 있다. 퍼즐을 풀려면 각 면에 있는 아홉 개의 작은 정육면체의 색이 동일해야 한다. 큐브는 각 면을 양방향으로 90도 만큼 돌릴 수 있도록 만들어져 있다. 회전이 마친 이후에는, 다른 면을 돌릴 수 있다. 이렇게 큐브의 서로 다른 면을 돌리다 보면, 색을 섞을 수 있다. 이 문제에서는 루빅스 큐브가 모두 풀린 상태에서 시작한다. 윗 면은 흰색, 아랫 면은 노란 www.acmicpc.net # Code ## rotate2 : 해당 면을 돌릴 때 일어나는 면의 변화 def rotate2(array, direction): ..
(Python) 백준 17144번: 미세먼지 안녕!
출처 : https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼 www.acmicpc.net python으로 제출했을때 시간초과 pypy3로 제출했을 때 통과 # Code ## 먼지 퍼뜨리기 def spread..
(Python) 백준 15686번: 치킨 배달
출처 : https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 www.acmicpc.net # Code from itertools import combinations ## 맵크기(N), 치킨집 최대 선택가능개수(M)..