본문 바로가기
728x90
반응형

코딩/백준

알고리즘 - Python / 백준 - 2729번 : 이진수 덧셈 2729번: 이진수 덧셈 (acmicpc.net) 2729번: 이진수 덧셈 이진수 덧셈은 매우 간단하고, 십진수 덧셈과 비슷하게 하면 된다. 십진수 덧셈을 할 때는, 오른쪽부터 왼쪽으로 차례대로 숫자 하나씩 더하면 된다. 이진수 덧셈도 이와 비슷하게 하면 된다. 십 www.acmicpc.net 풀이 각 케이스에 대해 이진수 2개를 입력받고 , 두 이진수를 더한 결과를 이진수로 출력하는 문제이다. 파이썬은 진수변환과 관련한 다양한 함수가 존재하므로 , 이를 통해서 쉽게 해결가능하다. n = int(input()) for _ in range(n): a,b = input().split(" ") a = int(a,2) b = int(b,2) print(bin(a+b).replace("0b","")) 더보기
알고리즘 - Python / 백준 - 3020번 : 개똥벌레 3020번: 개똥벌레 (acmicpc.net) 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 풀이 동굴에 종유석과 석순이 있고 개똥벌레가 날아갈 때 , 부수는 종유석과 석순 개수의 최솟값을 구하고 그러한 구간이 얼마나 있는지 구하는 문제이다. N,H의 범위가 2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000 이므로 , 한줄 한줄 따라가며 계산하면 시간초과가 날 것이다. 종유석의 길이가 4 라면 , 4 3 2 1 구간은 모두 부숴야할 종유석이 +1 되고 , 석순도 거꾸로 보면 같다. 따라서 종유석과 석순.. 더보기
알고리즘 - Python / 백준 - 1239번 : 차트 1239번: 차트 (acmicpc.net) 1239번: 차트 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 8보다 작거나 같다. 둘째 줄에, 민식이가 조사한 개의 수가 주어진다. 개의 수는 100 이하의 자연수이고, 조사한 개의 수의 합은 항상 100이다. www.acmicpc.net 풀이 파이차트의 퍼센트를 입력받고 중앙을 지나는 라인의 최대 수를 구하는 문제이다. 항목의 수인 N이 8이 최대 이므로 모든 경우를 다 살펴보는 경우는 8! = 40,320 이다. 따라서 파이썬으로도 시간내에 모든 경우를 살펴볼 수 있다고 생각하여 전수조사 하였다. 이후 해당 경우에 라인이 어느 포인트에 그려지는지 리스트에 추가하고 리스트 항목에 +50 한 수가 포함되어 있는지 확인하는 식으로 라인 개수를 세었다. .. 더보기
알고리즘 - Python / 백준 - 5615번 : 아파트 임대 5615번: 아파트 임대 (acmicpc.net) 5615번: 아파트 임대 첫째 줄에 아파트의 면적의 수 N이 주어진다. 다음 줄부터 N개 줄에 카탈로그에 적혀있는 순서대로 면적이 주어진다. N은 100,000이하이고 면적은 231-1이하인 양의 정수이다. www.acmicpc.net 풀이 아파트의 면적이 2xy + x + y 일때 , ( x , y는 양의 정수 ) 면적이 될 수 없는 값을 구하는 문제이다. 식을 정리하면 2S + 1 = (2x + 1)(2y + 1) 이므로 , 두 홀수의 곱으로 다른 홀수를 만들 수 있는지 없는지 판단하는 문제이다. 따라서 2S + 1 이라는 홀수가 소수인지 아닌지 판별하는 문제이다. S의 범위가 매우 크므로 , 일반적인 소수 알고리즘이 아닌 "밀러-라빈 소수 판별법"을.. 더보기
알고리즘 - Python / 백준 - 9660번 : 돌 게임 6 9660번: 돌 게임 6 (acmicpc.net) 9660번: 돌 게임 6 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000) www.acmicpc.net 풀이 N개의 돌을 1 , 3 , 4개 씩 번갈아 가며 가져가는 게임에서 마지막 돌을 가져가면 승리한다. 두 사람 모두 최선의 플레이를 한다고 했을때 , 이기는 사람을 구하는 문제이다. 처음 보았을 때 DP 스타일의 문제 라고 생각했지만 , N의 크기가 1,000,000,000,000 이었기에 DP는 접어두고 규칙을 찾기 시작했다. 규칙을 찾아보니 2 부터 시작해 모두 찾아보니 +5 , +2 +5 , +2 ... 더해나가는 경우가 창영이가 승리하는 경우라는 것을 찾을 수 있었다. #1 - 상근 #2 - 창영 #3 - 상근 #4 .. 더보기
알고리즘 - Python / 백준 - 2115번 : 갤러리 2115번: 갤러리 (acmicpc.net) 2115번: 갤러리 첫째 줄에 갤러리의 세로 길이 M과 가로 길이 N이 주어진다. (1 더보기
알고리즘 - Python / 백준 - 1715번 : 카드 정렬하기 1715번: 카드 정렬하기 (acmicpc.net) 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 풀이 정렬된 묶음의 카드들을 합쳐 하나의 묶음으로 만들 때 , 가장 적게 비교하도록 만드는 문제이다. 문제 자체는 직관적이라 가장 작은 것 2개를 합치고 그걸 다시 배열에 넣고 하는 과정을 계속 진행하면 된다. 배열에 넣을 때마다 정렬이 필요하므로 heap을 통해서 위의 알고리즘을 구현하였다. import sys import heapq n = int(sys.stdin.readline()) stac.. 더보기
알고리즘/숏코딩 - Python / 백준 - 2154번 : 수 이어 쓰기 3 2154번: 수 이어 쓰기 3 (acmicpc.net) 2154번: 수 이어 쓰기 3 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. www.acmicpc.net 풀이 1부터 100,000까지의 수를 이어 붙이고 그 문자열 중에서 특정 숫자가 몇 번째에 나오는지 찾는 문제이다. 파이썬이 find() 나 index()를 통해 문자열에서 특정 문자의 위치를 찾는 것이 편하므로 코드가 짧을 것 같아 숏코딩에 도전하였다. 처음 든 생각은 for문으로 1부터 100,000까지 모든 수를 문자열에 이어 붙이고 그 문자열에서 find를 사용하는 것이었다. 위의 방법은 65B 로 숏코딩 1등을 위해서는 더 짧아야 했다. 두 번째로는 어차피 n의 범위가 100,000 까지 이므로 for문 안에서 100,000이.. 더보기
반응형

티스토리툴바