본문 바로가기
728x90

백준20

백준 11561 - 징검다리( Python ) https://www.acmicpc.net/problem/11561 11561번: 징검다리 각 테스트 케이스마다 한 줄에 승택이가 밟을 수 있는 최대 징검다리 수를 출력한다. www.acmicpc.net 이진탐색 실버 3 레벨의 문제 등차수열로 풀어야한다는 것을 생각하지 못해서 다른 분의 풀이를 참고하여 풀게되었다. - 이전에 점프한 거리보다 1 이상 더 긴 거리를 뛰어야한다 -> 3, 4, 5, 6 과 같은 규칙이 있을 것으로 생각해야됨 3, 5, 9, 15 와 같은 불규칙적인 점프는 도출해낼 수 없음 - 최대의 징검다리 수 -> 점프마다 최소 거리를 뛰어야하므로 1이라 가정하고 규칙을 구할 수 있음 => 즉, 최소 거리를 뛰는 규칙을 찾아야하기 때문에 등차수열을 생각 할 수 있다. 공차를 구하는 것이.. 2023. 3. 14.
백준 9012 - 괄호( Python ) https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 아마 스택 기본 문제이지 않을까 싶다. 예제로도 많이 등장하는 괄호 문제 1차 답안 n = int(input()) for i in range(n): data = input() stack = [] result = 'YES' for i in data: if i == '(': stack.append(i) else: if i == ')' and len(stack) == 0:.. 2023. 3. 6.
백준 1049 - 기타줄( Python ) 1049번: 기타줄 (acmicpc.net) 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 백준 그리디 4실버 문제인데 반례를 생각하지 못해서 결국 도움을 받은 문제.. 아직 반례를 생각하는게 쉽지않다 조금 더 분기를 차근차근 나누는 연습이 필요할 듯 싶다. 처음에는 단순히 튜플로 패키지, 단품 가격 비교만 했는데 조금 더 자세한 비교가 필요했다. 총 4개의 케이스가 있으며 튜플로 비교하는 것보다 패키지 묶음, 단품 묶음으로 비교하는 것이 생각하는 것이 편하다 1. 6개 이하인 경우 낱개 가격만 비교 2.. 2023. 2. 22.
백준 16401 - 과자 나눠주기( Python ) https://www.acmicpc.net/problem/16401 16401번: 과자 나눠주기 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1, www.acmicpc.net 이진탐색으로 풀이가 가능한 파라메트릭 서치형식의 문제이다. 이진탐색으로 풀이를 생각하는 것은 어렵지 않았던 반면 과자하나를 어떻게 여러번 잘라야하나라는 생각이 쉽게 들지 않앗다. 나누기를 이용하면 되는 간단한 수준이였음에도 불구하고 아직 풀이 방향성을 잡는데 시간이 오래 걸린다. 풀이는 매우 간단하다 m,n = .. 2023. 2. 16.
백준 24444 - 너비 우선 탐색 1( Python) - BFS https://www.acmicpc.net/problem/24444 24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방 www.acmicpc.net 너비 우선 탐색은 queue 자료구조를 사용해서 풀 수 있다. 기본예제와 차이점 정리 1. 양방향간선이므로 그래프를 뒤집어서 한 번 더 저장해야됨 2. 오름차순으로 방문해야하므로 큐에서 꺼낸 노드의 그래프를 순회하기전에 해당 그래프를 정렬해주어야한다. 3. 방문한 순서대로 출력을 해야하는 것이 아닌 해당 노드의 방문 순서를.. 2023. 1. 18.
백준 1012 - 유기농 배추( Python ) - DFS https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net dfs...bfs....어렵다 어려워 알고리즘 오픈 카톡방에 물어보니 24444, 1012, 7569문제로 기본을 쌓아보라는 추천받아서 주말동안 풀긴 풀었다 한문제당 한시간은 안걸린게 다행이였을까~? 여튼 이제는 조금 아주 조금은 감이 잡히는 것 같다 recursionError 가 발생해서 재귀깊이 제한해주는 코드를 추가해야 통과 할 수 있다. 이외에는 이코테에서 학습한 DFS코드와 동일하게 풀 수 있었다. .. 2023. 1. 16.
728x90
반응형

티스토리툴바