백준 1313번 : 합성소수 (Python)

문제링크 https://www.acmicpc.net/problem/1313 문제 총평 - 알고보면 쉬운 완전탐색 문제 접근방식 - n이 천만까지 나오기 때문에 에라토스 테네스의 체를 사용하여 소수를 천만까지 구하고 미리 모든 합성소수를 구해줍니다. - 이후 각각의 n에 따라서 이분탐색을 통해 미리 구해놓은 합성소수에서 n보다 작거나 같은 합성소수 중 가장 큰수를 출력하면 끝입니다. - 하지만 맞힌 사람들 코드를 보니 합성소수는 31373 까지 밖에 없다는 걸 깨닷고 소수도 31373까지만 구해주었습니다. 가능한 모든 합성소수 [111, 117, 119, 171, 231, 237, 297, 319, 371, 411, 413, 417, 437, 471, 473, 531, 537, 597, 611, 671, ..

• format_list_bulleted 알고리즘
• · 2024. 1. 13.
• textsms

백준 30505: SASA 마니또 (Python)

문제링크 https://www.acmicpc.net/problem/30505 문제 총평 - 무난한 구현 문제 문제 접근방식 - 이번 문제는 그림을 그려보면 쉽게 풀 수 있습니다. - 1번 예제를 그림으로 그려보면 이런 형식으로 나타낼 수 있습니다. - 이때 5번인 세종이의 번호를 제외한 나머지 1,4 번만이 5번의 마니또가 될 수 있으므로 정답은 2 입니다. - 이점으로 미루어 보아 나의 마니또가 정해지지 않은 사람의 수 - 세종이의 마니또 결합 유무가 가능한 사람의 수인것을 알 수 있습니다. - 하지만 예제 2과 같이 - 2번인 세종이의 마니또는 1,3 번이 가능하지만 3번이 3번의 마니또가 될 수 없으므로 정답은 1이므로 nojam 입니다. - 이 점에서 정답이 2일때 자신의 마니또와 자신이 가지는 ..

• format_list_bulleted 알고리즘
• · 2024. 1. 10.
• textsms

백준 2746: 좋은 배열 만들기 (Python)

문제링크 https://www.acmicpc.net/problem/2746 문제 총평 - 케이스를 잘 생각해 낸다면 쉬웠던 문제 문제 접근방식 - 이번 문제는 처음에 접근을 너무 어렵게 해서 많이 틀렸습니다. - 하지만 단순한 경우의 수라는걸 알면 쉽게 풀 수 있습니다. 정답코드 import sys; input = sys.stdin.readline n = int(input()) arr = list(map(int, input().split())) arr.sort() s = sum(arr) ans = 0 s1 = s-arr[-1] num = [0] * (1000000+1) for i in arr: num[i] += 1 num[arr[-1]] -= 1 for i in set(arr[:-1]): if s1-i-..

• format_list_bulleted 알고리즘
• · 2023. 12. 1.
• textsms

백준 29793: 라라와 용맥 변환 (Python)

문제링크 https://www.acmicpc.net/problem/29793 문제 총평 - 문제 유형을 안다면 매우 쉽게 풀 수 있다. 문제 접근방식 - 이번 문제는 처음에는 굉장히 당황스럽던 문제이지만 문제 풀이법을 알고 나면 아주 쉬웠던 문제였습니다. - + 파이써닉 하게 아주 쉽게 풀 수 있습니다 정답코드 import sys;input = sys.stdin.readline n,m = map(int,input().split()) arr = list(input()) ans = 987654321 if m == 1: print(0) elif m == 2: ans = 0 for i in range(1,n): if arr[i] == arr[i-1]: ans +=1 arr[i] = 0 print(ans) eli..

• format_list_bulleted 알고리즘
• · 2023. 9. 15.
• textsms

[백준] 13537 수열과 쿼리 1 - 머지소트트리(merge sort Tree) (Python)

문제링크 https://www.acmicpc.net/problem/13537 문제 총평 - 머지 소트 트리를 공부한다면 아주 쉽게 풀 수 있다. 문제 접근방식 - 이번 문제는 아무런 문제를 고른 것이 아닌 세그트리를 공부 후, 머지 소트 트리라는 것이 있어서 공부를 하고 나서 풀었습니다. - 다른 요소가 중요하다기 보단 머지 소트 트리 연습 문제같은 느낌이니 머지 소트 트리를 모른다면 학습 후 문제를 푸시는 것을 추천드립니다. - 또한 기존에는 sys를 잘 쓰진 않지만 이 문제에서는 sys로 입력을 받지 않으면 시간 초과가 뜨기 때문에 사용하였습니다. 정답코드 import bisect, math,sys input = sys.stdin.readline n = int(input()) arr = list(ma..

• format_list_bulleted 알고리즘
• · 2023. 8. 7.
• textsms

[백준] 20442 ㅋㅋ루ㅋㅋ - 투 포인터 (Python)

문제링크 https://www.acmicpc.net/problem/20442 [20442번: ㅋㅋ루ㅋㅋ 어떤 문자열에서 몇 개의 문자를 지워서 부분 수열을 만들 수 있다. 예를 들어, ABC의 부분 수열은 ABC, AB, BC, AC, A, B, C와 빈 문자열이다. www.acmicpc.net](https://www.acmicpc.net/problem/20442) 문제 총평 - 투 포인터를 사용하여 문자열을 탐색하는 문제이다. - 문제는 어렵지 않으나 문자열의 길이를 보고 바로 투포인터를 생각하지 못한다면 어렵다고 생각이 든다. 문제 접근방식 - 처음에는 문자열의 최대 길이가 300만 이라는 것을 보고 당황을 하였는데 이렇게 범위가 클 때는 항상 알고있는 자료구조를 떠올리면서 접근을 하면 풀이법을 생각..

• format_list_bulleted 알고리즘
• · 2023. 8. 6.
• textsms