본문 바로가기
반응형

파이썬87

[백준 24552] 올바른 괄호 올바른 괄호(24552)문제 출처 : https://www.acmicpc.net/problem/24552 이 문제를 처음 보았을 때 스택을 이용하여 문제를 해결한다고 생각했습니다. 보통 괄호 문제는 스택에 넣어가며 문제를 해결하기가 쉽기 때문 입니다. 아직 괄호 문제를 풀어본 경험이 없다면 먼저 아래 문제부터 해결해 보시기 바랍니다.https://davincicoding.tistory.com/189 [백준 9012] 괄호괄호(9012)문제 출처 : https://www.acmicpc.net/problem/9012 이 문제는 다빈치코딩 알고리즘에서 이미 스택으로 풀어본 문제 입니다. 이전 스택 풀이는 아래 링크를 확인 바랍니다.https://wikidocs.net/215110 06.davincicoding.. 2024. 11. 27.
[백준 2504] 괄호의 값 괄호의 값(2504)이 문제는 2008년 정보 올림피아드 지역 본선 초등부 4번, 중등부 2번 문제 입니다.문제 이해하기괄호 관련 문제가 보인다면 먼저 스택이 아닌가 생각해 보아야 합니다. 괄호 관련 문제는 스택의 특성을 이용해서 해결하는 경우가 많기 때문 입니다. 괄호 문제를 푸는 방법에 대해서는 아래 링크에서 소개 했었습니다. 아래 링크를 통해 괄호 문제를 어떻게 바라봐야 하는지 확인 바랍니다.https://davincicoding.tistory.com/189 [백준 9012] 괄호괄호(9012)문제 출처 : https://www.acmicpc.net/problem/9012 이 문제는 다빈치코딩 알고리즘에서 이미 스택으로 풀어본 문제 입니다. 이전 스택 풀이는 아래 링크를 확인 바랍니다.https:/.. 2024. 11. 26.
[백준 22341] 사각형 면적 사각형 면적(22341)문제 출처 : https://www.acmicpc.net/problem/22341 이 문제는 2021년 정보올림피아드 2차 대회 초등부 1번 문제 입니다. 종이에 점이 주어졌을 때 가로나 세로로 잘라 더 큰 면적을 남겨나가며 최종적으로 얻게 되는 면적을 구하는 문제 입니다. 규칙에 맞게만 수행한다면 어려운 점 없이 문제를 해결할 수 있습니다. 간단한 문제이기 때문에 코드를 작성해 나가며 문제를 해결해 보겠습니다.코드 작성코드를 작성해보겠습니다.입력 받기N, C = map(int, input().split())A, B = N, Nfor _ in range(C): X, Y = map(int, input().split()) A, B = get_area(A, B, X, Y)pr.. 2024. 11. 25.
[백준 9012] 괄호 괄호(9012)문제 출처 : https://www.acmicpc.net/problem/9012 이 문제는 다빈치코딩 알고리즘에서 이미 스택으로 풀어본 문제 입니다. 이전 스택 풀이는 아래 링크를 확인 바랍니다.https://wikidocs.net/215110 06. 괄호[백준 9012]문제 출처 : [괄호](https://www.acmicpc.net/problem/9012) 괄호의 쌍을 찾는 문제는 대표적인 스택 문제라 할 수 있습니다. “(” 가 입력 되었…wikidocs.net 그럼에도 다시 이 문제를 풀이하는 이유는 스택 말고도 다른 풀이 방법이 여러가지가 있기 때문 입니다. 괄호를 사용한 문제는 여러가지가 있기 때문에 다른 풀이 방법도 익숙해져야 그 문제에 맞는 풀이법을 사용할 수 있기 때문 입니.. 2024. 11. 24.
[백준 18222] 투에-모스 문자열 투에-모스 문자열(18222)문제 출처 : https://www.acmicpc.net/problem/18222 k를 입력 받아 그 값이 0인지, 1인지를 찾는 문제 입니다. 재귀로 풀 수 있는 문제로 재귀를 이제 막 배웠다면 조금 어려울 수 있습니다.문제 이해하기문자열 x는 10 ** 18 이라는 엄청난 크기를 가지고 있습니다. 따라서 하나 하나 계산 해서는 답을 구할 수 없습니다. 문자열 x는 두 배씩 커지면서 매 번 값이 반전된다는 것을 이용하면 문제를 좀 더 쉽게 해결 할 수 있습니다.문제를 이해하기 위해 x를 만들어 보겠습니다. 처음 x는 0 입니다.0이제 x를 반전해서 이어 붙여 줍니다.0 1다음 역시 x를 반전해서 이어 붙여 줍니다.0 1 1 0이것의 길이를 두 배씩 늘려주면 다음과 같습니다0.. 2024. 11. 23.
[백준 20188] 등산 마니아 등산 마니아(20188)문제 출처 : https://www.acmicpc.net/problem/20188 이 문제는 2020년 정보올림피아드 2차 대회 초등부 3번, 중등부 2번 문제 입니다.문제 이해하기한 번만 읽어서는 잘 이해하기 힘든 문제 입니다. 특히나 다양성이라는 용어가 중요한데 이 말의 뜻이 어렵습니다.다양성은 길에 포함된 오솔길의 개수로 정의된다.이렇게 정의 되어 있습니다. 문제를 제대로 읽지 않으면 다양한 경로의 개수로 잘못 이해하기 쉽습니다. 문제를 잘 읽어보면 이 문제에서 원하는 다양성은 두 지점을 지나는 간선의 개수 입니다. 이 간선의 개수는 최단 경로를 뜻하는 것이 아니라 정상 즉 루트를 지나는 경로입니다.위와 같이 6, 7을 연결하는 다양성은 루트 부터 각 번호까지 간선의 개수 3.. 2024. 11. 22.
[백준 21760] 야구 시즌 야구 시즌 (21760)문제 출처 : https://www.acmicpc.net/problem/21760 이 문제는 2021년 정보올림피아드 1차 고등부 1번 문제 입니다.N개의 리그가 존재하고, 각 리그에는 M개의 팀이 있습니다. 모든 리그에 팀은 M개로 정해져 있는지 리그 전체의 팀은 N * M 개 입니다.같은 리그에서는 같은 리그에 있는 다른 팀과 각각 A번 씩 경기를 해야 합니다. 그리고 다른 지역과는 B번 씩 경기를 해야 합니다. A와 B는 다음과 같은 관계를 가집니다.A = k * B판데믹의 영향으로 경기의 수를 D번으로 제한 하게 되었고, A, B 값을 조절해야 합니다. 하지만 모든 팀들은 한 번 이상 경기를 진행해야 합니다. 즉 A, B는 1 이상 입니다.문제 이해하기N, M, k, D가 .. 2024. 11. 21.
[백준 17623] 괄호 괄호(17623)문제 출처 : https://www.acmicpc.net/problem/17623 이 문제는 2019년 정보올림피아드 2차 고등부 2번 문제 입니다. 괄호 문제들이 심심치 않게 출제되고 있기 때문에 어떻게 푸는지 감을 잡고 있어야 합니다. 이 문제는 특히나 생각할 부분이 많이 있습니다. 단순히 괄호만 계산하면 되는 것이 아니라 괄호 문자열을 숫자로 변경해서 가장 숫자가 낮은 형태로 저장해야 합니다.괄호 문자열을 만드는 것은 DP로 해결이 가능해 보입니다. 그리고 dmap값을 통해 숫자로 변경하는 부분은 복잡하기는 하지만 그리 어려운 부분은 아닙니다.문제 이해하기X 찾기올바른 문자열을 만드는 방법을 생각해 보겠습니다. solve(N)이라는 함수를 만들어 문자열 X를 찾는 것입니다. N값에 .. 2024. 11. 20.
[백준 20186] 수 고르기 수 고르기(20186)문제 출처 : https://www.acmicpc.net/problem/20186 이 문제는 2020년 정보올림피아드 2차 대회 초등부 1번 문제 입니다.문제 이해하기문제를 읽어보면 상당히 복잡해 보입니다. 하지만 조금만 잘 생각해보면 규칙을 쉽게 찾을 수 있습니다.2 3 1 2 1, K = 3문제의 예제처럼 위와 같이 숫자가 있고 3개의 숫자를 선택해야 합니다. 그리고 점수는 자신의 왼쪽에 있는 선택된 수 입니다. 3개의 숫자를 어떻게 고를지 모르겠지만 K값이 3이기 때문에 숫자 3개를 골라야 합니다. 이 숫자들을 a, b, c라고 하겠습니다. a, b, c의 점수는 각각 a - 0, b - 1, c - 2 입니다. 이 숫자들의 합은 a + b + c - 0 - 1 - 2로 나타낼.. 2024. 11. 19.
[백준 2447] 별 찍기 - 10 별 찍기 - 10 (2447)문제 출처 : https://www.acmicpc.net/problem/2447 반복문에 대해 처음 배웠을 때 시작하는 것이 별 찍기 입니다. 아직 별 찍기가 무엇인지 잘 모른다면 아래 링크를 통해 별 찍기가 무엇인지 알아보기 바랍니다.https://wikidocs.net/192041 03. 별 찍기# 별 찍기 별 찍기는 반복문을 제대로 익히기에 아주 좋은 방법입니다. 숫자를 입력받고, 해당 숫자에 맞게 별이 찍히는 프로그램을 작성하는 것입니다. 가령 5를 입력하면 첫 번…wikidocs.net 백준에는 다양한 별 찍기 문제가 있으니 아직 별 찍기 이전 문제들을 풀어보지 못했다면 풀어보시기 바랍니다. 아래 링크를 들어가면 여러 가지 형태의 별 찍기 문제를 볼 수 있습니다.ht.. 2024. 11. 18.
[백준 2812] 크게 만들기 크게 만들기(2812)문제 출처 : https://www.acmicpc.net/problem/2812N자리의 숫자에서 K개의 숫자를 지워 가장 큰 숫자를 만드는 문제 입니다.문제 이해하기문제를 잘 생각 해보면 뒤의 숫자가 앞의 숫자보다 크다면 앞의 숫자를 지워주면서 가장 큰 숫자를 찾아나가야 합니다.숫자를 한 자리씩 탐색 시작현재 숫자가 앞의 숫자보다 크고, 지워야할 숫자가 남아 있다면 앞의 숫자를 제거스택을 이용해서 숫자를 만들어 나가면 된다는 것을 느꼈다면 반은 성공한 것입니다.예제 만들어 보기예제에 있는 1924를 예를 들어보겠습니다. 1924에서 2개의 숫자를 빼서 가장 큰 숫자를 만들어야 합니다.1924 탐색 시작첫번째 숫자 1 탐색.만든 숫자 : 1, K : 29 탐색. 1보다 크고, K가 남.. 2024. 11. 17.
[백준 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.
[백준 17616] 등수 찾기 문제 출처 : https://www.acmicpc.net/problem/17616 이 문제는 2019년 정보 올림피아드 초등부 2차 3번 문제 입니다. 문제 이해하기두 학생중 누가 더 잘했느냐를 종합하여 특정 학생 X의 등수 범위를 파악해야하는 문제 입니다.문제의 예제 입력3번을 보겠습니다. 5 5 11 32 33 43 54 5 해당 입력을 그림으로 표현하면 아래와 같습니다.1, 2번을 제외한 3, 4, 5번의 등수는 확실하게 알 수 있습니다. 하지만 1번이 1등인지 2번이 1등인지 알 수 없습니다. 따라서 1번의 범위는 최대 1등, 최소 2등이 됩니다.보통 DFS, BFS 문제를 풀 때 방향성을 고려하지 않는 양방향으로 구현하지만 이 문제에서는 단방향으로 해야 합니다. 단방향으로 자신보다 높은 성적을 .. 2024. 11. 3.
[백준 20187] 종이접기 2020년 정보 올림피아드 2차 대회에서 초등부 2번, 중등부 1번 문제였던 종이접기, 백준 온라인 저지에서 20187번을 풀어 보도록 하겠습니다.문제 출처 : https://www.acmicpc.net/problem/20187문제 이해하기어릴적에 종이를 얼마나 접을 수 있을지 꼬깃꼬깃 접었던 기억이 있습니다. 그렇게 종이를 접고 접다보면 최종적으로 1 X 1 크기의 정사각형이 됩니다. 여기에 4등분 하여 하나의 위치에 구멍을 뚫고 접었던 반대로 풀기 시작하면서 구멍이 뚫린 위치를 출력해주면 됩니다.마지막 1 X 1 정사각형의 위치는 어떻게 잡으면 될까요? 규칙적으로 접고 접었다가 다시 펼치는 알고리즘을 생각해보면 분할 정복으로 문제를 해결할 수 있습니다. 전체크기를 하나하나 줄여 나가다보면 제일 마지막.. 2024. 10. 15.
[백준 32069] 가로등 이 문제는 2024년 정보올림피아드 2차 대회 초등부 2번, 중등부 1번, 고등부 1번으로 출제된 문제 입니다. 문제 출처 : https://www.acmicpc.net/problem/32069 가로등이 있는 위치의 어두운 정도를 0으로 하고 거리가 1씩 늘어날 때마다 어두운 정도가 1씩 늘어납니다. 이렇게 모든 위치의 어두운 정도를 구한 다음 K 번째 까지의 어두운 정도를 출력하면 됩니다.가로등의 위치에서 1씩 멀어질 때마다 어두운 정도 1을 더해주어 각 위치의 어두운 정도를 구하면 됩니다. 이렇게 거리가 1씩 늘어날 때마다 1을 더해주는 형태의 문제는 BFS로 쉽게 해결할 수 있습니다. 하지만 문제가 BFS 형태가 아닌것 같다는 것이 문제가 됩니다. 가장 큰 문제는 숫자의 범위라 할 수 있는 L의 크.. 2024. 10. 3.
[백준 5676] 음주 코딩 문제 출처 : https://www.acmicpc.net/problem/5676 세그먼트 트리에 대한 이해가 필요한 문제 입니다. 기본적인 세그먼트 트리에 대해 아직 잘 모른다면 아래 링크를 통해 확인하시기 바랍니다.https://wikidocs.net/209446 06. 세그먼트 트리세그먼트 트리(Segment Tree)는 구간의 합, 구간의 최솟값, 구간의 최댓값등을 빠르게 구할 때 사용합니다. 앞에서 배웠던 누적합과 비슷하다고 느낄 수 있지만 누적합은 합…wikidocs.net 문제 이해하기제목은 음주 코딩이지만 음주와는 전혀 관련 없는 문제 입니다. 주어진 수열이 있고 이 수열의 수들을 곱했을 때 양수가 될지, 음수가 될지, 0이 될지만 확인하면 됩니다.다만 숫자가 너무 커질 것을 대비해서 직접 .. 2024. 6. 15.
[백준 28432] 끝말잇기 문제 출처 : https://www.acmicpc.net/problem/28432 문제 이해하기끝말잇기를 하기 위해서 앞의 단어의 마지막 글자와 다음 단어의 첫 번째 글자를 알아야 합니다. 그리고 그 문자가 끝말잇기 리스트에 포함되서는 안됩니다. 여기서 또 한가지 문제는 ?가 맨 처음에 위치할 수도 있고, 마지막에 위치할 수도 있다는 것입니다. 따라서 처음과 마지막일 경우의 처리도 생각하면서 문제를 해결해야 합니다. 우리가 고려해야할 사항을 적어보았습니다.?가 처음에 위치할 경우?가 마지막에 위치할 경우문자중에 ?가 있는지 확인위 세 가지를 고려해서 문제를 해결해 보겠습니다.코드 작성그럼 코드를 작성해 보겠습니다.입력 받기N = int(input())S = []idx = 0for i in range(N).. 2024. 6. 8.
[백준 30106] 현이의 로봇 청소기 문제 출처 : https://www.acmicpc.net/problem/30106 DFS나 BFS를 활용하여 풀 수 있는 플러드 필 문제 입니다. 하지만 DFS로 풀었을 때에는 시간초과가 발생했습니다. 같은 로직의 BFS로는 시간초과 없이 통과 되었습니다. 파이썬으로 문제를 풀 때에는 DFS보다는 BFS로 문제를 해결하는 습관을 들이는 것이 좋을 것 같습니다.문제 이해하기이 문제가 다른 플러드 필 문제와 다른 점은 연결이 되어있지 않아 여러 구역으로 나누어지는 것이 아니라 높이로 인해 건너갈 수 없어 여러 구역으로 나누어진다는 사실 입니다. 따라서 높이의 차를 통해 연결 여부를 따져야 합니다.코드 작성하기그럼 코드를 작성해 보겠습니다.입력 받기mii = lambda : map(int, input().sp.. 2024. 5. 7.
[백준 2776] 암기왕 문제 출처 : https://www.acmicpc.net/problem/2776 수첩 1에 있는 정수가 수첩 2에 있으면 1을, 없으면 0을 출력하는 문제 입니다.문제 이해하기수첩 1의 순서가 중요한 것이 아니기 때문에 수첩 1을 정렬한 다음, 수첩 2의 숫자로 이분탐색을 하여 결과를 출력하면 됩니다.이 방법보다 더 쉬운 방법은 수첩 1을 set 자료구조로 저장하여 찾는 것입니다. 간단한 문제이기 때문에 이분 탐색, set 두 가지 방법 모두 해보겠습니다.코드작성이분 탐색의 입력부터 알아보겠습니다.입력 받기mii = lambda : map(int, input().split())T = int(input())for _ in range(T): N = int(input()) arr = list(mii.. 2024. 5. 3.
[백준 2295] 세 수의 합 문제 출처 : https://www.acmicpc.net/problem/2295 집합에 포함된 세 수를 더한 결과가 집합 내에 있는 가장 큰 수가 되는 경우를 찾는 문제 입니다. 세 수 x, y, z와 그 결과로 가장 큰 수 k를 찾아야 합니다. 이 때 꼭 기억해야 하는 부분은 x, y, z, k의 값이 서로 같아도 된다는 부분 입니다. 저는 세 수가 같을수는 없다고 생각하고 아무리 풀어도 틀리다고 나와 문제를 다시 제대로 읽어보니 숫자가 중복되어도 상관 없다는 부분을 찾을 수 있었습니다. 저와 같은 실수를 하지 마시기 바랍니다.아이디어세 개의 수를 더하기 때문에 시간복잡도가 높을 것으로 생각이 듭니다. 하지만 조금만 더 생각해보면 시간복잡도를 줄일 수 있는 아이디어가 있습니다. 우리가 구해야 하는 공식.. 2024. 5. 2.
[백준 2512] 예산 문제 출처 : https://www.acmicpc.net/problem/2512 렌선 자르기 문제와 비슷한 느낌이 드는 문제 입니다. 다빈치코딩 알고리즘에 넣기에는 중복적인 내용이라 블로그에 추가하였습니다.문제 이해하기예산이 낮은곳은 그대로 두고, 예산이 높은곳만 줄여나가며 총액보다 작게 만드는 문제 입니다.이 문제는 일반적인 이분 탐색 문제와 다른점이 있습니다. 바로 예산을 증액할 필요는 없다는 것입니다. 예산의 총액이 신청한 예산보다 크다면 더이상 예산을 늘릴 필요 없이 최대값을 출력하면 됩니다. 이 부분만 주의하면 문제를 해결할 수 있습니다.코드 작성그럼 코드를 작성하며 문제를 해결해 보겠습니다.입력 받기N = int(input())arr = list(map(int, input().split())).. 2024. 5. 1.
[백준 18185] 라면 사기 (Small) 문제 출처 : https://www.acmicpc.net/problem/18185문제 이해하기라면을 최대한 싸게 사면 되는 문제 입니다. 1개를 살 때에는 3원, 2개를 살 때에는 5원, 3개를 살 때에는 7원을 주고 사야 합니다. 최대한 많이 사는 것이 이득이기 때문에 그리디로 문제를 해결할 수 있습니다.하지만 그리디 문제는 반례를 찾기가 힘듭니다. 반례를 잘 찾아 문제를 해결해야 합니다. 반례는 3개를 살펴볼 때 나오는 것이 아니라 4개 이상일 때 발생 합니다. 라면이 위와 같이 있다고 하겠습니다. 그리디 알고리즘으로 한꺼번에 많이 사는것이 이득이기 때문에 처음에 3개를 사보겠습니다.3개를 한꺼번에 샀기 때문에 3 * 7 로 21의 돈이 들었습니다. 그리고 2번째 2개, 4번째 3개가 남았습니다. 각.. 2024. 4. 29.
반응형

티스토리툴바