11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 문제 요약 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 2. 파이썬 2 - 1. BFS 백준 - 2606 바이러스 [BFS] 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 e-room.tistory.com 2 - 2. 코드 N = int(input()) tree = [[] for _ in range(..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 문제 요약 문자열 s가 주어집니다. 문자열 s안에 연속으로 같은 알파벳 2개가 있으면 제거하고 앞뒤로 이어 붙입니다. 해당 과정을 계속 반복하여 모든 알파벳을 제거할 수 있으면 1을 리턴하고, 없으면 0을 리턴합니다. 2. 접근 방법 제거할 수 없는 알파벳을 담을 Stack을 초기화합니다. 문자열을 순차적으로 방문합니다. Stack이 비어있으면 현재 알파벳을 넣습니다. Stack에 최근에 넣은 알파벳과 현재 알파벳이 다를 경우 제거할 수 없으므로 현재 알파벳을 넣습니다. Stack에 최근에 넣은 알파벳과..
2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 1. 문제 요약 컴퓨터의 수 n, 직접 연결된 컴퓨터의 수 m, 연결된 컴퓨터 쌍의 번호가 주어진다. 1번 컴퓨터와 직간접적으로 연결되어 있는 컴퓨터의 수를 구하시오. 2. 접근 방법 BFS(너비 우선 탐색) 알고리즘을 활용합니다. 1번을 기준으로 찾으면 되기 때문에, 4번과 7번은 무시합니다. 방문할 리스트를 생성하고 해당 리스트의 맨 앞부분에 1번을 추가합니다. (Deque 추천) 방문 리스트의 맨 앞 인덱스부터 순차적으로 방문합니다. 1번을 방문합니다. 1번을 ..
2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 1. 문제 요약 컴퓨터의 수 n, 직접 연결된 컴퓨터의 수 m, 연결된 컴퓨터 쌍의 번호가 주어진다. 1번 컴퓨터와 직간접적으로 연결되어 있는 컴퓨터의 수를 구하시오. 2. 접근 방법 DFS(깊이 우선 탐색) 알고리즘을 사용합니다. 1번을 기준으로 찾으면 되기 때문에, 4번과 7번은 무시합니다. 1번에서 2번을 방문하고, 2번은 방문했다고 표시를 합니다. 2번에서 방문할 수 있는 곳들 중 방문하지 않은 곳을 방문합니다. 3번으로 방문 후, 더 이상 방문할 곳이 없으므..
2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 1. 문제 요약 나무의 수 n, 가져가려고 하는 나무의 길이 m이 주어지고, 나무의 높이 수열이 주어진다. 자를 높이를 지정하면 해당 높이에 맞게 모든 나무가 잘리며, 지정한 높이 이하의 나무들은 잘리지 않는다. m을 만족하면서 자를 수 있는 나무의 높이의 최솟값을 구하시오. 2. 접근 방법 자르는 높이 별로 얻을 수 있는 나무의 길이를 수열이라 생각하고 이분 탐색을 활용하여 풀면 쉽게 풀 수 있습니다. 빨간색이 배열의 인..
10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 1. 문제 요약 숫자 배열이 주어지고, 찾고자 하는 숫자가 주어졌을 때, 찾고자 하는 숫자가 배열에 존재하는지 판단하시오. 2. 접근 방법 이분 탐색 알고리즘을 사용합니다. 해당 알고리즘은 일반적으로 하는 up down 게임과 같은 원리입니다. 정렬된 상태에서 절반씩 소거하며 찾아내는 방법입니다. 오름차순으로 정렬된 배열에서 중간 부분을 탐색하고, 찾고자 하는 숫자보다 크면 해당 지점부터 끝부분까지의 중간 부분을 탐색합니다. 찾고자 ..
16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 1. 문제 요약 n과 문자열이 주어지고, 문자열에서 최대 n개의 종류의 알파벳을 포함한 문자열의 길이를 구하라. 2. 접근 방법 투포인터 알고리즘을 사용하여 문자열을 순차적으로 검사합니다. j(끝) 위치의 알파벳이 새로운 알파벳일 경우 count += 1을 하고 사용 중인 알파벳으로 표시합니다. 사용 중인 알파벳의 종류가 n보다 클 경우 줄어들 때까지 i(시작) 위치의 알파벳을 이동합니다. 사용 중인 알파벳 종류가 하나 줄어들 경우 count -= 1 표시를 해줍니다. 현..
22988번: 재활용 캠페인 첫 번째 용기와 두 번째 용기를 가져가서 용량이 $\left(0+1+\frac{13}{2}\right)$㎖ $=$ $7.5$㎖ 남은 용기를, 세 번째 용기와 네 번째 용기를 가져가서 용량이 $\left(2+3+\frac{13}{2}\right)$㎖ $=$ $11.5$㎖ 남은 용 www.acmicpc.net 1. 문제 요약 헤어에센스 용기의 수 n, 용기의 용량 x, 각 용기에 현재 들어있는 양의 수열 arr이 주어진다. 용기 2개를 갖다 주면, 두 용기에 남아있는 잔량 + x/2 만큼 채워진 헤어에센스를 준다. 단, 용기의 용량보다 넘치게 주지는 않는다. 현재 가지고 있는 용기를 이용하여 가득 찬 헤어에센스를 최대 몇 병 만들 수 있는지 구하시오. 2. 접근 방법 이미 가득 ..
3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 1. 문제 요약 자연수 수열이 주어지고 해당 수열의 수들 중, 두 수를 합하여 x와 같은 경우의 수를 구하라. 2. 접근 방법 - 투 포인터 배열을 오름차순으로 정렬합니다. 성능 향상 : x보다 작은 수들만 사용하도록 필터링 i = 0, j = 수열의 크기 - 1 arr[i] + arr[j] == x 일 경우 answer += 1 i += 1, j -= 1 (정렬을 했기 때문에, 해당 수들을 더했을 때, x..
