[백준] 1697 숨바꼭질 | BFS | Sil1 Pythonhttps://www.acmicpc.net/problem/1697 구상유형 : bfs메모리 초과는 처음봐서 고생했다. 문제 조건을 잘못이해했음..~ 그래도 배운 게 있으니까TIP : dict, set보다 처음부터 초기화해서 쓰더라도 list가 더 메모리 적게 쓰고 빠를 수 있다.Q : 아니 다들 visited체크를 해서 한번 방문한 노드는 다시 방문하지 않게 짜는데, 그게 왜 되지?? 더 최적으로 방문한 경로가 답이면 답이 걸러지지 않나A : BFS라서 그게 가능함! BFS는 넓이 우선 탐색이고, 우리는 가장 짧은 깊이의 답을 찾아야 하는 상황.이 때 이미 방문한 노드라는 뜻은 같은 깊이이거나 더 짧은 깊이에서 이미 그 숫자에 도달할 수 있었다..
알고리즘
[백준] 2667 단지번호붙이기 | DFS,BFS | Sil1 Pythonhttps://www.acmicpc.net/problem/2667 구상유형 : dfs (bfs도 가능할듯) [문제 해석]연결된 그룹의 수와 크기를 세는 문제가로세로로 인접되어있으면 같은 그룹임그룹의 총 개수 셈각 그룹마다 몇개가 포함되어있는지 개수 셈시간제한 1초5 구상칸 전체를 돈다visited면 넘어간다방문 전이면서 1인 칸을 만나면 dfs시작그 주변에 있는 1인 칸만 스택에 넣으며 dfs돈다 두두두돌면서 1 대신 해당되는 그룹 번호로 바꿔준다 (0,1은 이미 입력데이터에서 사용중이므로 그룹 번호는 2부터 사용)dfs끝나면 칸 전체 돌기를 이어서 진행 트러블 슈팅문제 구상에서 실수해서 한번 헤맸다 dfs bfs도 아직 멀었구나..
[백준] 14698 전생했더니 슬라임 연구자였던 건에 대하여 (Hard) | Gol4 | 힙 Pythonhttps://www.acmicpc.net/problem/14698 구상유형 : 힙최소값이 어떤 경우일지 고민을 했는데 찾아보니까 그냥 매번 현재 존재하는 슬라임 중 가장 작은 것들을 쓰면 최소라고 함. 왜지?[문제 해석]슬라임을 2마리씩 합성하는데, 합성 시마다 두 슬라임의 에너지의 곱만큼 전기가 든다.합성 결과로 두 슬라임의 에너지의 곱만큼의 에너지를 가진 한마리의 새로운 슬라임이 됨 슬라임을 모두 합성해 한마리로 만드는 데에 드는 모든 전기의 곱의 최소값 답 : 테스트케이스마다 모든 전기의 곱의 최솟값을 1, 000, 000, 007 로 나눈 나머지 출력 구상최소값을 어케 구할까..-> 그냥 작은..
[백준] 13094 과제 | Gol3 | 힙 Pythonhttps://www.acmicpc.net/problem/13904 구상풀이 1 : 별다른 자료구조 사용않고 그냥 구현함 (112ms) 로직 특성상 힙을 활용한 방식보다 느리다.풀이 2 : 힙 (56ms)이 방식이 속도가 훨씬 빠르다!접근 방식을 아예 다르게 해야 힙을 쓸 수 있었다. 로직을 새로 짬. 더 효율적인 로직임! [문제 해석]얻을 수 있는 점수 최댓값 구하기과제는 하루에 1개만, 완료 시 점수과제 별로 점수 다름. 마감일 지나면 점수x과제 개수N 마감일까지 남은 일수d 시간 제한 : 1초 구상 - 힙 쓰는 ver과제를 점수 큰 순으로 마감일에 가장 가까우면서 배치가능한 자리에 배치구현과제 점수 기준으로 최대힙을 만든다.점수가 가장 큰 과..
[백준] 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..
