본문 바로가기

알고리즘/백준 문제 풀이

 (338)
[Python] 1246번 온라인 판매 https://www.acmicpc.net/problem/1246 1246번: 온라인 판매 첫째 줄에 정수 N(1 ≤ N ≤ 1,000)과 M(1 ≤ M ≤ 1,000)이 입력된다. 둘째 줄부터 M+1번째 줄까지 i+1번째 줄에는 Pi(1 ≤ Pi ≤ 1,000,000)가 입력된다. www.acmicpc.net 22/09/10 연습에서 풀었던 문제로, 문제 읽는 게 조금 시간이 걸렸던 문제이다. 이런 문제가 실전에서 나온다면 당황했을 것이다... 문제 접근 방식: 경래가 수익을 최대로 올리고 싶다고 했고, 한 고객에게 1개만 달걀을 팔기로 했다. 각 고객들이 제시한 최대 지불 금액 P가 리스트로 주어지고, 이 금액을 넘지 않는 선에서 고객들은 금액을 낼 수 있다고 했다. 또한, 달걀은 최대 M명까지만 살..
[Python] 25371번 k진수 정수의 자릿수 나누기 25371번: k진수 정수의 자릿수 나누기 (acmicpc.net) 25371번: k진수 정수의 자릿수 나누기 양의 정수 n과 k가 주어진다. n을 k진수로 변환한 수를 a라고 하자. a의 각 자릿수를 0을 기준으로 나눈 결과를 집합 b라고 하자. 0이 연속으로 나와서 공백이 생기는 경우는 집합 b에 포함되지 않는 www.acmicpc.net 22/09/09 정직한 제목, 정직한 문제이다. 제목과 걸맞게 잘 구현하면 되는 문제이다. 문제 접근 방식: 10진법으로 입력받은 숫자를 k진법으로 변환시켜주는 함수를 정의했다. 이 함수는 너무나도 잘 알려져 있고, 진법에 관한 지식이 있다면 충분히 구성할 수 있기 때문에 설명하지 않겠다. 그냥 그 함수와 파이썬의 sum함수, 그리고 '0'을 기준으로 분리하는 sp..
[Python] 2669번 직사각형 네개의 합집합의 면적 구하기 2669번: 직사각형 네개의 합집합의 면적 구하기 (acmicpc.net) 2669번: 직사각형 네개의 합집합의 면적 구하기 입력은 네 줄이며, 각 줄은 직사각형의 위치를 나타내는 네 개의 정수로 주어진다. 첫 번째와 두 번째의 정수는 사각형의 왼쪽 아래 꼭짓점의 x좌표, y좌표이고 세 번째와 네 번째의 정수는 사각 www.acmicpc.net 22/09/08 이 문제 또한 브론즈 문제 치고는 독특한 아이디어를 가지고 있다. 얼핏 봐서는 기하학 문제처럼 보이지만, 그렇게 풀면 정말 어렵고, 직접 그림을 그림으로써 해결하는 문제이다. 문제 접근 방식: 그냥 직접 그림을 스케치북에 그리듯이 그림으로써 해결한다. 좌표를 2차원좌표로 받고 거기에 해당하는 곳을 모두 1로 바꿔주면 구현 끝! 어렵게 생각하면 오히..
[Python] 1236번 성 지키기 1236번: 성 지키기 (acmicpc.net) 1236번: 성 지키기 첫째 줄에 성의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 성의 상태가 주어진다. 성의 상태는 .은 빈칸, X는 경비원이 있는 칸이다 www.acmicpc.net 22/09/08 그룹 채점 현황에서 무작위로 골라서 푼 문제로, 의외로 브론즈 문제 치고는 재미있는 아이디어를 가진 문제 같아서 흥미로웠다. 문제 접근 방식: 'X'표시가 되어있는 곳은 이미 경비원이 지키고 있는 줄이라는 뜻이다. 나는 성의 모습을 입력받고, 각 줄에 경비원이 있는지 확인하는 row_check, col_check 리스트를 1로 초기화하며 선언해주었다. 성의 모습을 확인하며, 만약 경비원이..
[Python] 11659번 구간 합 구하기 4 11659번: 구간 합 구하기 4 (acmicpc.net) 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 22/09/08 누적 합 알고리즘을 사용하여 해결할 수 있는 전형적인 문제로, 만약 이 문제를 해결하고 싶다면 누적 합 알고리즘에 관해서 조금 알아두는 것이 편할 것이다. 문제 접근 방식: 그냥 누적 합 알고리즘을 그대로 구현한 것이다. 누적 합 알고리즘은 위와 같은 상황처럼 부분 합을 구하는데 그 쿼리의 양이 감당할 수 없을 정도로 많을 때, 이를 쉽게 구하고자 고안된 알고리즘으로..
[Python] 1711번 직각삼각형 1711번: 직각삼각형 (acmicpc.net) 1711번: 직각삼각형 첫째 줄에 점의 개수 N(3 ≤ N ≤ 1,500)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 좌표값은 절댓값이 1,000,000,000을 넘지 않는 정수이며, 주 www.acmicpc.net 22/09/08 그룹 연습에서 풀다가 실패했던 문제로, 다시 풀어서 맞았습니다! 를 받은 문제이다. 단순한 브루트 포스이지만, 맞왜틀을 많이 당한 문제로, 지금 다시 보니 for문과 combinations의 차이점을 느낄 수 있었던 문제였던 것 같다. 문제 접근 방식: 단순 무식하게 그냥 세 점을 잡아서, 세 점의 길이 중 가장 긴 변의 제곱이 나머지 두 변의 길이의 제곱의 합과 같은지..
[Python] 15645번 내려가기 2 15645번: 내려가기 2 (acmicpc.net) 15645번: 내려가기 2 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 22/09/07 이전에 북마크 해놓았던 문제 중 하나로, 무난하게 풀 수 있었던 dp문제였다. 이전에 비슷한 문제를 풀어서 쉽게 풀 수 있었다. 문제 접근 방식: 사실 dp류의 문제는 아이디어만 알면 구현하는 것 자체는 그렇게 어렵지 않은 문제가 꽤 많다. 이것도 그러한데, 아이디어는 다음과 같다. 각각의 dp리스트를 정의해주었다. 총 6개가 존재하는데, 예를 들면 다음과 같다. first_line_min[N]은 내가 ..
[Python] 4470번 줄번호 / 23803번 골뱅이 찍기 - ㄴ / 23804번 골뱅이 찍기 - ㄷ 4470번: 줄번호 (acmicpc.net) 4470번: 줄번호 텍스트에서 줄을 입력받은 뒤, 줄 번호를 출력하는 프로그램을 작성하시오. www.acmicpc.net 23803번: 골뱅이 찍기 - ㄴ (acmicpc.net) 23803번: 골뱅이 찍기 - ㄴ 서준이는 아빠로부터 골뱅이가 들어 있는 상자를 생일 선물로 받았다. 상자 안에는 ㄴ자 모양의 골뱅이가 들어있다. ㄴ자 모양은 가로 및 세로로 각각 5개의 셀로 구성되어 있다. 상자에는 정사 www.acmicpc.net 23804번: 골뱅이 찍기 - ㄷ (acmicpc.net) 23804번: 골뱅이 찍기 - ㄷ 서준이는 아빠로부터 골뱅이가 들어 있는 상자를 생일 선물로 받았다. 상자 안에는 ㄷ자 모양의 골뱅이가 들어있다. ㄷ자 모양은 가로 및 세로로 ..

티스토리툴바