Python32 백준 [5052] 전화번호 목록(트라이, 문자열, 트리, 정렬) with python 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 문제를 풀기 위해서는 트라이라는 개념을 알아야한다. 시간 제한이 없다면 그냥 하나하나 탐색을 하면 되겠지만 시간 제한이 1초다. 트라이를 간단히 설명하자면 아래와 같다. 트라이(Trie)란? Trie: 트라이(Trie)란 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조입니다. 위에 보이는 트리의 루트에서부터 자식들을 따라가면서 생성된 문자열들이 트라이 자료구조에 저장되어 있다고 볼 수 있습니다. 저장된 단어는 끝을 표시하는.. 2022. 1. 19. 백준 [1764] 듣보잡 (정렬, set, 문자열, 해시) with python 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 문제를 읽어보면 들어보지 못한사람이랑 보지 못한사람에서 중복되는 사람들을 오름차순으로 출력하면 되는 문제라 생각보다 처음에는 그냥 쭉쭉 풀어나갔다 그런데 시간 제한이 2초라 널널할 줄 알았는데 테스트케이스에서 500,000개를 꽉 채우면 시간 초과하는 일이 발생하는 듯 보였다. 아래는 처음에 짠 코드다. n, m = map(int, input().split()) never_heard = [0 for _ in range(n)] never_listen = [0 f.. 2022. 1. 11. 백준 [2217] 로프(수학, 그리디, 정렬) with python 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성 Check Point: 1. 모든 로프를 사용해야 할 필요 X 2. 처음에 하나의 로프로 가장 큰 무게를 들 수 있는 로프를 찾기 위해 오름차순 정렬 3. 작은 무게를 들 수 있는 로프부터 나눠 들 때 최대무게를 구해 현재 max 값과 비교. n = int(input()) lopes = [0 for _ in range(n)] for i in range(n): tmp = in.. 2022. 1. 10. [1932] 정수 삼각형 with python (다이나믹 프로그래밍 dp) https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 처음에는 왼쪽 오른쪽만 된다는 생각을 안하고 코딩을 했더니 이상하게 답이 나왔는데 문제 잘 읽어보니 왼쪽 오른쪽 자식만 가능하다!! 1. DP 배열을 따로 만들어서 기존값이 수정되서 더할 때 문제되지 않게끔 하면 될 듯하다! 2. n==1 일때 반례를 생각못해서 계속 90퍼쯤 틀렸는데 이 부분도 체크! 백준 게시판에 질문을 남기려다가 딱 찾아서 혹시 나같은 사람이 있을까봐 올려뒀음! 글 읽기 - 게시판에 있는 반례를 다 해봤는데 안되시는 분!! 댓글을 작성하려면 로그인.. 2021. 9. 30. 이전 1 2 3 4 ··· 8 다음
