🕹 알고리즘/💁🏻♂️ 백준
백준 :: 7570번 줄 세우기 (Python)
문제 링크 https://www.acmicpc.net/problem/7570 7570번: 줄 세우기 입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하 www.acmicpc.net 접근 방식 정렬을 하려고 삽질을 하다가 결국 다른 분들의 풀이를 참조했던 문제 .. 제일 앞이나 제일 뒤로 보내는 어린이의 수를 구하기 위해서는 현재 어린이들 중에서 잘 서 있는 어린이의 수와, 잘못 서있는 어린이의 수를 구하면 된다. 예를 들어 예제 입력으로 나온 5 2 4 1 3 의 경우 2번과 3번은 “잘 서 있다” 라고 말할 수 있다. 그 외의 5, 4, 1번의 어린이는 제일 앞이나 뒤..
백준 :: 1254번 팰린드롬 만들기 (Python)
문제 링크 https://www.acmicpc.net/problem/1254 1254번: 팰린드롬 만들기 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. 동호는 www.acmicpc.net 문제 캡쳐 접근 방식 앞에서부터 읽나 뒤에서부터 읽나 똑같은 문자열를을 팰린드롬이라고 하고, 최소한의 문자를 추가해서 팰린드롬으로 만드려고 할 때 그 길이를 출력하는 문제입니다. 먼저 가장 최선의 경우와 최악의 경우를 먼저 떠올려 봤는데 최선의 경우는 이미 팰린드롬이기 때문에 하나도 붙이지 않아도 되는 경우, 최악의 경우는 주어진 문자열만큼을 뒤집어서 뒤에 덧붙여줘야 하는 경우였습니다. 예를..
백준 :: 1202번 보석 도둑 (Python)
문제 링크 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 접근 방식 먼저 각 가방에 담을 수 있는 보석의 최대 가격을 구하는 문제라서 보석을 가격 순으로 내림차순 정렬하고 가방마다 보석을 순회하면서 최대한 높은 가격의 보석을 담으려고 했다. 하지만 그렇게 생각하고 제약사항을 봤는데 보석과 가방의 개수가 각각 최대 30만.. 내가 생각한 풀이의 시간복잡도를 계산해보면 30만의 제곱이라..
백준 :: 1541번 잃어버린 괄호 (Python)
문제 링크 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 접근 방식 +, - 연산만 가능한 상태에서 식의 결과를 최소값으로 만드려면 최대한 큰 값을 빼주면 된다. 즉, - 뒤에 나오는 + 연산을 먼저 해주면 된다. 첫번째 예제로 살펴보면 55-50+40 의 값을 최소로 만드려면 55-(50+40) 으로 괄호를 쳐주면 된다. 그렇다면 - 를 기준으로 식을 자르고, 자른 식들을 먼저 계산한 후 전부 빼주는 식으로 구현해보자 ! 풀이 코드 i..
백준 :: 10951번 A+B-4 (Java, Python)
https://www.acmicpc.net/problem/10951 10951번: A+B - 4 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 브론즈 5에 해당하는 쉬운 문제이지만, 테스트의 종료 조건을 처리하지 못해서 틀린 사람들이 많은 것 같다. 문제를 살펴보자. 살펴볼 포인트는 두 가지이다. 공백을 기준으로 두 정수가 입력됨 더 이상 읽을 데이터가 없을 때 입력이 종료 여기서 주의할 점은 읽을 데이터가 없다는 것 ! 읽을 수 있는 데이터가 없다는 건 EOF 를 의미한다. EOF 는 End Of File. 데이터가 더 이상 존재하지 않는 파일의 끝을 의미한다. 일단 입력 방식을 여러 가지로 해서 풀어보자. 사실 방금 자바 입력 시간 줄이는 법..
백준 :: 1237번 정ㅋ벅ㅋ (Python)
백준 문제 알고리즘을 조금씩 풀면서 글을 써보려 한다. 오늘은 첫번째 문제 풀이 ! 사실 이 문제는 알고리즘 문제가 아니라 넌센스 문제이다. https://www.acmicpc.net/problem/1237 1237번: 정ㅋ벅ㅋ 우주를 정ㅋ벅ㅋ할 사람에게는 예제 입력과 예제 출력이 필요하지 않다. www.acmicpc.net 문제를 살펴보자. 입력없이 "첫째 줄에 문제의 정답을 출력한다" 고만 되어있다. 무슨 말인지 알지 못해 시간이 걸렸는데.. 말 그대로 "문제의 정답" 을 출력하면 끝이다... print("문제의 정답") 끝.