728x90 반응형 코딩/백준 리스트형 알고리즘 - Python / 백준 - 1240번 : 노드사이의 거리 1240번: 노드사이의 거리 (acmicpc.net) 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 풀이 트리에서 노드 사이의 거리를 입력받고 입력된 두개의 노드 사이의 거리를 출력하는 문제이다. bfs를 통해 트리를 탐색하고 way 배열에 start 노드 부터 해당 노드까지의 거리를 저장하였다. bfs의 큐에서 end 노드가 pop 되는 시점이 목표 노드까지 도달하였다는 뜻이므로 , way 배열에 저장된 해당 노드까지의 거리를 출력하면 된다. import sys n,m = map(int, sys.stdin.readline().split(" ")) gr.. 더보기 알고리즘/숏코딩 - Python / 백준 - 22396번 : カレー作り 22396번: カレー作り (acmicpc.net) 22396번: カレー作り 各データセットについて，W0 [L] の水に R0 [g] のルウを混ぜた作りかけのカレーから，濃度 C のカレーを作るために追加する必要のあるルウの個数の最小値を 1 行で出力すること．追加す www.acmicpc.net 풀이 요즘 숏코딩에 재미를 붙여서 숏코딩과 관련된 내용도 정리하면 나중에 찾아보기 좋을 듯하여 글을 작성하였다. 파격적으로 짧은 코드가 나오지 않은 쉬운 문제들을 찾아보며 숏코딩 등수에 도전해보았다. 브론즈3 난이도의 문제에서 아직 17명밖에 해결하지 않은 숏코딩 경쟁자가 적어 보이는 문제를 하나 택하고 숏코딩을 진행 경쟁자가 없어 날로 먹긴 했지만 , 코드 길이 138 B , 언어 파이썬으로 해당 문제에서 숏코딩 1등을 달성하였.. 더보기 알고리즘 - Python / 백준 - 1068번 : 트리 1068번: 트리 (acmicpc.net) 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 트리를 입력받고 하나의 노드를 지웠을 때 , 트리의 리프노드의 개수를 구하는 문제이다. 문제에서 부모 노드가 없는 경우를 -1 로 두고 있으므로 , -1 인 경우를 모두 루트 노드로 둔다. 이후 해당 트리를 탐색하며 자식 노드가 없을 경우 정답에 1씩 더해 최종 리프노드 숫자를 출력하면 된다. import sys n = int(sys.stdin.readline()) stack = list(map(int, sy.. 더보기 알고리즘 - Python / 백준 - 1991번 : 트리 순회 1991번: 트리 순회 (acmicpc.net) 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 풀이 이진트리를 입력받고 각각 전위 순회, 중위 순회, 후위 순회의 결과를 출력하면 된다. 이진트리를 배열에 입력받고 그에 따라 전위 순회 , 중위 순회, 후위 순회를 구현하여 정답을 출력하였다. 전위 순회, 중위 순회, 후위 순회의 경우 재귀 함수를 이용해 쉽게 구현할 수 있다. import sys n = int(sys.stdin.readline()) stack = [[] for i in range(n.. 더보기 알고리즘 - Python / 백준 - 17070번 : 파이프 옮기기 1 17070번: 파이프 옮기기 1 (acmicpc.net) 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 파이프를 움직여 해당 구간까지 옮길 수 있는 방법의 개수를 구하는 문제이다. 현재 파이프의 상태가 가로인지 , 세로인지 , 대각선인지에 따라서 움직일 수 있는 경우가 다르므로 3차원 dp 배열을 통해 각 경우를 구분하고 구분된 경우에 따라서 다음 움직임을 구하도록 하였다. dp[k][i][t] 에서 i와 t는 본래 2차원 dp 배열의 인덱스 , k는 0 일 때 가로 , 1 일 .. 더보기 알고리즘 - Python / 백준 - 1789번 : 수들의 합 1789번: 수들의 합 (acmicpc.net) 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 풀이 서로 다른 N개의 자연수의 합이 S라 하고 S를 알 때 N의 최댓값을 구하는 문제이다. N을 가장 크게 만들기 위해서는 1부터 계속 더해가면서 그 값을 만들면 된다. 1,2,3... 을 S에서 뺴주면서 S 1 ( S=4 ) , 2 ( S=2) , 3 ( S=2 < 3 이므로 남은 S값인 2를 모두 전 값에 더해버림) 결과적으로 S = 5 인 경우는 1 , 4 로 이루어질 수 있다. import sys a = int(sys.stdin.readlin.. 더보기 알고리즘 - Python / 백준 - 11725번 : 트리의 부모 찾기 11725번: 트리의 부모 찾기 (acmicpc.net) 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 트리의 간선을 입력받고 해당 노드에 대해서 부모를 찾는 문제이다. 간단한 트리 탐색 문제 이므로 , bfs를 통해서 해결 하였다. bfs를 구현시 , 큐에 자식노드를 넣는 과정에서 해당 부모 노드의 번호를 함께 넣어 쌍으로 입력하였고 , 나중에 pop 할때 정답 배열에 해당 부모 노드를 입력 하였다. import sys e = int(sys.stdin.readline()) s = [[] for _ in range(e + 1)] for i in range(e-1): .. 더보기 알고리즘 - Python / 백준 - 1932번 : 정수 삼각형 1932번: 정수 삼각형 (acmicpc.net) 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이 삼각형 모양으로 이루어진 수열을 위에서 부터 더했을 때 , 가장 큰 값을 찾는 문제이다. 모든 경우를 다 해보아야 하고 위쪽의 삼각형을 더한 결과를 아래쪽에도 사용하므로 dp로 접근해 해결하였다. 삼각형은 모서리 쪽이 아닌 이상 위의 2개의 수중에서 선택을 해야하고 그떄 max값을 가지는 수를 선택해 dp 배열안에 가장 큰 수의 경우만 저장될 수 있도록 한다. 이후 마지막 dp배열에서 max 값을 찾고 출력하면 된다. import sys n = int(sys.stdin.readl.. 더보기 이전 1 ··· 5 6 7 8 9 10 11 ··· 13 다음 반응형
