[백준 11725] 트리의 부모 찾기 (Python)
문제 링크 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 해설 Idea BFS 1번 노드부터 BFS를 수행하면서 다음 노드에 순차적으로 접근 다음 노드가 이미 방문한 노드의 경우 부모 노드라 판단하여 배열에 저장 부모 노드가 저장된 배열에 대해 2번 노드부터 순차적으로 부모 노드를 출력 Time Complexity O(N+E) = 200,000 Data Size N: 2
[프로그래머스] 쿼드압축 후 개수 세기 (Python)
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/68936 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해설 Idea Divide and Conquer 2차원 배열을 4등분씩 나눠 재귀함수를 호출하고 동일한 값으로 채워져 있는지 판단하여 값의 개수 증가 2^n 형태의 정수에 대해 NumPy를 활용해 행렬 인덱싱을 간단히 구현 Time Complexity O(N^2 Log N^2) = 20,000,000 Data Size arr: [[int(1)]], shape(2^n, 2^n) 1
[프로그래머스]n^2 배열 자르기 (Python)
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/87390 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해설 Idea Greedy n의 크기가 굉장히 크기 때문에 2차원 배열을 만드는 것만으로 시간 초과가 발생할 것을 예상 r행 c열의 값은 max(r,c)+1과 같고 1차원 배열의 인덱스 i에 대해 r은 i//n, c는 i%n와 동일 left부터 right까지의 인덱스를 규칙에 맞는 값으로 변환하여 반환 Time Complexity O(N) = 10^5 Data Size n: 1
[프로그래머스]n진수 게임 (Python)
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/17687 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해설 Idea Math 0부터 시작해 t*m의 길이를 만족하는 N진법 배열을 생성 매 순서마다 p 위치에 해당하는 값을 추출해 문자열로 반환 Data Size n: 2
[백준 1697] 숨바꼭질 (Python)
문제 링크 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 해설 Idea BFS N에서 시작해 K에 도달할 때까지 x-1, x+1, x*2에 대한 최단거리를 탐색 두 점이 위치할 수 있는 범위 내에서 가까운 거리의 점부터 탐색을 수행하고 K에 대한 거리를 출력 N이 K보다 클 경우 x-1 외에는 이동수단이 없기 때문에 시간 단축을 위해 예외로 처리 Time Complexity O(N) = 100,000 Data ..
[백준 1676] 팩토리얼 0의 개수 (Python)
문제 링크 https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 해설 Idea Math 팩토리얼 수를 구하고 문자열로 변환해 연속되는 0의 개수를 출력 Data Size N: 0
[백준 1541] 잃어버린 괄호 (Python)
문제 링크 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제 해설 Idea Greedy 최솟값을 만들기 위해서는 '-'를 기준으로 괄호를 치는 것이 최선 '-'를 기준으로 식을 나누고 구분된 식을 계산하여 결과를 출력 Data Size arr: str(50) 해설 코드 arr = input().split('-') answer = sum(map(int,arr[0].split('+'))) for i in arr[1:]: answer -= ..
[백준 1389] 케빈 베이컨의 6단계 법칙 (Python)
문제 링크 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 문제 해설 Idea BFS 1부터 N까지의 번호에 대해 매번 BFS를 수행하면서 다른 모든 노드와의 거리를 파악 가장 작은 거리의 합을 가진 노드의 인덱스 번호를 출력 Time Complexity O(N^2+NM) = 510,000 Data Size N: 2
[백준 5430] AC (Python)
문제 링크 https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문제 해설 Idea Implementation, Deque 문제에서 주어진대로 매번 배열을 뒤집으면 O(N^2)의 시간 복잡도로 시간 초과가 발생 배열에 영향을 주지 않으면서 R 함수를 처리하기 위해 상태 변수를 정의하고, D 함수가 호출될 경우 배열의 상태에 따라 첫 번째 수를 버릴지 마지막 수를 버릴지 결정 마지막에 배열의 상태를 업데이트하고 정해진 형태로 결과를 출력 Time Complexity O(N) = 100,000 Data Siz..
[백준 1463] 1로 만들기 (Python)
문제 링크 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 해설 Idea Dynamic Programming N에 대해 조건을 만족하는 경우에서 3으로 나누기, 2로 나누기, 1을 빼는 연산을 반복 수행하고 각각의 연산횟수 별로 도출할 수 있는 값을 모두 저장 앞선 결과를 모두 활용해 다음 결과에 대한 모든 경우를 탐색하고 결과 집합에 1이 있을 시 탐색을 종료 1이 포함된 마지막 집합의 인덱스 번호를 최소 연산횟수로 출력 Data Size N: 1