본문 바로가기

전체 글74

[백준] 7568번 문제출처: https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 브루트포스 알고리즘인데, 먼저 브루투 포스 알고리즘에 대해 간단히 이야기 하자면 이렇다. 주어진 경우의 모든 경우의 수를 구한다. 그리고 그 중에서 원하는 입력값에 맞는 값을 찾아낸다. 이러기 위해선 완전 탐색이라는 것을 해야 예외없이 완벽하게 수행할 수 있다. ​ 브루트 포스는 선형 구조일 때는 순차 탐색을, 비선형 구조일 때는 깊이 우선 탐색(DFS), 너비 우선 탐색(.. 2022. 6. 15.
[백준] 1789번 문제출처: https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 슬금슬금 실버 5단계로 올라와서 풀기 시작한 문제다.(아직 수학구현이긴 하지만...) 사실 이 당시의 나한테는 브론즈 2~ 실버 5단계는 나누는 것에 의미가 없었다. 브론즈가 더 어렵게 느껴질 때도 있는 초짜여서 그랬던가^_ㅠ ​ 아무튼 문제의 내용을 요약하자면, 서로 다른 N개의 자연수의 합이 S인데, S가 주어졌을 때 N의 최대 개수를 구하는 것이다. 최소 개수면 그냥 자기 자신을 합한 경우인 1밖에 안 나오기 때문에 최대 개수로 정한 듯하다. 가령, S = 55라면, 우리는 1+2+3+4+5+6+7.. 2022. 6. 15.
[백준] 13305번 문제출처: https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 미루고 미루던 그리디 알고리즘 문제이다. 문제를 요약하면, 원하는 도시까지 도달하는데 필요한 최소의 주유비를 구하는 것이다. 가령 예시처럼 4개의 도시가 있고 마지막 도시에 도달하고 싶을 때, 최소한으로 1리터당 5원하는 맨 첫번째 도시에서 5x2=10원 충전을 필수로 하고 그 다음 가장 주유비가 저렴한 곳에서 나머지 리터당 주유를 채우면 된다. 다만, 제일 오른쪽 거리는.. 2022. 6. 15.
[백준] 1764번 문제출처: https://www.acmicpc.net/problem/1764 듣보잡이라는 말도 벌써 한참 지난 유행어인가... Latte는 쓰고 다녔는데(^,^..) 듣도 못한 사람, 보도 못한 사람의 명단이 출력된다. 그 명단 중 겹치는 사람을 '듣도보도 못한 사람'(듣보잡)이라고 정의한다. 그리고 우리가 출력해야 할 것이 그 명단이다. 명단에 있는 사람의 수, 그리고 사전순(오름차순)으로 명단을 출력하면 된다. ​ 처음에는 듣도 못한 사람의 배열, 보도 못한 사람의 배열을 각각 append받아서 그 두 가지를 비교하는 것을 생각했다. 당연히 시간초과가 난다. 제한시간은 2초다. 한 3~4초였으면 이것도 되긴 됐을 것같은데, 제한 시간이 걸려있기 때문에 패스. ​ 그렇다면 집합을 이용하면 어떨까? 고등.. 2022. 6. 15.
[백준] 1205번 문제출처: https://www.acmicpc.net/problem/1205 1205번: 등수 구하기 첫째 줄에 N, 태수의 새로운 점수, 그리고 P가 주어진다. P는 10보다 크거나 같고, 50보다 작거나 같은 정수, N은 0보다 크거나 같고, P보다 작거나 같은 정수이다. 그리고 모든 점수는 2,000,000,000보 www.acmicpc.net 말 그대로 등수를 구하는 문제이다. 단, 동점이 존재할 경우 같은 등수로 보고 그 직후의 등수를 +1등수로 한다. Test Case로 예를 들면, [100, 90, 90, 80]이 존재할 때 1,2,2,4등인 것이다. 3등이 없고 동점자는 2등으로 두명인 셈이다. ​ 나는 처음에 문제를 잘못 이해하고(대충 본 내 잘못.맞음.) 80을 3등이라고 생각했다. 그.. 2022. 6. 15.
[백준] 1436번 문제출처: https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 감독 숌이 종말의 숫자(?) '666'이 들어가는 숫자의 영화 시리즈를 낼 때 그 시리즈가 몇번째인지 알 수 있다. 문제 제목을 종말의 숫자로 바꿔도 될 것같다. 근데 다른 얘기긴 한데 숌도 참 산독기인것같다. 보니까 N이 10000 이하의 자연수던데 그럼 시리즈를 10000개 내겠다는 포부일까... 진짜 야망어린 독기인 것같다. 나도 저렇게 살아야지. ​ '666'이 들어가는 경우는.. 2022. 6. 15.

티스토리툴바