Algorithm/Baekjoon117 11725. 트리의 부모 찾기 (Python) 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 각 노드에 연결된 노드들을 담아놓는 배열(nodes)을 만들어준다. 입력으로 5 3을 받으면 nodes[5]에 3을 추가해주고 nodes[3]에 5를 추가해주는 방식으로 nodes 배열을 채워준다. 루트 노드가 1이라고 했으므로 1부터 큐에 담아서 각 노드에 연결되어 있는 노드들에 대해서 탐색한다. nodes[1]에 있는 노드들을 차례대로 큐에 담아주는데 이때 nodes[1]에 있는 노드들의 부모는 1번 노드이므로 부모 노드로 1을 담아준다. 이와 같은 방식으로 큐를 돌면서 노드들의 부모 노드를 찾아주고 마지막에 부모 노.. 2022. 2. 10. 1072. 게임 (Swift, Python) 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 풀이 이분탐색을 사용하여 해결하는 문제. 몇 번의 게임을 더 해야 하는지를 기준으로 잡으면 되는 간단한 문제였다. 간단한 문제인데 정답 비율이 낮았던건 Z를 구할 때 실수 연산에서 발생하는 오차때문인 것 같다. 처음 python으로 문제를 풀 때 Z를 구하는 식으로 다음과 같이 사용했다. Z = math.trunc((Y / X) * 100) 위와 같이 Z를 구했을 때 오답이 나왔는데 Y / X 연산에서 실수 관련해서 오차가 발생하기 때문이라는것 같다. 그.. 2021. 12. 16. 3055. 탈출 (Swift, Python) 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 풀이 물이 차있는 지역과 고슴도치의 위치를 담기 위해 큐를 두 개 만들었다. 각각의 큐에는 좌표(x, y)와 시간(time) 정보가 들어간다. 처음에 입력을 받으면서 time이 0인 값으로 큐를 담아준다. 고슴도치의 위치에서 bfs 탐색을 하면서 시간 정보를 비교해준다. prev_time 변수를 하나 만들어서 이전의 시간을 담아두고 큐에서 값을 꺼낼때마다 둘을 비교해준다. 만약 둘의 값이 다르다면 물을 확장시키는 flood 함수를 호출한다. 물이 차 있는 지역을 담기 위한 .. 2021. 12. 4. 1068. 트리 (Swift, Python) 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 2차원 배열을 만들어 각 노드에 자신의 자식 노드 리스트를 담아둔다. 예를 들어 입력이 -1 0 0 1 1 과 같은 형태로 주어지면 0은 root 노드로 설정하고 1과 2는 부모 노드가 0이므로 배열의 [0]에 [1, 2]를 담는다. 3과 4는 부모 노드가 1이므로 배열의 [1]에 [3, 4]를 담는다. 그 후 root 노드부터 dfs 탐색을 시작한다. dfs로 노드를 탐색하면서 현재 노드에 자식 노드가 하나도 없을 경우 카운트를 증가시키고 탐색을 종.. 2021. 12. 2. 1738. 골목길 (Swift, Python) https://www.acmicpc.net/problem/1738 1738번: 골목길 첫째 줄에 골목길들이 교차하는 지점의 개수 n (2 ≤ n ≤ 100)과 골목길의 개수 m (1 ≤ m ≤ 20,000) 이 차례로 주어진다. 이어지는 m개의 행에 각각의 골목길을 나타내는 세 정수 u, v, w가 차례로 www.acmicpc.net 풀이 민승이네 집(1번)에서 코레스코 콘도(n번)까지 가는데 있어서 최적의 경로를 찾는 문제이다. 가는 경로에 음수가 존재하므로 다익스트라 알고리즘으로는 해결할 수 없고 벨만 포드 알고리즘을 이용해서 해결 가능하다. 기존과의 차이점은 보통 목적지까지 최단 거리를 찾는거였다면 이번 문제는 금품의 양이 최대가 되는 경로를 찾는 것이다. 하나 주의할 건 기존의 벨만 포드 알고리즘.. 2021. 11. 18. 15422. Bumped! (Python) https://www.acmicpc.net/problem/15422 15422번: Bumped! The input consists of a single test case. The first line lists five space-separated integers n, m, f, s, and t, denoting the number of cities n (0 < n ≤ 50 000), the number of roads m (0 ≤ m ≤ 150 000), the number of flights f (0 ≤ f ≤ 1 000), th www.acmicpc.net 풀이 어떤 한 지점에서 시작해서 최단 거리를 구하는 문제로 다익스트라를 활용해서 문제를 해결할 수 있다. 이 문제에서 비교해야 할 것은 다음과 같.. 2021. 11. 16. 이전 1 ··· 16 17 18 19 20 다음
