Python/백준 문제 풀이43 [BOJ] 1018번 체스판 다시 칠하기 [BOJ] 1018번 체스판 다시 칠하기 문제 처음 보면 엄청 당혹스러운 브루트 포스 문제다. 먼저, 브루트 포스(Brute force)는 말 그대로 무차별 대입을 뜻하며, 어떠한 규칙을 구하는 것이 아닌 모든 경우의 수를 따지는 방법이다. 모든 경우의 수를 따지다 보니 $ N $이 적당히 작아야 하며, 실행 시간도 $ N $에 맞게 커야 한다. 이 문제의 경우엔 2초로 설정되어 있다. 만약 $ N $이 크거나 시간이 짧다면 브루트 포스를 하면 안 되고, 그리디 알고리즘이나 특정 알고리즘을 사용해야 한다. $ N $이 적당히 작아 보이고, 그에 맞거나 약간 긴 시간 제한이 주어지며, 바로 떠오르는 알고리즘이 없다면 주로 브루트 포스를 사용하게 된다. 모두 다 대입하는게 컴퓨터를 배우는 입장에서 덜 떨어져.. 2022. 9. 5. [BOJ] 2447번 별 찍기 - 10 [BOJ] 2447번 별 찍기 - 10 문제 매우 어려운 재귀 문제다. 뉴비 절단기 삼대장 중 하나답게 매우 어렵다. 재귀의 핵심은 반복되는 부분을 코드로 압축시키는 것이다. 먼저 이 문제에서는 어떻게 반복되는지를 살펴보자. 먼저 $ 1 \leq k < 8 $이지만 $ k = 0 $의 경우도 있다고 치자. 그렇다면 $ k = {0, 1, 2} $일 때의 패턴은 아래와 같다. # k == 0 * # k == 1 *** * * *** # k == 2 ********* * ** ** * ********* *** *** * * * * *** *** ********* * ** ** * ********* 패턴이 보이는가? $ k \geq 1 $부터 $ k $번째 패턴에서의 첫 $ 3^{k-1} $줄에는 $ k-1 .. 2022. 8. 31. [BOJ] 12018번 Yonsei TOTO [BOJ] 12018번 Yonsei TOTO 문제 꽤 쉬운 그리디 알고리즘이다. 연세 토토(또는 카지노)를 안다면 더 쉽게 풀 수 있다. 연세 카지노는 2015년부터 열린 유서 짧은 수강신청 방법이다. 기존의 수강신청과 다르게 오직 마일리지 배팅만으로 수강신청과 기타 우선순위 등을 고려해 수강 합불이 결정된다. 서버 터질 걱정도 없고 기간 내에만 배팅하면 된다는 압도적인 장점은 있었으나, 정작 인원이 많고 강의가 적었던 학부에서는 일부 학생이 우주 공강이 되어버려 휴학까지 하는 지옥이 펼쳐졌다. 이는 현재까지 보완이 계속 진행되었지만 여전히 문제라고 한다. 이젠 내겐 있어서 다 옛말이지만... 그립긴하다. 핵심은 수강 인원보다 배팅한 사람이 적으면 1만 넣으면 되고, 그렇지 않다면 총 배팅한 사람 중 가.. 2022. 8. 12. [BOJ] 10871번 X보다 작은 수 [BOJ] 10871번 X보다 작은 수 문제 X보다 작은 수를 수열 순서대로 출력하면 되는 문제다. import sys if __name__ == '__main__': N, X = map(int, sys.stdin.readline().rstrip().split()) A = list(map(int, sys.stdin.readline().rstrip().split())) for num in A: if num < X: print(num, end=' ') for문의 iterable 객체의 특성을 사용하면 쉽게 풀 수 있다. 2022. 8. 10. [BOJ] 1110번 더하기 사이클 [BOJ] 1110번 더하기 사이클 문제 기존 두 자릿수에서의 일의 자리 숫자와 두 수를 합한 수의 첫 번째 수를 합친 수로 새로운 수를 만들 때 기존의 수로 돌아올 때의 사이클 횟수를 구하는 방법을 구해야 하는 문제다. import sys if __name__ == '__main__': N = int(sys.stdin.readline().rstrip()) temp_N = N count = 0 while True: temp_N = (temp_N%10)*10 + sum(list(map(int, str(temp_N))))%10 count += 1 if temp_N == N: break print(count) 문제를 이해했다면 쉽게 풀 수 있는 문제다. 2022. 8. 10. [BOJ] 10952번 A+B - 5 [BOJ] 10952번 A+B - 5 문제 반복문과 조건문을 적절히 잘 써야 하는 문제다. import sys if __name__ == '__main__': while True: A, B = map(int, sys.stdin.readline().rstrip().split()) if A == 0 and B == 0: break print(A + B) A와 B가 각각 0과 0일 때에 무한 루프를 풀면 된다. 2022. 8. 10. [BOJ] 17114번 하이퍼 토마토 [BOJ] 17114번 하이퍼 토마토 문제 매우 흔한 BFS 문제이다. 대신 11차원일 뿐이다... 2차원 토마토와 3차원 토마토 문제는 아래에 적어둔다. [BOJ] 7576번 토마토 문제 (2차원) [BOJ] 7569번 토마토 문제 (3차원) 핵심은 위의 두 문제와 별반 다르지 않다. 입력을 받고, 1인 곳의 좌표를 저장하고, 그 좌표에서 계속 BFS를 돌려서 값을 갱신하고, 다시 모든 좌표를 돌아 0이 나오면 -1을 출력 후 종료하고 아니라면 모든 좌표값 중 최댓값을 구하는 것이다. 위의 2차원과 3차원과의 차이가 있다면, 이 문제는 무려 11차원이다. 입력 받는 것부터가 장난이 아니다. 다만 차원만 높을 뿐이지 푸는 데에는 큰 차이가 없어서 복잡한 입력 처리 연습으로 매우 괜찮은 것 같다. impo.. 2022. 8. 10. [BOJ] 15926번 현욱은 괄호왕이야!! [BOJ] 15926번 현욱은 괄호왕이야!! 문제 굉장히 어려웠던 스택 문제다. 올바른 괄호 문자열의 전체 길이를 구하는 것과 그 길이가 얼마만큼 되는 것인지가 중요하다. import sys if __name__ == '__main__': N = int(sys.stdin.readline().rstrip()) bracket_str = list(sys.stdin.readline().rstrip()) max_bracket = 0 stack = [-1] for i in range(N): if bracket_str[i] == '(': stack.append(i) else: stack.pop() if stack: max_bracket = max(max_bracket, i-stack[-1]) else: stack.a.. 2022. 8. 10. [BOJ] 14681번 사분면 고르기 [BOJ] 14681번 사분면 고르기 문제 if - else문을 연습할 수 있는 좋은 문제이면서 매우 쉬운 문제다. import sys if __name__ == '__main__': x = int(sys.stdin.readline().rstrip()) y = int(sys.stdin.readline().rstrip()) if x > 0: print(1 if y > 0 else 4) else: print(2 if y > 0 else 3) print문 안에 if - else문을 넣을 수 있는 파이썬의 미친 성능을 체감할 수 있다. 2022. 8. 4. [BOJ] 1330번 두 수 비교하기 [BOJ] 1330번 두 수 비교하기 문제 간단한 조건문 문제다. import sys if __name__ == '__main__': a, b = map(int, sys.stdin.readline().rstrip().split()) if a > b: print('>') elif a < b: print(' 2022. 8. 4. 이전 1 2 3 4 5 다음 728x90
