Engineering Note

문제 https://www.acmicpc.net/problem/9372 [ 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net ](https://www.acmicpc.net/problem/9372) 문제해결방법 최소 방문은 항상 연결된 그래프이기 때문에 방문한 곳을 또 방문하지 않고 그대로 이어진 길을 모두 따라서 방문하면 된다. 근데 이렇게 하면 사실 전체 국가수에서 -1을 한 값이다. 그래도 DFS로 한번 풀어 보았다. 문제에 주어진 첫 번째 테스트 케이스에 대한 그림 그..

문제 https://www.acmicpc.net/problem/14241 [ 14241번: 슬라임 합치기 영선이와 효빈이는 슬라임을 합치는 게임을 하고 있다. 두 사람은 두 슬라임을 골라서 하나로 합쳐야 한다. 게임은 슬라임이 하나 남았을 때 끝난다. 모든 슬라임은 양수 크기를 가지고 있다. 두 www.acmicpc.net ](https://www.acmicpc.net/problem/14241) 문제해결방법 문제에서 주어진대로 구현하면 되는 문제다. 두 슬라임을 뽑아서 합치고, 점수는 두 슬라임 무게를 곱한 값을 누적해주면 되고 합쳐진 슬라임은 다시 슬라임 상자에 넣어주고 두 슬라임을 뽑아주면서 위 행위를 반복한다. 그리고 하나의 슬라임이 될 때 게임을 종료한다. 코드 import sys n = int(..

문제 https://www.acmicpc.net/problem/16466 [ 16466번: 콘서트 HCPC (Hanyang Completely Perfect Celebrity)는 한양대학교 최고의 가수에게 주어지는 칭호이다. 한양대학교는 매년 최고의 HCPC를 선발한다. HCPC가 되기란 여간 어려운 게 아니다. 매일 아침 날달걀을 까먹 www.acmicpc.net ](https://www.acmicpc.net/problem/16466) 문제해결방법 입력받은 티켓팅 번호들을 정렬한 후 1,2,3,4 순으로 차례대로 일치하는지 검사하고 다른 값이 출현하면 그때 그값이 1차 티켓팅에서 팔리지 않은 가장 작은 숫자이다. 만약에 모두 확인했는데도 다른 숫자가 없었다면 1부터 N까지 숫자모두 존재 하는 것이기때문..

문제 https://www.acmicpc.net/problem/17298 [ 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net ](https://www.acmicpc.net/problem/17298) 문제해결방법 모든 숫자마다 자기보다 크면서 자기와 가까운 우측에 존재하는 수를 찾으면 시간복잡도가 거의 N^2에 가깝게 나온다. 이를 해결하기 위해 중복된 계산을 다시 해주지 않는 방법을 생각했다. 오큰수를 찾는 과정을 머리로 그려 보자. 첫 번째 수부터 마지막 수까지 차례대로 숫자를 꺼내면서 오큰수를 찾지 못한 수는 기록해둔..

문제 https://www.acmicpc.net/problem/11725 [ 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net ](https://www.acmicpc.net/problem/11725) 코드 import sys from collections import deque def go(start, graph, visited): global res q = deque() q.append(start) while q: parent = q.popleft() visited[parent] = True for child in graph[parent]: if not visited[chi..

문제 https://www.acmicpc.net/problem/11866 [ 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net ](https://www.acmicpc.net/problem/11866) 코드 import sys from collections import deque sys.stdin = open("input.txt") N, K = map(int,sys.stdin.readline().rstrip().split()) check = [False]*(N+1) check[0] = True q = deque() res = [] cnt = 0 for i in range(1,N+1): q.appen..

it 취업을 위한 알고리즘 문제 풀이 문제 https://www.acmicpc.net/problem/2231 코드 import sys n = int(sys.stdin.readline().rstrip()) for i in range(n): res = 0 temp = i while temp: num = temp%10 temp //= 10 res += num if res+i == n: print(i) break else: print(0) 문제해결방법 문제를 정확히 읽으면 쉽게 해결 할 수 있는 문제이다. 분해합, 생성자의 정의를 이해하고 분해합을 만드는 생성자는 분해합보다 작다라는 추론을 하면 브루트포스로 쉽게 구현할 수 있다. 생성자를 구하기 위해서는 주어진 N보다는 무조건 작은 숫자여야 한다. 이유는 N보..

문제 https://www.acmicpc.net/problem/1436 [ 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net ](https://www.acmicpc.net/problem/1436) 코드 import sys n = int(sys.stdin.readline().rstrip()) devliMovie = 666 series = 0 while True: if "666" in str(devliMovie): series += 1 if series == n: print(devliMovie) break dev..