728x90 분류 전체보기 썸네일형 리스트형 [백준알고리즘] 11729번: 하노이 탑 이동 순서 -Python [백준알고리즘] 11729번: 하노이 탑 이동 순서 -Python https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5 www.acmicpc.net 오랜만에 하노이탑 문제를 푼 것 같다. 분할 정복 문제.. 더보기 [백준알고리즘] 11728번: 배열 합치기 -Python [백준알고리즘] 11728번: 배열 합치기 -Python https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거나 같은 정수이다. www.acmicpc.net 그냥 서로 다른 두 배열을 정렬된 상태로 출력하는 문제이다. 아래처럼도 풀어봤고, 각각 정렬된 두 배열에서 작은 값부터 하나씩 비교해서 결과를 출력하는 코드도 작성했으나 아래의 코드가 조금 더 빨랐고 간단해 보여서 그냥 잔뜩 파이썬스러운 코드만 올렸다. 1 2 3 4 5 6 import .. 더보기 [백준알고리즘] 10815번: 숫자 카드 -Python [백준알고리즘] 10815번: 숫자 카드 -Python https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이가 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 www.acmicpc.net 처음에 주어진 수들이 존재하고, 다음에 주어지는 값들이 여기에 존재하는지 판.. 더보기 [백준알고리즘] 1967번: 트리의 지름 -Python [백준알고리즘] 1967번: 트리의 지름 -Python https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n번째 줄까지 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연결하는 두 노드 중 부모 노드의 번호를 나타내고, 두 번째 정수는 자식 노드를, 세 번째 정수는 간선의 가중치를 나타낸다. 간선에 대한 정보는 부모 노드의 번호가 작은 것이 먼저 입력되고, 부모 노드의 번호가 같으면 자식 노드의 번호가 작은 것이 먼 www.acmicpc.net 이전에 풀었던 "1167번 트리의 지름" 문제와 거의 유사하다. 오히려 이 문.. 더보기 [백준알고리즘] 11725번: 트리의 부모 찾기 -Python [백준알고리즘] 11725번: 트리의 부모 찾기 -Python https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 트리의 연결 정보가 주어졌을 때 각 노드의 부모를 모두 출력하는 문제이다. 처음 주어진 입력 정보를 각 노드의 번호별로 리스트를 통해서 유지했다. 그 후 head[]라는 부모 노드의 번호를 가리키는 리스트를 생성해주었고, 1번 노드부터 BFS 방식으로 문제를 풀었다. 각 노드와 연결된 노드 중에서 아직 head[]에 부모 노드가 결정되지 않은 노드는 현재 노드를 부모로 하도록 해주었다. 사이클이 없.. 더보기 [백준알고리즘] 1167번: 트리의 지름 -Python [백준알고리즘] 1167번: 트리의 지름 -Python https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 매겨져 있다고 생각한다) 먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되 www.acmicpc.net 와 이 문제도 되게 오래 걸려서 풀었다... 오래 걸린 이유는 두 가지로 뽑을.. 더보기 [백준알고리즘] 1991번: 트리 순회 -Python [백준알고리즘] 1991번: 트리 순회 -Python https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현된다. www.acmicpc.net 이번 문제는 tree traversal (트리 순회) 문제이다. 트리 순회에는 문제에서 요구하는 데로 3가지 방법이 있다. 1. preorder traversal (전위 순회) 2. inorder traversal (중위 순회) 3. postor.. 더보기 [백준알고리즘] 2146번: 다리 만들기 -Python [백준알고리즘] 2146번: 다리 만들기 -Python https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다. 이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북 www.acmicpc.net 와;;; 너무 어려웠다 ㅠㅠㅠ 문제를 푸는 방법은 그래도 찾았는데.. 계속 메.. 더보기 이전 1 ··· 31 32 33 34 35 36 37 ··· 50 다음