본문 바로가기

알고리즘/백준

 (263)
[백준] 13975번 : 파일 합치기 3 13975번: 파일 합치기 3 13975번: 파일 합치기 3 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, www.acmicpc.net 🤔 문제분석 우선순위큐를 활용하여 가장 작은 파일부터 합쳐나아가는 문제입니다. 가장 작은 파일끼리 합쳐야 합의 가중치가 낮기때문입니다. 💻 코드 import sys import heapq input = sys.stdin.readline T = int(input()) for _ in range(T): K = int(input()) queue = [] for file in list(map(int, input().split())): h..
[백준] 16724번 : 피리부는사나이 16724번: 피리 부는 사나이 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 🤔 문제분석 서로소 집합을 활용하여 문제를 해결하였습니다. 사이클이 생기는 집합을 만들고, 그 집합의 총 개수를 구하면 됩니다. 사이클이 생기는 그룹의 집합안에서 어느한곳이 막힌다면 움직이지 못하기 때문입니다. 유니온-파인드로 사이클을 모두 하나의 집합으로 만들어주고 그 집합의 개수를 새면 됩니다. 💻 코드 import sys input = sys.stdin.readline N, M = map(i..
[백준] 14725번 : 개미굴 14725번: 개미굴 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N (1 ≤ N ≤ 1000)개가 주어진다. 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 정 www.acmicpc.net 🤔 문제분석 입력값을 알파벳 순으로 정렬을 하고, 정렬한 데이터를 순회하면서 경로를 기준으로 방문처리를 하여 문제를 해결하였습니다. 이미 방문한 경로가 있다면 그 경로는 무시 하도록 하면 됩니다. 💻 코드 import sys input = sys.stdin.readline visited = set() N = int(input()) ants_route = [] for _ in range(N): temp = list(map(st..
[백준] 1351번 : 무한수열 1351번: 무한 수열 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 🤔 문제분석 다이나믹프로그래밍 + 깊이우선탐색으로 문제를 해결 할 수 있습니다. 깊이 우선탐색을 하게되면 P와 Q가 2이상이기때문에 지수시간이 됩니다. N이 10^12 이므로 O(N)으로는 문제를 해결 할 수 없습니다. 다이나믹 프로그래밍을 처음에는 배열을 N크기만큼 생성했었는데 N의 크기만큼 생성하지않고 딕셔너리 자료구조를 활용하였습니다. 딕셔너리 자료구조도 마찬가지로 메모리 크기가 지수의 크기만큼 생성되기때문에 훨씬 효율적입니다. 💻 코드 import sys from collections import defaultdict input = sys.stdin.readline N, P..
[백준] 16562번 : 친구비 16562번: 친구비 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 🤔 문제분석 유니온-파인드로 문제를 해결 할 수 있습니다. 친구-친구-친구인 상태는 이미 Parent가 같은 집합들입니다. 그렇기 때문에 처음에 친구관계가 주어진다면 모두 유니온 합니다. 그런다음 친구비를 오름차순으로 정렬한뒤에 해당 친구와 유니온을 하는데, 이미 간선이 연결되어있는 상황이라면 유니온을 하지 않아야합니다. 최소신장 트리의 길이는 구하는 문제처럼 해결하면 됩니..
[백준] 1525번 : 퍼즐 1525번: 퍼즐 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 🤔 문제분석 너비우선탐색, 집합 자료형을 활용하여 문제를 해결하였습니다. “123456780”을 하나의 문자열로 보고 해당문자열을 방문처리 하여 그다음 방문때 방문하지 않도록 합니다. 0의 위치를 파악하고 해당위치에서 갈 수 있는 곳을 선택하여 너비우선탐색합니다. Serialize 와 Deserialize 함수를 두었는데, Serialize 함수는 2차원 배열을 문자열로 바꾸어주는 함수이고, Deserialize 함수는 문자열을 다시 배열로 바꾸어주는 함수입니다. 탐색을 할때에는 2차원 배열을 사용하고, 방문처리를 할때에..
[백준] 6198번 : 옥상 정원 꾸미기 6198번: 옥상 정원 꾸미기 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net 🤔 문제분석 스택 자료구조를 활용하여 문제를 해결한다. 스택은 해당위치에서 자기자신보다 낮은 건물이 나올때까지 꺼낸다. 스택에 담긴 자료는 해당 건물포함해서 그 뒤에 볼 수 있는 건물을 담는다. 자기자신보다 큰 건물이기때문에 해당 건물을 포함한 그 뒤에있는 건물 또한 볼 수 있기때문이다. 💻 코드 import sys input = sys.stdin.readline N = int(input()) buildings = list(..
[백준] 17299번 : 오등큰수 17299번: 오등큰수 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 🤔 문제분석 스택 자료구조를 활용하면 문제를 해결 할 수 있다. counter 해당 숫자의 개수를 누적하고, 인덱스로 접근하여 개수의 크기를 판별한다. 만약 리터리에션에서 자기자신보다 작은 counter들은 모두 꺼내고, 작업을 다완료한뒤 stack의 크기를 확인하여 stack이 0보다 크면 스택의 마지막 원소에서 인덱스를 가져오고 그렇지 않다면 -1을 넣는다. 💻 코드 import sys input = sys.stdin.readline N = int(..

티스토리툴바