본문 바로가기
728x90

분류 전체보기

[백준알고리즘] 3085번: 사탕 게임 -Python [백준알고리즘] 3085번: 사탕 게임 -Python https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 문제 상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다. 가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다. 사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하 www.acmicpc.net 브루트 포스문제이다. 문제가 약간 헷갈리는데, 반드시 색이 다른 두 사탕이 인접한.. 더보기
[백준알고리즘] 15684번: 사다리 조작 -Python [백준알고리즘] 15684번: 사다리 조작 -Python https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다. 초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 www.acmicpc.net Python3로는 시간 초과가 난다. 브루트 포스문제인데 최근에 또다시 브.. 더보기
[백준알고리즘] 10448번: 유레카 이론 -Python [백준알고리즘] 10448번: 유레카 이론 -Python https://www.acmicpc.net/problem/10448 10448번: 유레카 이론 문제 삼각수 Tn(n ≥ 1)는 [그림]에서와 같이 기하학적으로 일정한 모양의 규칙을 갖는 점들의 모음으로 표현될 수 있다. [그림] 자연수 n에 대해 n ≥ 1의 삼각수Tn는 명백한 공식이 있다. Tn = 1 + 2 + 3 + ... + n = n(n+1)/2 1796년, 가우스는 모든 자연수가 최대 3개의 삼각수의 합으로 표현될 수 있다고 증명하였다. 예를 들어, 4 = T1 + T2 5 = T1 + T1 + T2 6 = T2 + T2 or 6 = T www.acmicpc.net 문제 분류는 브루트포스로 되어있다. 문제를 푼 방식은 간단하다. 1번 만.. 더보기
[백준알고리즘] 2573번: 빙산 -Python [백준알고리즘] 2573번: 빙산 -Python https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지 www.acmicpc.net 이 코드는 PyPy3로만 통과한 코드다. Python3로는 시간 초과가 발생한다. 사실 처음.. 더보기
[백준알고리즘] 1300번: K번째 수 -Python [백준알고리즘] 1300번: K번째 수 -Python https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B의 인덱스는 1부터 시작한다. www.acmicpc.net 너무 어려웠다.... 아이디어가 도무지 기억이 안 나서 알고리즘 분류를 봤는데도 도저히 이분 탐색으로 할 수 있는 방법이 생각나지 않았다. 생각한 방법은 너무 시간이 오래 걸리는 것뿐이었다. 그래서 결국 여러 블로그들을 찾아봤다. 다 같은 내용인데 다 이해가 안돼서 아래의 블로그를 집중.. 더보기
[백준알고리즘] 2098번: 외판원 순회 -Python [백준알고리즘] 2098번: 외판원 순회 -Python https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 전에 외판원 순회 2를 푼 적이 있었는데, 그 이전 문제인 것 같다. 풀이는 여기에 썼었다. 외판원 순회 2와 같은 방법으로 문제를 풀면 된다. 전에 비트 마스크로 풀었던 기억이 인상 깊게 남아있었어서, 그렇게 풀까 하다가 브루.. 더보기
[백준알고리즘] 10164번: 격자상의 경로 -Python [백준알고리즘] 10164번: 격자상의 경로 -Python https://www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으로 구분된다. K의 값이 0인 경우도 있는데, 이는 ○로 표시된 칸이 없음을 의미한다. N과 M이 동시에 1인 경우는 없다. www.acmicpc.net 경우의 수를 구해주는 문제이다. DP를 사용해 모든 경우의 수를 구해주면 된다. O표시가 없는 경우(k=0인 경우)에는 시작점에서 끝점까지 이동할 수 있는 모든 경우의 수를 구해주.. 더보기
[백준알고리즘] 5557번: 1학년 -Python [백준알고리즘] 5557번: 1학년 -Python https://www.acmicpc.net/problem/5557 5557번: 1학년 문제 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다. 상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. www.acmicpc.net 별생각 없이 딕셔너리를 이용해서 풀었다. 현재까지의 누적 계산량과 인덱스를 쌍으로 하는 튜.. 더보기
728x90

티스토리툴바