본문 바로가기

파이썬12

순열 사이클 분할:백준 25577, 7805, 10451 1. 기본 개념순열 $(a_1, a_2, \dots, a_n)$이 주어졌을 때, 이를 함수 $f(i)$로 표현할 수 있다. 여기서 $f(i)$는 $i$번째 원소를 다른 원소의 위치로 매핑하는 함수이다.예를 들어, 순열 $(2, 3, 1)$이 있다면:$f(1) = 2$: 첫 번째 위치의 원소는 두 번째 위치로 간다.$f(2) = 3$: 두 번째 위치의 원소는 세 번째 위치로 간다.$f(3) = 1$: 세 번째 위치의 원소는 첫 번째 위치로 간다.2. 함수의 반복적 적용$f^2(i) = f(f(i))$: 함수 $f$를 두 번 적용한 결과이다.$f^k(i)$: $f$를 $k$번 반복 적용한 결과이다.만약 $i = f^k(i)$가 되는 최소 $k$를 찾으면, 이는 $i$가 순환하는 주기이다.3. 순열 사이클$i.. 2025. 1. 9.
백준18005🐨Even or Odd? https://www.acmicpc.net/problem/18005문제의 주요 조건을 살펴보자.picked n consecutive positive integers between 1 and 1018 guess if their sum is even or oddIf the sum must be even, write 2.If the sum must be odd, write 1.If the sum could be even or could be odd, write 0.The single line of input contains a single integer n (1 ≤ n ≤ 109). 일련의 $n$개 수의 합이 홀수가 되거나 짝수가 되는 것은홀수로 시작하는지 짝수로 시작하는지가 영향을 줄 것이다.홀수로 시작하는.. 2024. 8. 6.
파이썬🐨더욱 더 로우레벨한 입출력 import osarr = list(map(int, os.read(0, os.fstat(0).st_size).split()))is_hacker = any((((i // 2) + 1) * 100)  제시된 코드는 os.read와 os.fstat를 사용하여 표준 입력으로부터 데이터를 읽고 처리하는 방식으로 작성된 코드이다. 이 코드의 동작 방식과 sys.stdin, open(0), input()과의 차이점을 자세히 설명하겠다.코드 분석import os# 표준 입력으로부터 데이터를 읽어온다arr = list(map(int, os.read(0, os.fstat(0).st_size).split()))# 조건에 따라 'hacker'인지 아닌지 판별is_hacker = any((((i // 2) + 1) * 100).. 2024. 7. 31.
백준3015🐨오아시스 재결합.py 백준 3015번 “오아시스 재결합” 문제는 스택을 이용하여 각 사람이 볼 수 있는 다른 사람의 쌍을 구하는 문제이다. 아래에 주어진 코드를 바탕으로 문제 풀이를 설명한다:n, *nums = map(int,open(0).read().split())stack = []result = 0for i in range(n): count = 1 while stack and stack[-1][0] 코드 설명초기화 및 입력 처리:n과 nums에 입력 데이터를 받아오고, stack과 result를 초기화한다.스택을 이용한 탐색:각 사람의 키를 nums에서 하나씩 순서대로 처리한다. 현재 사람의 키 nums[i]를 기준으로, 스택에 쌓인 이전 사람들 중 nums[i]보다 작거나 같은 키를 가진 사람들을 제거한다. .. 2024. 7. 30.
백준17298🐨오큰수.py .c + 백준17299🐨오등큰수.py https://redcubes.tistory.com/124 🐨BOJ#6549 히스토그램에서 가장 큰 직사각형] 모노톤 스택(#1725히스토그램)히스토그램에서 가장 큰 직사각형 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 256 MB 54258 14782 9717 26.945% 문제 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이redcubes.tistory.com 오큰수 (NGE: Next Greater Element)오큰수: 현재 숫자 오른쪽에 위치하면서 현재 숫자보다 큰 수 중 가장 왼쪽에 있는 수.예시: 숫자 배열이 [9, 5, 4, 8]일 때 각 숫자의 오큰수는 다음과 같다:9: 오른쪽에 더 큰 수가 없으므로 -15: 오른쪽에 있는 8이 오큰수4: 오른쪽에 있는.. 2024. 7. 28.
🐨BOJ#1300] K번째 수 https://www.acmicpc.net/problem/1300 아이디어1 (구현+약간의 최적화)n × n크기의 배열을 생성해서 일렬로 만든 뒤 개수를 Counter라이브러리로 세어서 키를 정렬해서 탐색아이디어2 (약간의 최적화)n × n크기의 배열을 처음부터 일렬로 만든 뒤 개수를 Counter라이브러리로 세어서 키를 정렬해서 탐색from collections import Countern = int(input())k = int(input())c = Counter([i*j for i in range(1, n+1) for j in range(1, n+1)])tot = 0for key in sorted(c.keys()): tot += c[key] if tot >= k: print(k.. 2024. 5. 23.
🐨BOJ#1697 숨바꼭질]🙄BFS(feat. collections) 문제 보기 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 아이디어 딱 봐도 dp로 풀 수 있을 것 같지만... 머리가 아파서(=어려워서) 수빈이가 도착할 수 있는 위치가 분기로 갈라지는 트리를 만들어서 풀기로 했다. 가장 적은 횟수(빠른 시간)에 동생을 찾아야 하기 때문에, 트리의 깊이가 가장 얕은 게 정답이다. 그래서 dfs로 탐색한 뒤 깊이를 비교하는 것 보다 bfs를 사용해야 한다고 생각했다. 그리고 분기.. 2024. 3. 29.
백트래킹(Backtracking, 퇴각검색) # 14889번 스타트와 링크, # 9663번 N-Queen [파이썬] 목차 그래프와 트리 탐색 알고리즘 백트래킹의 소개 개념 방법 성능개선 개발 활용 사례(예산 활용법 찾기) 알고리즘 설명 코드보기 백준 문제 #14889 스타트와 링크 # 9663번 N-Queen α–β A* B* 퇴각검색 빔 벨먼-포드 최상 우선 양방향 Borůvka 분기 한정법 BFS 영국박물관 D* DFS 데이크스트라 에드먼즈 플로이드-워셜 Fringe search 언덕등반기법 IDA* 반복적 깊이심화 존슨 Jump point 크러스컬 Lexicographic BFS LPA* 프림 SMA* 출처: https://ko.wikipedia.org/wiki/%ED%87%B4%EA%B0%81%EA%B2%80%EC%83%89 퇴각검색 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 퇴각검색.. 2024. 2. 14.
14889번 스타트와 링크 - 백 트래킹 14889번 스타트와 링크 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 더보기 문제의 이해 어떤 사람과 팀이 되느냐에 따라 능력치가 달라질 때 두 팀의 능력치 차이가 가장 적을 때 얼마인지 알아내는 문제다. 직관적으로 떠오르는 방법은 조합을 구하고 팀 1,2를 조합해서 최소값을 찾으면 되는 문제인데 백트래킹이 붙어 있어서 아마 안 되겠지 생각하며 해 보았는데 성공. 조합을 생각해 보면 한 팀만 구성하면 나머지 팀이 완성되기 때문에, 그리고 인원이 짝수인 것이 보장되기 때문에 $$n C (n/2) = \frac{n!}{(n/2)!.. 2024. 2. 8.
백준 # 31287번 장난감 강아지 - 파이썬 4 2 URLD YES 3 2 URD NO 시뮬레이션으로는 풀리지 않고 시간 초과가 난다. 생긴 도형의 최종점과 원점의 관계를 통해 그림을 새로 그리지 않고 원점을 최종점(x,y)에 대해 -x, -y 만큼 이동한다고 생각하고 문제를 풀었지만 시간 초과를 도무지 해결할 수가 없었다. 먼저 1회 순회하면서 0,0을 지나는지, 어느 점을 지나는지 기록하고, 최종점을 구한 뒤에 2회 반복부터는 좌표에 대한 함수로 구하려고 했는데.... 안되었다. 망한 코드를 보자. 이거보다 개선된 k회 포지션을 기준으로 하는 코드가 있는데 의미없다. def can_return_to_origin(n, k, text): x, y = 0, 0 positions = set() # 거쳐간 좌표들을 저장할 집합 # 명령어 순회 for t.. 2024. 2. 5.
백준 #1168번 요세푸스 문제 2 와 세그먼트 트리 파이썬 + 11025번 요세푸스 문제 3 백준에서 변형 문제 2개를 제외하면 정통(?) 요세푸스 문제는 아래와 같습니다. 요세푸스 순열을 구하는 문제 마지막 생존자를 구하는 문제 문제 제목 요세푸스 문제 0 11866번 2초/512MB 요세푸스 문제 1158번 2초/256MB 요세푸스 문제 2 1168번 0.15초/128MB 요세푸스 문제3 11025번 1 초/ 16 MB 마지막 요세푸스 문제 1179번 2초 128MB 입력범위 및 부가조건 1 ≤ K ≤ N ≤ 1,000 1 ≤ K ≤ N ≤ 5,000 1 ≤K≤ N≤ 100,000 Java X: 0.8 PythonPyPy: 0.75 Kotlin (JVM): 0.8 1 ≤K≤N≤ 5,000,000 1 ≤ N ≤ 10^15 1 ≤ K ≤ 90 요세푸스 문제 - 위키백과, 우리 모두의 백과사전 위.. 2024. 2. 4.
백준20920🐨영단어 암기는 괴로워.py 문제만들고자 하는 단어장의 단어 순서는 다음과 같은 우선순위를 차례로 적용하여 만들어진다.자주 나오는 단어일수록 앞에 배치한다.해당 단어의 길이가 길수록 앞에 배치한다.알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다+길이가 M이상인 단어들만 외운다고 한다.입력첫째 줄에는 영어 지문에 나오는 단어의 개수 N과 외울 단어의 길이 기준이 되는 M이 공백으로 구분되어 주어진다. $(1≤N≤100000, 1≤M≤10)$둘째 줄부터 N+1번째 줄까지 외울 단어를 입력받는다. 이때의 입력은 알파벳 소문자로만 주어지며 단어의 길이는 10을 넘지 않는다.단어장에 단어가 반드시 1개 이상 존재하는 입력만 주어진다.출력단어장에 들어 있는 단어를 단어장의 앞에 위치한 단어부터 한 줄에 한 단어씩 순서대로 출력한다.예제.. 2024. 2. 2.

티스토리툴바