안녕

0. 문제 링크 https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 1. 풀이 방법 해당 문제는 단순히 사이클이 존재하는 노드를 집합으로 넣으면 되는 문제이다. 나는 전혀 최적화를 하지 않고, 모든 노드를 살펴보면서 탐색하게 하였다. 물론 이 방법이 좋은 것은 아니지만, 그래도 꽤 시간은 빨랐다. 아무튼 DFS를 하다가 특정 노드가 이미 True로 설정되어 있다면, 이는 사이클이 생긴 것이므로 이를 ans set에 넣고 반환하게 하였다..

0. 문제 링크 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 1. 풀이 방법 음... 해당 문제는 매우 쉬웠다. 그냥 BFS를 하면 풀리는 문제다. 이때 익혀야 하는 토마토의 개수를 미리 세서, 그 개수만큼 되면 끝내게 했다. 만약 해당 갯수만큼 모두 채우지 못했는데, BFS가 끝나버리면 이는 모두 채우지 못하는 것이므로 -1을 반환하였다. 2. 코드 from collections import deque import ..

0. 문제 링크 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 1. 풀이 방법 우선 빙산의 녹음을 구현한 함수인 melt()와 그룹화하는 함수인 group() 함수를 구현했다. 그리고 빙산 근처에 바다의 개수를 세는 adj도 따로 만들어서, 빙산 근처에 몇 개의 바다가 있는지 셌다. melt() 함수를 사용하고, 다시 인접한 바다의 개수를 셌다. 만약 특정 빙산이 모두 녹았다면 해당 빙산은 adj 딕셔너리에서 pop 하였다. group(..

0. 문제 링크 https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 1. 풀이 방법 해당 문제에서 물고기의 값과 이동 방향은 복소수로 하나로 묶었다. 근데 딕셔너리를 쓰면 더 간단하게 풀 수 있을 것 같긴했는데, 이미 복소수로 묶어놔서 그냥 복소수로 풀었다. 우선 물고기의 움직임을 구현함 함수인 fish_move() 함수와 상어가 갈 수 있는 좌표를 반환하는 can_shark_move() 함수를 구현했다. maps는 물고기와 상어..

0. 문제 링크 https://www.acmicpc.net/problem/20061 20061번: 모노미노도미노 2 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 1. 풀이 방법 비트마스킹으로 문제를 풀었음 특별한 점은 없음 주석 처리를 자세히 해놓았으므로, 코드를 보면 이해할 수 있음 2. 코드 import sys def goto_board(*args): # 넣을 수 있는 자리를 찾는 함수 max_cnt = 7 for i in range(6): for val in args: if val & 1 = 1 for color in [g..

0. 문제 링크 https://www.acmicpc.net/problem/16974 16974번: 레벨 햄버거 상근날드에서 오랜만에 새로운 햄버거를 출시했다. 바로 레벨-L 버거이다. 레벨-L 버거는 다음과 같이 만든다. 레벨-0 버거는 패티만으로 이루어져 있다. 레벨-L 버거는 햄버거번, 레벨-(L-1) 버거, www.acmicpc.net 1. 풀이 방법 해당 문제의 알고리즘은 구현이지만, 사실 가만 보면 분할 정복 문제와 다를 것이 없다. 방법은 별거 없다. 맨 왼쪽 빵보다 왼쪽에 있으면 패티가 없다. 중간 패티라면 왼쪽 패티 갯수를 넣는다. 왼쪽 빵과 중간 패티 사이라면 분할 정복으로 왼쪽만 분할 정복으로 넣는다. 오른쪽 빵과 중간 패티 사이라면 왼쪽 패티 갯수를 더하고 오른쪽을 햄버거를 분할 정..

0. 문제 링크 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 풀이 방법 이 문제에서 고통을 받은 것은,,,python3로는 시간초과가 나는 것이다... 물론 스터디원 중에는 python3로도 푼 괴물이 있긴하다. 아무튼 나는 python3로는 안 풀려서 13, 14는 하드코딩을 했는데, 그 외의 방법은 내가 예전에 쓴 글에서 자세히 설명되어 있다. 알고리즘은 백트래킹을 사용했다. 2022.05.26 - [Computer Science/알고리즘] - [..

0. 문제 링크 https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 1. 풀이 방법 첫 번째로 동전의 위치를 찾았다. 만약 동전이 둘 다 범위 안에 있다면, 무난하게 동전을 움직이게 했고, 만약 벽이라면 움직이지 않고 다시 현재 위치에 있게 했다. 그리고 다시 deque에 넣었다. 만약 동전이 둘 다 범위 바깥이라면, 둘 다 떨어졌다는 의미이므로, continue를 했다. 만약 한 개만 떨어졌다면 그대로 반환을 했음 하지만 해당 경우에 동전이 겹..

0. 문제 링크 https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 1. 풀이 방법 우선 배열을 돌린다, 회전한다 뭐 이런거는 너무 오래 걸릴 것 같았다. 그래서 12시 방향을 시작점으로 하고, 그 좌표를 저장하는게 좋아보였다. 그래서 결국엔 다 풀었는데, 뭔가 마지막 예제가 계속 안 됐었다. 알고보니까 인접한 모든 애들을 없애야 하는 것이 있었다. 여기서 다시 BFS로 풀자니 푼 시간이 아깝고, 다시 구현하기도 귀찮았다. 그래서 ..

0. 문제 링크 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 1. 풀이 방법 (참고로 해당 방법은 python3로는 안 풀립니다..ㅠ) 해당 문제를 푸는 로직은 간단합니다. 우선 그룹(인구 이동이 가능한 좌표들)을 찾고, 인구 이동하는 것을 반복합니다. 그렇게 모든 좌표에서 이동이 끝나면, 날짜를 하루 셉니다. 근데.....시간 초과가 나네요ㅠ.. 아마 중복으로 계산하는 부분이 있을 것으로 생각됩니다. 2. 코드 from co..