[백준] 16946 벽 부수고 이동하기 4 | BFS | Gol2 Pythonhttps://www.acmicpc.net/problem/16946 채점 되게 천천히 됨 쫄깃하네여..ㅎ골드 쯤 되니까 시간제한이 문제가 되기 시작한다 ㅎ허허 구상유형 : bfs [문제 해석]벽이 존재하는 맵이 주어짐. 각 벽마다 벽이 없어졌을 때, 해당 벽 위치에 인접한 공간 크기를 구하는 문제빈 공간은 0, 벽은 1벽 위치에 해당하는 공간 크기를 10으로 나눈 나머지를 출력시간제한 : 2초구상 1 (timeout)전체를 돈다벽(1)이 나오면 해당 벽에 인접한 공간을 bfs 돌며 공간 크기를 계산한다벽 위치에 공간 크기를 10으로 나눈 나머지를 기록한다 구상 2 (성공)전체를 돈다방문 전인 빈 공간(0)이 나오면 bfs 인접한..
DSA
[백준] 2146 다리만들기 | BFS | Gol3 Pythonhttps://www.acmicpc.net/problem/2146 pypy로만 성공한 풀이입니다.(python은 시간초과)구상유형 : bfs비슷한 문제들을 푸는 중이라 접근은 어렵지 않게 했으나조건문 하나 잘못적어서 시간 진짜 많이 썼다 도륵시간초과만 나서 시간을 줄이는 방법만 고민했는데 코드에 잘못된 부분이 있었다코드에 논리적인 오류가 있어도 오답이 아닌 시간초과만 날 수도 있다는 것을 깨달은 시간,,,pypy로만 통과했지만 핵심적인 문제는 찾았고 더 이상 시간복잡도 개선에 시간을 쓰는 건 무리라고 판단. 넘어가자! [문제 해석]땅과 땅을 연결하는 가장 짧은 다리 길이 찾기다리와 인접해있으면 연결된 것임시간제한 2초 구상전체를 2번 돌아야 ..
[백준] 13549 숨바꼭질 3 | BFS | Gol5 Pythonhttps://www.acmicpc.net/problem/13549 구상유형 : bfs직전에 푼 1697과 유사그래서 좀더 깔끔하게 풀 수 있었다! [문제 해석]1697 숨바꼭질 문제와 동일하나, 2배 이동을 하는 경우 드는 시간이 0이라는 점만 다르다.N에서 K로 가는 가장 빠른 횟수 찾기한 횟수에 할 수 있는 이동의 종류는 3가지+1-12배 0 ≤ N, K ≤ 100,000시간제한 2초메모리제한 512 MB 구상매번 세가지 경우 모두 bfs 돈다단, 아래 조건을 만족하지 않으면 큐에 넣지 않는다.이미 방문했던 숫자의 경우 이전의 해당 숫자까지 갔던 최소이동횟수보다 클 때숫자가 이동 가능 범위를 벗어날 때 (0 ≤ N ≤ 100,000)..
[백준] 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과제를 점수 큰 순으로 마감일에 가장 가까우면서 배치가능한 자리에 배치구현과제 점수 기준으로 최대힙을 만든다.점수가 가장 큰 과..
[백준] 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..
