본문 바로가기
728x90

백준 풀이103

[백준/BOJ] - 11497번 python 풀이 - 그리디 푸는데 고생좀 한 문제. 일단 주어진 배열을 오름차순으로 정렬한다. [10,10,11,11,12,12,13] 이라고 정렬 됐을 때, 문제에서 원하는 배열을 가지기 위해서는 가장 큰 값을 가운데로 두고, 가장 작은 값부터 배열 외각에 위치시키는 것이 주 목적이다. 본인은 하나의 반복문안에 변수 2가지를 한번에 처리하려고 했다. 그 말은 즉, 정렬시킬 배열을 temp라고 가정하면, temp의 앞, 뒤에 원하는 변수를 넣는 과정을 한번에 처리하려고 했다는 점. 1 사이클이 끝나면 [10,0,0,0,0,0,10] 2 사이클이 끝나면 [10,11,0,0,0,11,10] . . . 최종적으로 [10,11,12,13,12,11,10] 이 되게끔 해야함. 처음 반복문 변수를 통해 구현하려 했는데, 반복문 변수를 이용하.. 2023. 11. 1.
[백준/BOJ] - 1946번 python 풀이 - 그리디 해당 문제는 단순하게 보면 서류와 면접 순위가 동시에 나보다 뛰어난 사람이 있으면 떨어뜨리는 문제이다. 그렇다면, 입력된 정보들을 서류 순위 기준으로 정렬을 한다. 그러면, 첫번째에 위치한 값은 서류 1등이기 때문에 비교를 할 필요가 없다. 그렇다는 것은 두번째부터 비교를 해야한다는 의미이며, 2번째에 위치한다는 것 자체가 탈락할 위험군이라는 의미이다. 서류에서 나보다 뛰어난 인원(정렬했을 때 idx가 나보다 앞에 있는 친구들)이 존재하기에, 그 인원들과의 면접 순위를 비교해봤을때 나보다 뛰어난지 아닌지를 비교하면 된다. 하나하나 다 비교하면 시간 복잡도가 비약적으로 상승하기 때문에 시간 초과를 방지할 겸 비교하려는 대상의 면접 순위와 서류가 나보다 뛰어난 친구들 중 면접 1등과 비교를 한다. 기본적으로.. 2023. 10. 31.
[백준/BOJ] - 11660번 python 풀이 - dp https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제를 봤을 때, 주어진 x 좌표와 y 좌표를 직관적으로 계산하여 해당 범위 내에 있는 값을 구하려 했는데, 단순 2차원 배열 반복문 문제가 실1이 맞나..? 싶었는데 역시나 였다. 정답은 잘 나오지만, 시간 초과가 떠버렸다. 심신미약 상태라 다른 방법이 도저히 떠오르지 않아 어떤 알고리즘 쓰는지 봤는데 dp 였다. 기존 주어진 배열의 크기와 같은 크기의.. 2023. 9. 18.
[백준/BOJ] - 1043번 python 풀이 - set https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 이 문제를 처음 보고 "그래프 탐색으로 하면 될 거 같은데..?"란 생각이 들었다. 하지만 그래프를 어떤 기준으로 정렬할지에 대한 해답이 나오지 않아 직관적으로 접근했다. 기본적으로 진실을 알고있는 집합이 주어진다. 진실을 알고 있는 집합의 원소를 파티 구성원으로 가지고 있는 파티 집합을 구해야 한다. 그렇기에 테스트 케이스를 보고 윗줄부터 아랫줄을 훑으며 겹치는 파티들과 진실의 집합을 합치면 되겠다는 생각.. 2023. 9. 13.
[백준/BOJ] - 1541번 python 풀이 - 문자열 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 괄호를 통해 +, -로만 이루어져 있는 식의 결과 값을 최솟값이 나오게 설계해야하는 문제이다. 사실상 괄호가 해당 식들에게 유의미한 영향을 줄 수 있는게 어떤 것이 있을까 생각했다. 바로 숫자 앞에 붙어있는 '-'를 무효화 할 수 있다는 것. 해당 문제는 만들 수 있는 최솟값을 만드는 것이 목적이므로 숫자 앞에 딸랑 붙어있는 -를 더 강력하게 괄호를 통해 더욱 더 - 값이 커지게 설정이 가능.. 2023. 9. 13.
[백준/BOJ] - 1389번 python 풀이 - 케빈 베이컨의 6단계 법칙 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 어떻게 풀면 될까? 문제의 설명이 다소 복잡한 면이 있기 때문에 집중해서 읽어보면 친구의 친구의 친구의~~ 친구! "두 사람이 있다고 가정하고 그 둘이 몇 관계 만에 이어질 수 있는가"가 핵심인 문제이다. 일단 기본적으로 인원의 수와 인맥 관계에 대한 입력이 주어지는데, 이를 보자마자 든 생각은 인맥 관계에 대한 설명이 나왔으니, 그래프에 해당 관계.. 2023. 9. 13.
728x90