반응형 오블완10 [백준 25400] 제자리 제자리(25400)문제 출처 : https://www.acmicpc.net/problem/25400 이 문제는 2022년 정보 올림피아드 2차 초등부 1번 문제 입니다.문제 이해하기제자리 상태가 된다는 것은 최종적으로는 1, 2, 3, … 순으로 남아있어야 한다는 뜻입니다. 만약 아래와 같은 숫자들이 있습니다. 5, 4, 3, 2, 1 이숫자들을 제자리 상태로 만든다는 것은 1 하나만 남기는 것입니다. 왜냐하면 어떤 숫자를 빼도 오름차순으로 정렬할 수 없기 때문 입니다. 만약 숫자들 중에 1이 존재하지 않는다면 제자리 상태를 만들 수 없고 결국 모든 카드를 제거해야 합니다. 결국 이 문제를 해결하기 위해서는 제일 먼저 1을 찾고, 다음은 2를 찾고, 또 3을 찾아 순서대로 정렬하고 정렬이 되지 않는 카드.. 2024. 11. 16. [백준 11437] LCA (재풀이) LCA 다시 풀기 (11437)문제 출처 : https://www.acmicpc.net/problem/11437 사실 이 문제는 예전에 해결 했던 문제 입니다. 다만 체점이 다시 되면서 맞았던 내용이 틀렸다고 나와 다시 풀게 되었습니다. 이 전 풀이는 아래 링크를 확인 바랍니다.https://davincicoding.tistory.com/36 [백준 11437] LCA문제 출처 : https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알davincicoding.co.kr 그럼 왜 틀렸는지와 그것을 해결한 방법을 알아보겠습니다. .. 2024. 11. 15. [백준 9655] 돌 게임 돌 게임(9655)문제 출처 : https://www.acmicpc.net/problem/9655 돌 게임은 다양한 방식으로 출제되고 있는 유명한 문제 입니다. 다양한 돌 게임중 가장 쉬운 형태의 문제 입니다.우리는 돌을 1개 혹은 3개를 가져갈 수 있습니다. 2개를 가져갈 수 있는 것이 아니라는 점을 기억해야 합니다. 이 때 두 사람은 최선을 다해 게임이 임합니다. 즉 자신이 지는 방향으로는 가지 않는다는 뜻입니다.문제 이해하기N개의 돌이 남았을 때 현재 상근이가 게임을 진행하면 누가 이길지를 출력하는 것이 우리가 만들 함수 입니다. 상근이의 차례에 돌이 1개 혹은 3개 남아있다면 무조건 상근이가 이깁니다. 반대로 2개 혹은 4개가 남아 있다면 무조건 창영이가 이기게 됩니다. 그럼 아래와 같은 함수를 .. 2024. 11. 14. [백준 32068] 보물 찾기 문제 출처 : https://www.acmicpc.net/problem/32068보물 찾기(32068)이 문제는 2024 정보올림피아드 2차 초등부 1번 문제 입니다.문제 이해하기S를 중심으로 양쪽으로 한 칸씩 이동하면서 어느쪽 물건을 먼저 찾는지 확인하는 것이 문제입니다. 어렵게 왔다 갔다 하면서 시뮬레이션해야 하는 것 처럼 보이지만 사실 양쪽의 거리만 알면 수학적으로 쉽게 해결 가능합니다.그래도 일단은 문제에서 요구하는대로 풀어보고, 다음으로 수학적으로 풀어보겠습니다.코드 작성하기그럼 코드를 작성해 보겠습니다.입력 받기T = int(input())for _ in range(T): L, R, S = map(int, input().split()) print(solve(L, R, S))먼저 테스.. 2024. 11. 13. [백준 31964] 반품 회수 반품 회수(31964)문제 출처 : https://www.acmicpc.net/problem/31964 이 문제는 2024년 정보 올림피아드 초등부 3번, 고등부 1번 문제 입니다.문제 이해하기N개의 집을 방문해서 반품을 회수하는데 걸리는 최소 시간을 구하는 문제 입니다. 각 집마다 물건을 내놓는 시간이 다르기 때문에 그 시간에 맞춰 잘 회수해야 합니다. 이 때 내놓은 물건을 빠르게 회수하는 것이 목적이 아니라 다시 택배 물건을 회수해서 빠르게 돌아오는 시간을 구해야 한다는 것이 핵심 입니다. 즉 물건을 언제 회수 하느냐는 문제가 아닙니다.우리가 알 수 있는 것은 물건을 시각 0에 모두 내어 놓아도 택배 트럭이 왔다 갔다 하는 시간만큼은 줄일 수 없습니다. N개의 집이 있기 때문에 N번 집까지 가는데 시.. 2024. 11. 12. [백준 2631] 줄 세우기 문제 출처 : https://www.acmicpc.net/problem/2631 이 문제는 2001년 정보 올림피아드 중등부 2번 문제 입니다. 처음에는 정렬 문제라 생각했습니다. 제목도 정렬과 관련 있는 줄 세우기고, 아이들을 원하는 위치에 넣어 정렬의 횟수를 구하면 되는 문제인가 생각했습니다. 하지만 막상 이렇게 풀려고 하니 최소 횟수를 구해야 한다는 부분에서 막혔습니다.문제 이해하기최소 횟수를 구하는 것이 포인트이기 때문에 이것을 반대로 생각했습니다. 이동해야 하는 아이들을 생각하지 않고 이동하지 않는 아이들을 생각해 보았습니다. 이런 문제를 풀 때 반대로 생각하는 것이 더 쉬운 방향일 수 있기 때문에 한번쯤은 고려해 봐야 합니다. 가만히 있는 아이들을 생각해보니 이미 정렬되어 있는 아이들이 움직이.. 2024. 11. 11. [백준 2193] 이친수 이친수(2193)문제 출처 : https://www.acmicpc.net/problem/2193 0과 1로 이루어진 이진수 중 특별한 성질을 가지고 있는 이친수를 찾는 문제 입니다. 이친수의 성질은 다음과 같이 두 가지 입니다.이친수는 1로 시작합니다.이친수는 1이 연속해서 나타나지 않습니다.이 두 가지 성질을 만족하는 이친수의 개수를 찾는 것 입니다.문제를 보면 DP의 Top-Down으로 문제를 해결할 수 있을것 같습니다. 함수를 만들고 그 함수의 특징을 다음과 같이 정의 하였습니다.solve(n, c)n은 이친수의 길이 입니다. 그리고 c는 마지막 숫자를 나타냅니다. 즉 0 아니면 1이 됩니다. 그리고 이 함수의 리턴값은 길이가 n까지이고 마지막 숫자가 c인 이친수의 경우의 수 입니다.코드 작성하기그.. 2024. 11. 10. [백준 3745] 오름세 문제 출처 : https://www.acmicpc.net/problem/3745 주식의 오름세를 찾는 문제 입니다. 점점 커지는 형태의 부분 수열을 찾는 문제로 LIS를 찾는 문제와 같습니다. LIS 라는 것만 알고 있다면 알고리즘을 이용하여 쉽게 문제를 해결 할 수 있습니다.코드 작성다른 함정이 없어 보이기 때문에 바로 문제를 해결해 보겠습니다. LIS를 해결할 때 속도도 빠르고 모듈을 사용하여 오류도 없을만한 이분탐색 bisect를 사용하겠습니다.입력 받기while True: try: N = int(input()) arr = map(int, input().split() except: break이 문제는 테스트 케이스의 개수가 존재하지 않습니다. 따라서 .. 2024. 11. 9. [백준 11057] 오르막 수 문제 출처 : https://www.acmicpc.net/problem/11057 간단한 DP 문제 입니다. 점화식이 바로 떠오른다면 문제 없지만 보통 점화식을 바로 떠올릴 수 없습니다. 그런 경우 Top-Down으로 먼저 문제를 해결하고 이를 Bottom-Up으로 바꾸는 것이 좋습니다.아직 Top-Down, Bottom-Up이 무엇인지 잘 모르겠다면 아래 링크를 통해 확인해 보시기 바랍니다.https://wikidocs.net/206429 09. 동적 계획법(다이나믹 프로그래밍)동적 계획법이라 불리는 DP(dynamic programming) 는 큰 문제를 작은 문제로 쪼개어 나가면서 문제를 해결하는 기법 입니다. DP에는 크게 두 가지 방법이 많이 사…wikidocs.net 문제 이해하기Top-Dow.. 2024. 11. 8. [백준 2624] 동전 바꿔주기 문제 출처 : https://www.acmicpc.net/problem/2624 이 문제는 2002년 정보 올림피아드 중등부 2번 문제 입니다. 다빈치코딩 알고리즘 책에서 동전 문제들은 많이 다루었습니다.[백준 2091] 동전 : https://wikidocs.net/265710 06. 동전 [백준 2091][TOC] # 동전(2091) 문제 출처 : [동전](https://www.acmicpc.net/problem/2091) 지금까지 동전0, 동전2, 동전1 순으로 동전 문제를 …wikidocs.net문제 이해하기동전 문제들을 통해서 다양한 문제풀이 방법을 배웠습니다. 동전1(2293) 문제에서 경우의 수를 구하는 방법을 배웠고, 동전(2091) 문제에서 동전의 개수가 정해져 있는 문제를 풀어보았습니다.. 2024. 11. 7. 이전 1 다음 반응형
