King of the Jungle Lion

문제링크:13172번: Σ (acmicpc.net) 13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net 이 문제는 M개의 N면체 주사위를 굴렸을때, 그리고 그 주사위의 모든 면의 수의 합이 S일때 모든 주사위를 굴렸을 때의 기대값을 구하는 문제이다. 각 주사위의 기대값은 간단하게 S/N으로 구할 수 있지만, 여기서 구한 S/N들을 더하는 과정에서 생길 수 있는 오류와 효율적인 방법에 대해 다루는 문제이다. 문제를 처음 읽었을 때에는 모듈러가 무엇인지 잘 몰라서 잘 이해가 안갔는데, 몇번 읽어보니 이해 할 수 있었다. 백준의 문제를 풀다 보면 가끔 엄청나게 큰 수를 계..

문제링크: 12865번: 평범한 배낭 (acmicpc.net) 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 이 문제는 제한 무게가 있는 배낭에 물품 당 무게, 가치가 각각 주어진 물품을 가장 효율적으로 넣는 문제이다. 이 문제는 DP를 활용하여 풀 수 있었다. 나는 1차원 배열의 DP를 사용해서 풀었지만 인터넷을 보니 2차원 배열의 DP를 사용해 푸는 방법도 있었다. 그런데 1차원 배열을 사용하는것이 더 간단하고 메모리나 시간복잡도 상에서도 ..

문제링크:2638번: 치즈 (acmicpc.net) 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 이 문제는 치즈의 위치가 주어진다. 치즈가 없는 곳은 공기이므로 치즈가 만약 공기와 접촉면이 2개 이상이라면 1시간뒤 치즈는 녹아 없어져 공기가 된다. 특이사항으로는 치즈가 만약 닫힌 도형 모양, 예로 도넛 모양으로 위치되어 있을 시 가운데 구멍은 공기이긴 하나 외부 공기가 아니므로 치즈를 녹게 만들 수 없다. 이 문제는 일단 BFS알고리즘으로 접근해야 한다는 것은 느꼈지만 위의 많은 조건들을 어떻..

문제링크:9465번: 스티커 (acmicpc.net) 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 이 문제는 스티커가 2행 n열로 배치되어 있고, 스티커가 각각 점수를 가진다 했을때, 스티커를 하나 떼기로 정하면 상하좌우 4방면의 스티커는 뗄 수 없어지는 조건에서 뗀 스티커의 총 최대 점수 합을 구하는문제이다. 보통 행렬이 있고 상하좌우 등의 조건이 있으면 bfs를 사용했지만 n이 100000으로 매우 크고 행이 2행밖에 되지 않아 다른 방법을 생각해야 했다. import sys T=int(sy..

문제링크:2448번: 별 찍기 - 11 (acmicpc.net) 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 이 문제는 별다른 설명 없이 예제 케이스를 보고 3*2^k 에 대한 별 찍기를 가능하게 하는 코드를 만드는 문제이다. 여기서 입력값은 3*2^k (0

문제링크: 2206번: 벽 부수고 이동하기 (acmicpc.net) 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 이 문제는 기본적인 미로찾기 문제에서 벽을 처음부터 끝까지 이동하면서 총 한 번 부술 수 있다는 조건을 추가한 문제이다. 처음에는 기본적인 미로찾기 문제를 해결하는 BFS 알고리즘을 사용하면서 벽을 부수는 카운트를 추가하고, 기존의 미로찾기 문제처럼 미로의 행렬만큼의 visited를 만들어서 방문하지 않은(0)인 곳만 찾아다니고 방문한 곳은 (1)로 바꾸어 가며 최단거리..

문제링크: 1967번: 트리의 지름 (acmicpc.net) 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 트리의 지름을 구하는 문제이다. 특징으로는 이 문제에서 주어지는 트리는 항상 간선의 개수가 노드의 개수-1 개 만큼 있다는 것이다. 사실 이미 1167번: 트리의 지름 문제를 이미 풀어 보았기 때문에 이 문제는 쉽게 풀 수 있었다. 1167번 문제는 트리의 노드, 간선의 개수가 자유롭게 주어져 고려해야 할 것이 더 많은 문제이다. 트리의 지름을 구하는 방법은 일단 한 노드에서 가중치..

문제링크: 1918번: 후위 표기식 (acmicpc.net) 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 중위 표기로 주어진 식을 후위 표기하여 반환하는 문제이다. 딱히 방법이 생각도 안나고 후위 표기라는 것도 처음 들어봐서 어려운 문제였다. 특히 괄호가 있는점이 복잡해 보였고 문제에서 설명하는 과정 처럼 a+b*c -> (a+(b*c)) 이렇게 사칙연산의 우선순위에 따라 괄호를 쳐주고, 괄호 순서대로 후위 표기를 하는 알고리즘을 만든다면, 두개의 알고리즘을 만들어야 하고, 사칙연산의 부호에 대해 괄호..

문제링크:1916번: 최소비용 구하기 (acmicpc.net) 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 처음 다익스트라 알고리즘을 모르고 dfs로 시작 노드부터 가능한 노드까지 모두 탐색하여 최소값을 찾는 방식으로 했지만 당연하게 시간 초과가 났다. 다익스트라 알고리즘에 대해 인터넷에 찾아 본 후 다익스트라 알고리즘을 사용하여 문제를 해결하였다. import sys import heapq N=int(sys.stdin.readline().rstrip()) M=int(sy..