안녕

0. 문제 링크 https://www.acmicpc.net/problem/2374 2374번: 같은 수로 만들기 n(1 ≤ n ≤ 1,000)개의 자연수 A[1], A[2], A[3], …, A[n]이 있다. 이 자연수에 Add(i)라는 연산을 하면, A[i]가 1만큼 증가한다. 이때, A[i]만 증가하는 것이 아니고, A[i]의 좌우로 인접한 같은 수의 그룹이 한 www.acmicpc.net 1. 풀이 방법 일단 같은 숫자면 같은 그룹이므로, 중복으로 넣어야 되나 싶었다. 그래서 일단 넣을때부터 같은 그룹이면 하나의 숫자만 넣었다. 예를 들어서, 1 1 1 3 1이 입력되면, 1 3 1만 stack에 들어갔다. 그 이후에는 어떻게 숫자를 더할 것인가가 문제인데, 나는 다른 방법을 썼다. 인덱스를 기준으..

0. 문제 링크 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 1. 풀이 방법 문제를 보고 이건 탐색 기법을 써야겠다고 생각을 했다. 문제 무작정 DFS, BFS를 쓰는 건 좀 아닌 것 같았다. 왜냐면 모든 노드에서 다른 노드를 탐색하는 방법을 사용하면 n^2이 될 것 같았기 때문이다. 어떻게 최장거리를 탐색할 것인가에 대해 고민을 했다. 방금 글 쓰면서 떠오른건데 TSP를 조금 손 봐서 최장거리를 찾아낼 수 있을 것 같다..

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/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 1. 풀이 방법 의외로 방법은 심플하다. 그냥 row, col, 3 * 3 구역 내에서 넣을 수 있는 숫자를 찾으면 된다. 그리고 그 방식으로 DFS를 했다. 근데 문제는 이런 방식으로 했을 때, 스도쿠가 전부 채워지지 않으면 다시 넣을 수 있는 숫자를 찾아야 하는 것... 분명 다른 방법이 있을텐데, 나는 해당 방법 말고는 딱히 떠오르지 않았다. 아무튼 이렇게 하니까 시간 초과가..

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/알고리즘] - [..