본문 바로가기

전체 글

 (351)
[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을..
트랜잭션 race condition 처리 1. 문제 특정 게시물의 조회수를 센다거나, 은행 계좌의 잔고를 관리하는 어플리케이션을 로직을 개발한다고 가정해보자. 이런 경우에 원래 모델의 값을 읽어서, +1 을 한다거나 특정 값을 더해서 새로운 값을 업데이트한다. Django에서 race condition을 고려하지 않고 단순하게 코드를 짜면 다음과 같이 짤 수 있다. post = Post.objects.get(id=1) post.view_count = post.view_count + 1 post.save() ---------- account = BankAccount.objects.get(id=1) account.balance = account.balance + remittance_ammount account.save() 위 코드는 race con..
[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..

티스토리툴바