본문 바로가기

분류 전체보기16

[자바] 백준 - 1018 (브루트포스) https://www.acmicpc.net/problem/1018 이 문제는 난이도가 실버 4에 정답률도 50%라 가볍게 시작했지만, 꽤 오래 걸렸던 문제이다. 우선 처음에 문제를 보고는 BFS를 떠올렸다.맨 왼쪽 위 칸에서 시작해서 해당 칸과 인접한 칸들은 반대의 색을 가지도록 계산하면 어떨까 했지만, 그러면 매번 체스칸의 색을 바꿔야 할 거 같아서 접었다. 다음으로는 문제를 다시 한 번 보고 생각했다.문제에서 체스판을 색칠하는 경우는 두 가지, 맨 왼쪽 위 칸이 흰색일 경우와 검은색일 경우라고 말을 해줬기 때문에 이것이 힌트라고 생각했다.그래서 나는 생각했다. "패턴은 'BWBWBWBW', 'WBWBWBWB' 두 가지뿐이니까 탐색할 체스판을 한 줄 씩 패턴과 비교하여 색이 다른 칸이 나올 때마다 카운.. 2025. 3. 2.
[파이썬, 자바] 백준 - 1747 (에라토스테네스의 체) https://www.acmicpc.net/problem/1747 이 문제는 소수 판별과 팰린드롬 판별만 할 수 있으면 쉽게 풀 수 있다. 1. 소수를 판별한다.  - 문제에서 주어진 N보다 큰 수가 팰린드롬일 수 있기 때문에 N의 최댓값보다 더 큰 범위의 소수를 판별해야 한다. 2. 팰린드롬을 구한다. - 숫자를 문자로 바꾸는 방법만 알면 된다. 구체적인 메커니즘은 주석으로 자세히 달아놨다. Code(Python)import sysinput = sys.stdin.readlineN = int(input())maxN = 2000000sosu = [False, False] + [True] * (maxN - 1)# 소수 판별# False : 소수 X# True : 소수 Ofor i in range(int(ma.. 2024. 12. 12.
[파이썬, 자바] 백준 - 1456 (에라토스테네스의 체) https://www.acmicpc.net/problem/1456 이 문제는 파이썬으로는 금방 풀었지만, 자바는 아직 미숙해서 한참 헤맸던 문제다.그 이유는 뒤에서 다루겠다. 1. 거의 소수를 구하기 위해 소수를 먼저 구한다. - 소수는 B의 제곱근까지만 구해준다. - 예를 들어 B가 10^14이고 현재 소수가 B의 제곱근인 10^7일 때, 거의 소수는 10^7에 제곱을 한 10^14가 된다. - 그 이상의 거의 소수에 대해서는 범위를 넘어가기 때문에 구해줄 필요가 없다. - 즉 B의 제곱근인 10^7보다 큰 소수는 거의 소수를 구해도 범위를 초과해버리기 때문에 계산에 필요하지 않다. - 따라서 B의 제곱근까지만 소수를 구해도 B의 범위 내에 있는 거의 소수를 모두 구할 수 있다. 2. 거의 소수를 구한.. 2024. 12. 11.
[파이썬, 자바] 백준 - 1744 (그리디 알고리즘) https://www.acmicpc.net/problem/1744 1. 양수와 음수가 둘 다 나올 수 있기 때문에 따로 생각해야 한다.    - 큰 숫자부터 두 개씩 묶어서 곱한 후에 더한다.    - 합이 최대가 되려면 되도록 음수가 없어야 한다.  - 음수를 없애기 위해서 음수는 음수끼리 곱해준 뒤에 더하도록 한다.  - 음수 또한 곱했을 때 결과가 가장 커야 하기 때문에 절댓값이 큰 순으로, 즉 작은 숫자부터 두 개씩 묶어서 곱한 후에 더한다. 2. 양수는 내림차순 정렬, 음수는 오름차순 정렬한다. - 만약 양수던 음수던 숫자가 홀수개 있다면, 마지막 하나의 수는 곱셈을 진행할 수 없다. - 양수의 경우 가장 작은 양수가 마지막에 남아야 하고, 음수의 경우 가장 큰 음수가 마지막에 남아야 한다. -.. 2024. 12. 6.
[파이썬, 자바] 백준 - 1541 (그리디 알고리즘) https://www.acmicpc.net/problem/1541 +와 -로만 이루어져 있는 식을 최소로 만드려면 빼야할 값을 최대한 키워서 빼면 된다. 1. -를 기준으로 식 슬라이싱2. 분해된 부분식 덧셈 연산3. 연산된 결과값 뺄셈 연산 풀이법을 생각해내기만 한다면, 문자열 슬라이싱으로 해결할 수 있는 문제이다. Code(Python)import sysinput = sys.stdin.readlinedef cal(li): # 부분식 연산 함수 li = li.split('+') # 부분식을 + 기준으로 슬라이싱 subSum = 0 # 부분합 for num in li: # 슬라이싱된 문자들 subSum += int(num) # 숫자로 바꿔서 덧셈 return subSum.. 2024. 12. 2.
[파이썬, 자바] 백준 - 1715 (그리디 알고리즘, 우선순위 큐) https://www.acmicpc.net/problem/1715 처음 이 문제를 봤을 때는 시간복잡도 내에 어떻게 풀지 전혀 감을 잡지 못 했지만, 우선순위 큐를 알고 있는 지금은 쉽게 풀 수 있었던 문제다. 먼저 들어온 데이터가 먼저 나가는 FIFO 형태의 일반적인 큐와 달리, 들어온 순서에 상관없이 우선순위가 높은 데이터가 먼저 나가는 큐이다.  문제 예제를 보면, 10, 20, 40의 카드 뭉치가 있을 때, 가장 적게 비교하여 합치는 방법은 (10 + 20) + (30 + 40) = 100이다. 즉, 적은 수의 카드 뭉치들부터 뭉치면 최소 횟수로 비교하여 합칠 수 있는 것이다. 이 예제만으로는 감이 안 잡혔다. "그냥 큐에 크기 순으로 넣고 두 개씩 뽑으면서 더하고, 더해서 나온 새로운 숫자를 다.. 2024. 12. 2.

티스토리툴바