www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 아이디어: 이거를 틀렸었나 보다.. 주어진 입력만 사용하지 말고 새롭게 child배열을 만들어서 풀면 간단히 풀 수 있는 문제였다. 일단 input의 부모배열을 가지고 child배열을 만들어 저장하고, 그 배열을 이용하여 DFS탐색을 한다. 이때 탐색하는 n이 삭제할 노드와 같다면 상황을 나누어야 하는데, n의 부모 노드의 자식이 n 하나 뿐이라면 부모노드도 리프노드가 되므로 cnt+=1을 해주고 그 외의..
복습
www.acmicpc.net/problem/5829 5829번: Luxury River Cruise Farmer John is taking Bessie and the cows on a cruise! They are sailing on a network of rivers with N ports (1
www.acmicpc.net/problem/19538 19538번: 루머 예제 1 0분 : 최초 유포자($1$, $6$번 사람)가 루머를 생성한다. 1분 : $1$번 사람은 $2$, $3$번 사람에게 루머를 퍼뜨린다. $2$번 사람은 주변인 $2$명 중 $1$명이 루머를 믿고 있어 루머를 믿게 된다. $3$ www.acmicpc.net 아이디어: 큐를 두개를 사용하여서 루머를 믿는 사람을 저장하는 큐 A와 A의 인접한 노드들을 저장하는 큐 B로 나눈다. A의 요소들을 pop하면서 시간을 저장하고 해당 요소의 인접리스트를 B에 저장한다. A의 요소가 모두 비게 되면 시간이 +1되는 것이다. 그리고 B의 요소들을 pop하면서 루머에 감염되었는지 여부를 판단하고 감염된 노드만 A에 다시 추가한다. 처음에는 최..
www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 아이디어: 앞선 A->B 문제와 비슷한 방식으로 그래프를 구현하여 풀 수 있을 것 같다. 대신 이번 문제는 무조건 BFS로 풀어야 한다. 생각해야 할 조건이 많아서 예상외로 까다로웠다. 처음에 그냥 제출하니 메모리 초과가 났고.. 그래서 한 번 만든 수를 다시 만들지 않도록 visit 배열을 추가했다. 예를 들면 *2를 하여 이미 한번의 경로만을 사용하여 만든 수를 +1 두번을 사용하..
www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A *2 끝에 1을 추가 -> *10+1 A부터 시작해서 갈 수 있는 경우가 2가지밖에 없으니까 그 방향으로 BFS로 탐색하면서 B가 나오면 도달하기까지 간선의 개수+1를 출력한다. 큐에 [변해가는 A의 값, cnt]를 추가하면서 탐색을 진행하고, n[0]이 B보다 큰 경우에는 연결된..
www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 아주 기본적인 DFS, BFS 구현 문제이다. 백준 기록 보면 인접리스트로 푼 것과 인접배열로 푼 것 두 가지 방식을 확인할 수 있다. dfs를 구현하는 방식에는 재귀함수로 구현하는 방법과 스택을 이용하는 방법 두 가지가 있는데, 이 문제에서는 정점번호가 작은 순서대로 출력해야해서 재귀함수로 구현하는 방법이 더 나을 것 같아 그렇게 풀었지만, 코드는 일단 올려놓는다. (df..
www.acmicpc.net/problem/20002
www.acmicpc.net/problem/10025 10025번: 게으른 백곰 첫 줄에 정수 N과 K가 들어온다. 둘째 줄부터 N째 줄까지, 공백을 사이에 두고 각 양동이의 얼음의 양을 나타내는 gi와 양동이의 좌표를 나타내는 xi가 주어진다. www.acmicpc.net 아이디어: 부분합을 이용하면 되지 않을까. 2k+1만큼의 길이를 더하면서 최댓값을 갱신한다.. 일단 ice배열을 1,000,000개씩 만들고, g와 x를 받으면서 ice[x]=g를 넣는다. 그리고 큐를 하나 만들어서 ice를 하나씩 추가하고 길이가 2k+1이 되면 하나씩 pop하고 다음 걸 더한다. 이때 최댓값을 갱신해준다. 간단한 문제인데.. 이렇게 막막하면 우짤꼬....ㅠㅠ #게으른 백곰 import sys from collect..
www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 아이디어: 주어진 수열을 돌면서 F(Ai) 배열을 채운다. 무식하게 풀어보자면.. 그냥 배열을 돌면서 다 비교할 수 있겠지만 그러면 O(n^2)이므로 시간초과가 날것이다.. 구글링을 해보니, 스택으로 조금만 생각하면 쉽게 풀 수 있었다. 일단 뒤에서부터 배열을 읽어나가는 게 핵심이다! 그리고 F[i]의 값을 스택에 push하되, 만약 현재 읽는 배열의 F[i]값이 스택의 top보다 작다면 NGF(i)는 스택의 top이 된다..
www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 아이디어: #덱 뽑고자 하는 원소가 맨 첫번째 원소가 될때까지 왼쪽이나, 오른쪽으로 이동시키는 최소 횟수를 구하면 된다. 근데 그 최소횟수는 어떻게 구하지? 덱에서의 해당 원소의 위치를 알아야 할 것 같은데.. -> index(x) index(x) popleft() 반대면 pop() 을 한다. 이 값이 뽑고자 하는 원소와 일치하지 않으면 각각 반대편에 다시 추가하고, ans+=1한다. 같은 경우 poplef..
