우당탕탕 공부중

https://www.acmicpc.net/problem/11866📌 문제 탐색하기목표원에서 사람들이 제거되는 순서인 요세푸스 순열을 출력한다.입력값첫째 줄에 사람 수인 n과 번째를 나타내는 k가 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)ex)7 3출력값(n, k)-요세푸스 순열을 출력한다.ex)📌 코드 설계하기해결 아이디어n+1 길이의 False로 채워진 Boolean 배열을 만들고 True의 개수가 K개일 때 출력하면 되나?흠 그러면 while문과 그 안에 for문이 들어가야되고 cnt도 k가 될때까지 판단해야 해서 계산량이 많다.그러면 어짜피 삽입할 때 O(N)은 소비되고 그 뒤로 삭제가 빠른 linked list를 써서 해결해보자.k-1만큼 이동해서 next_node를 삭제하고 n..

https://www.acmicpc.net/problem/2193📌 문제 탐색하기목표0으로 시작하지 않고, 1이 두 번 연속으로 나타나지 않는 이친수의 개수를 구한다.입력값첫 줄에 자릿수를 나타내는 n을 입력한다. (1 ≤ N ≤ 90)ex)3출력값n자리 이친수의 개수를 출력한다.ex)2📌 코드 설계하기해결 아이디어가장 처음으로 해야될게 입력된 정수를 binary로 바꿔야하는 것이다. 파이썬에 이렇게 이진수로 바꾸는 함수가 있나.?이진수로 바꿔서 코드를 작성했더니 시간 초과가 떴다.그러면 규칙을 찾아야한다. 이진수는 계속 반복된다. dp를 사용할 수는 없을까?📌 1차 제출 코드import sysinput = sys.stdin.readlinen = int(input().strip())cnt = 0fo..

https://www.acmicpc.net/problem/2303📌 문제 탐색하기목표각각 1~10사이의 수가 적힌 다섯 장의 카드 중 세 장의 카드에 적힌 수의 합을 구한 후 일의 자리 수가 가장 큰 사람이 이기는 게임을 진행한다.n명에게 각각 다섯 장의 카드가 주어졌을 때 이기는 사람을 출력한다.입력값첫 줄에는 사람의 수 n이 주어진다. (2 ≤ n ≤ 1000)n줄에 걸쳐 각 사람이 가진 카드가 주어진다. 이는 1 ~ 10의 정수 다섯 개이다.ex)3 7 5 5 4 9 1 1 1 1 1 2 3 3 2 10출력값n명에게 각각 다섯 장의 카드가 주어지고 세 장의 카드를 골라 합을 구한 후 일의 자리 수가 가장 큰 사람을 출력한다.가장 큰 수를 갖는 사람이 두 명 이상일 경우는 번호가 가장 큰 사람의 번..

https://www.acmicpc.net/problem/5567📌 문제 탐색하기목표친구의 친구까지 결혼식에 초대할 때 결혼식에 초대하는 동기의 수를 출력하자.입력값첫째 줄에 상근이의 동기수 n을 입력한다. (2 ≤ n ≤ 500)둘째 줄에 리스트의 길이 m을 입력한다. (1 ≤ m ≤ 10000)m개의 줄에는 친구 관계 a, b가 주어진다. (1 ≤ a ex)651 21 33 42 34 5출력값상근이의 결혼식에 초대하는 동기의 수를 출력한다.ex)3📌 코드 설계하기해결 아이디어이번 문제는 그래프 탐색을 하는 문제이다. dfs에서 했듯 모든 관계를 배열에 삽입하여 친구 관계를 저장한다.그리고 dfs를 2번만 돌아서 친구의 친구까지만 count할 수 있도록 하자.이렇게 코드를 짜고 있었는데 훨씬 쉬운..

https://www.acmicpc.net/problem/2204📌 문제 탐색하기목표대소문자를 구분하지 않고 사전순으로 가장 앞서는 단어를 출력하자.입력값매 테스트케이스마다 단어의 개수를 뜻하는 정수 n이 주어진다. (2 ≤ n ≤ 1000)다음 각 n줄은 길이가 최대 20인 단어가 주어진다.ex)3 Cat fat bAt 4 call ball All Hall 0출력값각 줄에 각 테이스케이스에서 사전순으로 가장 처음 등장하는 단어를 출력한다.ex)bAt All📌 코드 설계하기해결 아이디어이번 문제는 sort를 사용하면 되는 문제이다.입력을 받고 모든 단어를 lower로 환산해서 사전 순으로 sort하게끔 한 뒤 가장 앞에 있는 단어를 출력한다.다만, 특이한 점은 0이 입력되기 전까지 지속적으로 n을 입..

https://www.acmicpc.net/problem/2644📌 문제 탐색하기목표주어진 두 사람의 촌수를 계산하는 프로그램을 작성해보자.즉, 사람들 간의 관계가 주어졌을 때 서로 얼마나 많이 떨어져있는지 계산해서 반환하는 문제이다.입력값첫째 줄에 전체 사람수 n이 주어진다. (1 ≤ n ≤ 100)둘째 줄에 얼마나 많이 떨어져있는지 계산해야하는 두 사람의 번호가 주어진다.셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 부모 자식간의 관계이므로 해당 문제에서 사이클은 없다고 판단할 수 있다.넷째 줄부터 부모 자식간의 관계를 나타내는 번호 x, y가 주어진다. 이때, x가 부모, y가 자식이다.ex)97 371 21 32 72 82 94 54 6출력값두 사람의 촌수를 나타내는 정수를 출력한다..

https://www.acmicpc.net/problem/11724📌 문제 탐색하기목표방향 없는 그래프가 주어졌을 때 연결 요소의 개수를 구해보자.입력값첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2)둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v)ex)6 5 1 2 2 5 5 1 3 4 4 6출력값연결 요소의 개수를 출력한다.ex)2📌 코드 설계하기해결 아이디어이 문제도 어제와 비슷한 그래프 문제다. 근데 달라진 점은!그동안 계속 인덱스를 활용해서 그래프를 이었는데 이제는 이어질 정점의 값도 들어온다.하지만 여전히 dfs로 충분히 풀 수 있는 문제이다. 어쨋든 모든 정점에 방문해..

https://www.acmicpc.net/problem/17204📌 문제 탐색하기목표0번부터 시작해서 보성이의 번호 K까지 순서가 이어질 수 있는지 판단한다.순서가 이어질 수 없다면 -1을, 이어질 수 있다면 걸리는 횟수를 출력한다.입력값첫째 줄에 게임에 참여하는 사람의 수 N과 보성이의 번호 K가 공백을 두고 주어진다. (3 ≤ N ≤ 150, 1 ≤ K ≤ N - 1)둘째 줄부터 N줄에 걸쳐 i번 사람이 지목하는 사람의 번호 $a_i$가 주어진다. (0 ≤ i ≤ N - 1, 0 ≤ $a_i$ ≤ N - 1)ex)5 3 1 3 2 1 4출력값영기가 말해야하는 가장 작은 양의 정수 M을 출력한다.보성이가 마지막에 지목되지 못한다면 -1을 출력한다.ex)2📌 코드 설계하기해결 아이디어어제와 비슷한 ..

https://www.acmicpc.net/problem/10451📌 문제 탐색하기목표순열을 그래프로 만들어서 얼마나 많은 사이클이 나오는지 출력하기입력값첫째 줄에 테스트 케이스 개수인 정수 t를 입력한다.각 테스트 케이스의 첫째 줄에는 순열의 크기 N이 주어진다. (2 ≤ N ≤ 1,000)둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다.ex)2 8 3 2 7 8 1 4 5 6 10 2 1 3 4 5 6 7 9 10 8출력값각 테스트 케이스마다 입력으로 주어진 순열에 존재하는 순열 사이클의 개수를 출력한다.ex)3 7📌 코드 설계하기해결 아이디어순열이 이어진 그림을 보고 연결리스트를 먼저 떠올렸다.배열의 인덱스를 1부터 시작할 수 있게끔 0번 인덱스에 0값을 미리 저장해서 시작하고 ..

https://www.acmicpc.net/problem/1463📌 문제 탐색하기목표정수 n이 주어졌을 때 세 가지 연산 기법들을 사용하여 1을 만들어 본다.연산을 사용하는 횟수의 최솟값을 출력한다.사용할 수 있는 연산은 다음과 같다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.입력값정수 n을 입력한다. (1 ≤ n ≤ $10^6$)ex)10출력값세 가지 연산들을 사용하는 횟수의 최솟값을 출력한다.ex)3📌 코드 설계하기해결 아이디어시간 제한이 0.15초이므로 재귀나 반복되는 계산을 모두 줄여야한다.수의 규칙을 찾기 위해 쭉 써보면 다음과 같은 결과가 나오게된다.연산을 위해 이미 연산이 되어있는 앞의 숫자를 사용하면 되는 것이다.그러면 bottom-..