[백준] 11000 강의실배정 | Gol5 | 힙? Pythonhttps://www.acmicpc.net/problem/11000 구상풀이 1 : 리스트 (시간초과, pypy만 통과)풀이 2 : 힙 (시간초과, pypy만 통과)**풀이1, 2 는 동일 로직인데 사용한 자료구조만 다른 코드풀이 3 : 힙힙을 써서 통과된 게 아니라 로직을 더 효율적으로 개선해서 통과된 것임다동일 로직으로 리스트로도 가능할지도?그리고 다른 코드들 찾아보니까 더더 효율적인 로직이 있었다. 논리적으로 이해하기에는 내 코드가 쉽고, 대신 덜 효율적 [문제 해석]시간대가 겹치는 수업들을 최소한의 강의실에 배치하라답 : 강의실 최소개수시간제한 : 1초 구상효율 개선한 로직수업 시작시각, 종료시각을 시간순으로 정렬하고강의 시작 시각을 ..
분류 전체보기
[백준] 19638 센티와 마법의 뿅망치 | Sil1 | 힙 Pythonhttps://www.acmicpc.net/problem/19638 구상풀이 1 : 힙최대힙 음수로 써줘야 하는거 꽤나 귀찮네.. 메서드 만들어서 쓸 걸 그랬나풀이 2 (시간초과) : heapq 안쓰고도 풀 수 있나 싶어서 그냥 리스트랑 sort써서도 해봤다.-> heappush 대신 값을 넣을 때마다 다시 정렬해준다.-> 예제는 통과했으나 시간초과!heapq는 값을 정렬된 상태로 유지하며 계속 넣었다뺐다 해야할 때 유용할 것임을 느꼈다. [문제 해석]마법 뿅망치 : 키/2 가 됨. 키가 1일경우 영향x문제에 안적혀있었는데, 키가 홀수일 경우 2로 나눈 몫으로 하면됨항상 가장 키가 큰 사람 중 한명을 때림때리는 횟수T 제한있음답 : ..
[백준] 11279 최대 힙 | Sil2 | 힙 Pythonhttps://www.acmicpc.net/problem/11279 구상유형 : 힙(최대힙)파이썬은 그냥 heapq쓰면 되는 문제 구상최대힙이므로 heapq쓸 때 값을 음수로 저장입력된 자연수를 힙에 push입력이 0이면 가장 큰 값을 pop (출력하고 그 값을 배열에서 제거) 트러블 슈팅x 코드# v1 : 힙(최대힙)#파이썬은 그냥 heapq쓰면 되는 문제'''- 최대힙이므로 heapq쓸 때 값을 음수로 저장- 입력된 자연수를 힙에 push- 입력이 0이면 가장 큰 값을 pop (출력하고 그 값을 배열에서 제거)'''import heapqimport sysinput = sys.stdin.readlineN = int(input())heap = ..
[백준] 14675 단절점과 단절선 | Sil1 | 트리 Pythonhttps://www.acmicpc.net/problem/14675 구상유형 : 그래프(트리만 입력되는 경우) 단절점, 단절선 개념 [문제해석]주어진 트리에서 각 노드, 간선이 단절점, 단절선인지 묻는 질문에 답 출력질의 내용 t=1 일 때 : k번 정점이 단절점인가?t=2 일 때 : k번째로 입력받았던 간선이 단절선인가? 개념단절점, 단절선 : 특정 노드 또는 선을 제거했을 때 해당 그래프가 2개 이상으로 분리된다면 해당 노드 또는 선을 단절점 또는 단절선이라한다.DST(DFS Spanning Tree)를 활용해 단절점, 단절선을 판단할 수 있다.트리 : 모든 노드가 연결되어있는, 사이클 없는 그래프-> 사이클이 없고 모든 노드가 연..
[백준] 1991 트리 순회 | Sil1 | 그래프,트리 Pythonhttps://www.acmicpc.net/problem/1991 구상유형 : 트리 (dfs) [문제 해석]주어진 트리를 전위, 중위, 후위 순회한 순으로 각각 출력항상 A가 루트노드임시간제한 : 2초순회 방식전위 순회 : 루트 → 왼쪽 → 오른쪽 자식 순으로 방문중위 순회 : 왼쪽 → 루트 → 오른쪽후위 순회 : 왼쪽 → 오른쪽 → 루트 구상일단 트리를 입력받고.. 루트가 누군지 알려주니까 거기서부터 찾아가자세가지 순회 모두 현재 노드 기준으로 우선순위 먼저인 것부터 재귀호출 돌게 하고, 루트노드를 탐색하는 순서에 현재노드를 답에 추가해주면 된다. 트러블 슈팅순회방식 이해 한번에 못해서 몇번을 시뮬함 ㅎ 코드# v1 : 트리 (dfs)..
[백준] 14675 단절점과 단절선 | Sil1 | 그래프,트리 Pythonhttps://www.acmicpc.net/problem/14675 구상**주의**이 문제는 입력으로 트리만 들어오는데, 이 글은 트리가 아닌 그래프가 입력되어도 풀 수 있게 짠 풀이입니다.트리만 입력되는 경우에는 더 쉽게 풀 수 있으니 이렇게 안풀어도 됨!!!!!더 쉬운 풀이는 따로 글 쓰겠습니다 유형 : 그래프(트리)단절점, 단절선 개념 단절점 단절선 찾기 로직 이해하느라 한참걸렸다.. 나 이런거에 약해-> 아니 이문제는 이렇게 안풀어도 되는 문제입니다...ㅎㅎ... 트리만 주어지는 문제인데 나는 트리 아닌 그래프가 와도 되는 풀이로 풀고있던 거였다 어쩐지 어렵드라;;;; 트리만 입력될 때 쓸 수 있는 풀이로도 다시 풀어서..
[백준] 9663 N-Queen | Gol4 | 백트래킹 Python (시간초과)https://www.acmicpc.net/problem/9663 백트래킹 연습으로 풀어본 문제.돌고돌아서 테케가 통과되는 코드는 만들어냈지만 시간제한은 pypy로도 끝끝내 통과 못시킨 문제통과된 코드들이랑 비교해서 고쳐도 봤는데, 아예 코드를 갈아엎어야 하는 것 같다너무 시간을 많이 써서 여기까지만 하는 걸로.. 애초에 파이썬으로 통과되기 빡빡한 문제라고 하고,내 수준에서는 최적화에 시간을 더 쓰기보다는 다른 문제들을 풀어보는 게 맞는 것 같다.그래도 얻은 것들이 많아서 기록! 구상 [문제해석]N-Queen : 크기가 NxN인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제N이 주어지고, N개를 놓을 수 있는 경우의..
[백준] 15666 N과 M (12) | Sil2 | 백트래킹 Pythonhttps://www.acmicpc.net/problem/15666 구상백트래킹[문제해석]N개의 자연수 중 M개 고르기같은 수 여러번 고르기 가능수열은 비내림차순(같거나 오름차순)이어야 함 -> 순서 다른것도 정렬해서 같은걸로 쳐야 함결과는 중복없이, 사전순으로 트러블 슈팅x 코드# v1 : 백트래킹'''[문제해석]- N개의 자연수 중 M개 고르기- 같은 수 여러번 고르기 가능- 수열은 비내림차순(같거나 오름차순)이어야 함 -> 순서 다른것도 정렬해서 같은걸로 쳐야 함- 결과는 중복없이, 사전순으로'''N, M = map(int, input().split())nums = list(map(int, input().split()))num..
[백준] 15663 N과 M (9) | Sil2 | 백트래킹 Pythonhttps://www.acmicpc.net/problem/15663 구상[문제해석]N개의 자연수 중 M개를 고른 모든 경우 출력순서 다르면 다름중복 수열 없이사전순 출력구상 : 현재까지의 수열, 사용여부, 숫자 갯수 세기 해야겠군정렬된 순서로 만들면서 중복을 제거해줘야 했는데, 두 가지 방법으로 풀 수 있었다.set은 사용할 수 없었음! (트러블슈팅 참고)풀이 1 : 백트래킹 - dict.fromkeys(리스트)list(dict.fromkeys(리스트)) : 순서 유지하면서 중복 제거할 때 사용 가능!풀이 2 : 백트래킹 - 숫자 자료를 정렬해 직전값과 비교 트러블 슈팅처음에 냅다 문자열로 만들어서 set에 넣어 중복제거하고 마지막에..
[백준] 11725 트리의 부모 찾기 | Sil2 | BFS,DFS Pythonhttps://www.acmicpc.net/problem/11725 bfs dfs 까먹을 것 같아서 몸풀기!세가지 방법으로 풀어보았다. 구상풀이 1 : dfs - 재귀 (71496KB, 336ms)파이썬 재귀 깊이 제한을 조정하는 코드를 추가해서 통과했는데, 부하가 있는 것 같아 다른 방법도 풀어보기로풀이 2 : dfs - stack (61568KB, 312ms)풀이 3 : bfs - queue(deque) (62040KB, 300ms)성능은 채점시마다 약간의 오차가 있는걸 감안하면, 세가지 풀이에 그렇게 큰 차이는 없는 듯 하다.그래도 역시 bfs가 젤 빠르게 나오긴 했다만출력문으로 print말고 더 빠르다는 sys.stdo..
[백준] Sil2 | 해시 | 19583 싸이버개강총회 Pythonhttps://www.acmicpc.net/problem/19583 구상풀이 1 : 해시 - dictionary 알고리즘은 별거없는데 입력이나 시간 데이터 전처리가 귀찮았입력 종료 시점을 모르고 끝까지 받는 문제를 처음 풀어봐서 입력받는 법, 디버깅하는 법에서 헤맸다.풀이 2 : 해시 - setdictionary와 set은 공간, 시간복잡도가 거의 차이 안난다. set은 dictionary에서 key만 있는 거라고 보면 됨 [문제 해석]제때 입장, 퇴장 모두 확인된 사람 수제때 입장 : 채팅시각이 개총 시작시각보다 작거나 같음제때 퇴장 : 채팅시각이 개총 종료시각보다 크거나 같고 개총 스트리밍 종료시각보다 작거나 같음 -> 즉, 개총 시작..
[백준] Sil5 | 해시 | 7785 회사에 있는 사람 Pythonhttps://www.acmicpc.net/problem/7785 구상풀이 1 : 딕셔너리 쓰면 곰방곰방 풀린다딕셔너리 값 삭제는 del이나 pop을 쓴다.items()를 쓰면 key, value 쌍을 얻지만keys()를 쓰면 key만 얻을 수 있고 더 빠르다.풀이 2 : set을 써서 풀 수도 있다. dictionary써도 value에 넣을 게 딱히 없음.. key만 갖고있는 set으로도 풀어봤다.공간, 시간 복잡도는 거의 차이가 없었다. 신기하네join을 쓰면 출력이 훨 빨라져서 츄라이!sys.stdout.write도 써볼까.. 트러블 슈팅x 코드 - set# v2 : 해시 - setimport sysinput = sys.stdi..
[백준] Sil3 | 해시 | 17219 비밀번호 찾기 Pythonhttps://www.acmicpc.net/problem/17219 구상직전에 골드 쫌 머리싸매다 와서 싱거운 문제였다그냥 딕셔너리에 때려넣고 꺼내면 될 거 같은데..넴 됨시간 최적화한 다른 코드들 쫌 봤는데 입출력 한번에 하기나 sys.stdout.write나 다른 요상압축코드 써서 줄이고 계셨다간만에 기본 딕셔너리 복습했다날 열어주는 단 하나뿐인 비밀번호야 트러블 슈팅x 코드# v1 : 해시(딕셔너리)#그냥 딕셔너리에 때려넣고 꺼내면 될 거 같은데..넴 됨import sysinput = sys.stdin.readlineN, M = map(int, input().split())dic = {}for _ in range(N) : si..
[백준] Gol5 | 투 포인터,이진탐색 | 9024 두 수의 합 Pythonhttps://www.acmicpc.net/problem/9024 구상직전에 푼 3273번과 매우 유사한 문제! 풀이 1 : 이진탐색 (시간초과)TS : 테케 통과, 시간초과.. pypy는 통과!!! 논리는 맞았으나 시간이 문제.풀이 2 : 투 포인터이진탐색 문제는 투 포인터로도 풀 수 있다! [문제 해석]주어진 서로다른 수들 중 두 수의 합이 특정 수k에 가장 가까운 조합의 수숫자들은 -10^8 ~ 10^8(1억) 사이 정수. 숫자의 개수n는 1,000,000개 이하시간제한 : 1초답 : 합이 k에 가장 가까운 두 수 조합의 개수 구상2천만 연산 내에 짜야 함. n^2이면 시간초과3273번처럼 정렬 + 이진탐색 으로 짜면 될까..
[백준] Sil3 | 정렬,이진탐색 | 3273 두 수의 합 Pythonhttps://www.acmicpc.net/problem/3273 구상유형 : 정렬, 이진탐색시간초과땜에 이진탐색logn 사용완전 + 이진 -> nlogn [문제 해석]주어진 수들 중 두 수의 합이 특정 수x가 되는 경우의 개수숫자는 1~1,000,000 자연수, 숫자의 개수는 100,000 개 이하시간제한 : 1초 구상시간제한이 1초 = 2천만 건 안에 처리 -> n^2이 나오면 안됨2중 완전탐색 : n^2 시간초과완전 + 이진탐색 : nlogn, 통과!탐색 방법정렬해두고 탐색젤 작은거 + 더 큰거 로 시작작은걸 고정해두고 큰걸 옮기면서 반복, 합이 x보다 같거나 작아지면 break다음 작은 수 탐색작은 수는 배열 끝까지 탐색숫자..
