본문 바로가기

Algorithm

 (175)
[BOJ] 9095. 1, 2, 3 더하기 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - a1 : 1, a2 : 1, a3 : 2, a4 : 3 - 점화식 유추 : an = an-1 + an-2 - for문으로 3부터 N까지 점화식을 활용해서 값을 구함 2. 시간복잡도 - O(N) """ 2. 정답코드 import sys input = sys.stdin.readline n = int(input()) add_v = 0 for i in range(n): num = int(input()) num_list = [0, 1, 2, 4] for j in r..
[BOJ] 11726. 2×n 타일링 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - a1 : 1, a2 : 2, a3 : 1 + 2 = 3 - 점화식을 유추 : an = an-1 + an-2 - for문으로 3부터 N까지 값을 구함 - 이전 값과 이전이전 값을 더해서 10007로 나눈 나머지를 print 2. 시간복잡도 - O(2N) == O(N) """ 2. 정답코드 import sys input = sys.stdin.readline n = int(input(..
[BOJ] 1339. 단어 수학 https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 입력된 알파벳 단어를 2중 배열로 append - 알파벳에 숫자를 부여하기 위한 alpha_dict 딕셔너리를 만듬 - alpha들을 for문 돌아서 알파벳 위치에 숫자 크기를 부여하고 딕셔너리에 저장 - 딕셔너리의 value 값들을 alpha_list 리스트에 내림차순으로 정렬 - 리스트의 첫 인덱스가 자리 숫자가 가장 큰 숫자이기에 for문으로 9부..
[BOJ] 1715. 카드 정렬하기 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 카드 묶음을 정렬화 된 리스트로 만든다. - 첫 카드 묶음을 temp라는 변수에 저장한다. - for문으로 N까지 순차적으로 합을 계산한다. - 그 합은 다시 temp에 저장된다. - answer은 temp + cards[인덱스 위치]로 갱신한다. --> 틀린 로직 - 비교 횟수를 최소로 만들려면 작은 값들을 먼저 비교하고 큰 값들을 나중에 비..
[BOJ] 1946. 신입 사원 https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 성적을 입력받고 서류심사 등수를 기준으로 오름차순으로 정렬 - 순서대로 면접 순서를 비교하면서 count - temp는 서류 1등을 변수로 저장 - temp와 비교해서 면접 등수가 더 높으면 count + 1 - count + 1 했을 떄, temp에는 비교한 면접 등수가 저장된다. - 남은 인덱스와 위의 내용을 반복 2. 시간복잡도 -..
[BOJ] 16953. A → B https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A B // 2 - 2로 나누다가 일의 자리 숫자가 1인 경우 (if문) 일의 자리 삭제 -> B // 10 - BFS - Bottom-up 방식 - A와 횟수 answer(초기값 1)을 큐에 넣는다. - 여기서 두 가지 방향이 있는데, - 1. A에서 2를 곱하고 answer + 1을 한다. - 2. A에서 10을 곱하고 +1을 한 다음, answer + 1을..
[BOJ] 13305. 주유소 https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 첫 도시의 기름 값을 min_v로 설정 - 각 도시의 기름 값을 리스트로 두어서 min_v랑 비교해서 더 작으면 갱신 - 만약에 더 작다면 이전의 도시의 기름 값을 도시 간의 거리에 곱을 add_v에 더한다. 2. 시간복잡도 - O(N) """ 2. 정답코드 import sys input = sys.stdin.readline N = int(in..
[BOJ] 1541. 잃어버린 괄호 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - input이 들어올 때, '-'를 기준으로 분리해서 배열에 저장한다. - '-' 뒤에 붙은 문자들은 다시 '-'가 올 때까지 빼주어야 한다. - 그러기 위해서는 '+'가 포함된 인덱스에서 다시 한번 분리해서 리스트화 한다. """ 2. 정답코드 import sys input = sys.stdin.readline arr = input().split('-'..

티스토리툴바