개인 공부185 [Python] 백준 2623번 : 음악프로그램 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 문제 풀이 그래프 이론 중 위상정렬 문제이다. 위상정렬 알고리즘을 알고 있다면 쉽게 풀 수 있는 문제이다. 느낀 점 위상정렬에 대해서 한번 짚고 넘어갈 수 있는 문제가 되었다. 코드 import sys input = sys.stdin.readline N, M = map(int, input().split()) graph = [[] for _ in range(N+1)] indegr.. 2022. 7. 31. [Python] 백준 1107번 : 리모컨 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 💡 문제 풀이 브루트 포스 문제이다. 모든 경우를 따져주면 된다. 백만까지 범위의 모든 숫자를 따져서 가장 낮은 값을 찾아주면 된다. 주어진 범위는 50만까지인데 더 따지는 이유는 500,000 채널을 가려고 하는데 1, 2, 3, 4, 5가 고장 났을 경우 100에서 499,900번을 누르는 게 정답이 아니라 600,000에서 100,000번을 - 누르는게 정답인 경우가 있기 때.. 2022. 7. 30. [Python] 백준 1759번 : 암호 만들기 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 💡 문제 풀이 백트래킹 문제이다. 주어진 길이까지 백트래킹을 실시하고 주어진 조건만 맞추면 된다. 백트래킹의 기본이라고 볼 수 있다. ✔️ 느낀 점 브루트포스인 줄 알고 풀었는데 백트래킹 문제였다. 💻 코드 import sys l, c = map(int, sys.stdin.readline().split()) words = sorted(list(map(str, sys.stdin.readline().spl.. 2022. 7. 29. [Python] 백준 1577번 : 도로의 개수 https://www.acmicpc.net/problem/1577 1577번: 도로의 개수 첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 50보다 작거나 같은 자 www.acmicpc.net 💡 문제 풀이 DP 문제이다. 이 문제는 메모리의 크기는 작긴 하지만 n, m의 100까지므로 배열을 사용해도 괜찮다. 최단거리로만 이동하기 때문에 항상 아래 혹은 오른쪽으로만 이동한다는 점이 포인트이다. 주어진 (a,b), (c,d)에 대해서 어떤 점이 못 가는 점인지 판단하기 까다롭다는 생각에 방향에 따라 이동 가능 여부를 따지려고 4차원 배열까지 가고 마지막 배열에 boole.. 2022. 7. 26. [Python] 백준 2110번 : 공유기 설치 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 💡 문제 풀이 이분 탐색 문제이다. 입력받은 집의 위치를 정렬해서 이분 탐색을 진행한다. 이분 탐색 시 mid는 공유기 사이의 거리를 의미한다. 따라서 최소거리는 1, 최대 거리는 마지막 집과 처음 집의 간격이다. 지금 설치하려는 위치가 확인하는 간격(mid)을 벗어나는지 확인하면서 설치한 공유기 개수를 세어준다. 설치한 개수가 c보다 크다면 간.. 2022. 7. 26. [Python] 백준 1300번 : K번째 수 https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 💡 문제 풀이 이분 탐색 문제이다. 메모리가 128MB까지고 배열의 크기가 100억이 될 수 있어서 반복문으로 메모리를 할당해서 풀 수 없다. 찾으려는 값 K보다 작은 값의 개수를 알면 K가 어디 있는지 알 수 있기 때문에 확인하는 값(mid)보다 작거나 같은 숫자를 세면서 이분 탐색을 진행해주면 된다. ✔️ 느낀 점 이분 탐색 문제는 풀면서 항상 느낀다. 아이디어를.. 2022. 7. 26. 이전 1 ··· 20 21 22 23 24 25 26 ··· 31 다음