Trey

백준 1764번: 듣보잡 (www.acmicpc.net/problem/1764) 💡접근 제한 시간 : 2초 듣도 못한 사람 리스트, 보도 못한 사람 리스트에서 중복 원소를 찾아야하는 문제이다. 두개의 리스트를 만들어 이중 for loop으로 모든 원소를 비교할 경우, 최악의 경우 50만x50만 = 2500억번의 연산을 해야하므로 시간초과가 날 수 있다. 따라서, 탐색하는 시간이 O(1)걸리는 python dictionary를 사용해서 풀어보면 어떨까? 먼저, 듣도 보도 못한 종류의 관계없이, 이름을 key값으로 가져가고, key가 처음 생기는 경우라면 1을 넣어준다. → 삽입에 총 O(n) 시간복잡도가 소요됨 key값이 앞에서 만들어져있는 상태에서 또 같은 key값이 입력값으로 들어온다면, 해당 key값..

백준 1676번: 팩토리얼 0의 개수 (www.acmicpc.net/problem/1676) 💡접근 시간 제한 : 2초 구해야 하는것은 팩토리얼 결과값의 1의 자리부터 0이 나오지 않는 첫번째 숫자까지 0의 개수를 구하는것이다. 단순히 팩토리얼을 다 계산한 다음에 뒤에서부터 0의 개수를 세면 되지 않을까? ⚠️ 일단 문제에서 가장 큰 수인 500!의 자릿수는 무려 528이다... ⚠️ 역시 파이썬...! Python3.0부터는 int에 사이즈가 없어져서 자료형은 int를 사용해도 될 것 같다. https://docs.python.org/3/whatsnew/3.0.html#integers 팩토리얼을 계산한 후에 뒤에서 0의 개수를 세는 방법으로 풀겠다. 💡배운점 및 오답원인 다른 사람들의 풀이를 보니, J..

백준 1541번: 잃어버린 괄호(www.acmicpc.net/problem/1541) 💡접근 첫번째 숫자 다음 숫자부터, 마이너스 부호가 있을경우 다음 마이너스 부호가 나타나기전까지의 숫자들을 괄호처리하여 더한다. (아래의 그림을 참고하면 쉽게 이해될 것이다) 그리고 마이너스 부호가 없는 입력값의 경우는 다 더하기! 참고로, 예시를 보니 숫자의 위치는 바뀌지 않고, 괄호로 묶는다고해서 부호가 바뀌지는 않는다. 💡배운점 및 오답 원인 생각보다 예외조건 처리하는것이 까다로웠다.. 💡풀이 코드 input = input() # 마이너스 부호가 있으면 분류하기 if '-' in input: subs = input.split('-') # 마이너스 부호가 있었던 숫자들의 합 구하기 subs_sum = 0 for i ..

백준 Z문제(www.acmicpc.net/problem/1074)를 풀다가 분할 정복 개념을 다시 공부해야겠다고 느껴서 공부도 할 겸, 정리도 한번 할겸 이 글을 써봅니다! 1. 분할 정복(Divide and Conquer) 알고리즘이란? 2. 병합 정렬이란? 3. 병합 정렬 시간 복잡도 1. 분할 정복(Divide and Conquer) 알고리즘이란? 어떤 문제를 재귀적으로 분할, 정복, 그리고 결합하는 3단계의 방법으로 해결하는 기법입니다. 1) 분할 (divide) : 원래 문제를 더 작은 단위로 나눈다. - 예시) 병합 정렬에서 길이가 8인 원소를 길이가 4인 두개의 리스트로 나누는 단계 2) 정복 (conquer) : 문제의 단위가 해결하기에 충분히 작아졌다면, 종료 조건을 가지고 문제를 해결한..