본문 바로가기

Algorithm/BOJ

 (95)
[BOJ] 2579. 계단 오르기 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 첫 번째 계단의 값을 초기 값을 result에 append - 두 번째와 첫번째의 합, 두 번째를 비교해서 큰 값을 result에 append - 세 번째는 첫 번째와 세 번째 합, 두 번째와 세 번째의 합을 비교해서 큰 값을 result에 append - 3번째 부터 n번째 까지 for문을 돌린다. - 네 번째는 네 번째 인덱스와 result[i-2]의 합과 네 번째 ..
[BOJ] 1003. 피보나치 함수 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 피보나치 수열을 이용해서 1이 출력된 횟수와 0이 출력된 횟수를 카운트 한다. - 카운트 된 횟수를 배열에 append해서 print 2. 시간복잡도 - O(40N) == O(N) """ 처음에 zero는 1,0로 나열되고 one은 0,1로 나열된다. 그 이후의 n번째부터는 피보나치 수열(N2 = N1 + N0)로 나열된다. 그렇다면 이제, 규칙을 가지고 구현해보자. 0과 1의 초기배열을 먼저 만들어준다. 0은 [1,0] 1은 [0,1] 로 정해져있음. ..
[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을..

티스토리툴바