문제 링크https://www.acmicpc.net/problem/14567느낀 점위상정렬의 가장 기본적인 문제 형태라고 생각된다.진입차수를 따져주는 것이 위상정렬에서 키 포인트라고 생각되는데, 진입차수에 대한 배열을 만들고 진입차수가 0인 경우에만 다시 큐에 넣어서 순회해주어야 시간초과, 메모리 초과를 피할 수 있다!입력에 대해 두 가지 자료구조를 생각해볼 수 있다. 아마 현재 문제에서는 입력 값의 길이가 500000이라서 vector>도 괜찮을 수 있지만, 입력 값의 길이가 더 커진다면, 아마 map으로 조회를 해야 시간 초과가 안 날 것 같다! map의 조회성능 : O(logN), 삽입, 삭제 성능: O(logN)인접리스트의 조회성능 : O(1), 삽입, 삭제 성능: O(N)map> courses;..

문제 링크https://www.acmicpc.net/problem/5430느낀 점1. 문자열은 왠만하면 문자열로 처리하는 게 좋다.2. 크기가 큰 문자열을 함수의 인자로 받을 때, 참조 변수를 이용하면 메모리 낭비를 줄일 수 있다.3. rbegin, rend를 이용하면 순회를 더 깔끔하게 할 수 있다.#include #include #include #include using namespace std;deque nList;void divide(const string& str){ nList.clear(); string temp = ""; for (auto ch: str) { if (ch == '[') { continue; } el..

문제 링크https://www.acmicpc.net/problem/11663느낀 점이분 탐색의 개념이 아직 정확하게 확립이 안된 것 같은 느낌.. 그리고 등호 하나 반환 값 하나에 따라 결과가 천차만별로 달라지니 이것을 유의해서 이분 탐색 문제를 접근하자!import sysdef min_p(min): s, e = 0, len(dot) - 1 while s

문제 링크https://www.acmicpc.net/problem/7795느낀 점A -> B 집합이라고 했을 때, 경우의 수가 B의 원소의 갯수 ** A의 원소의 갯수가 나오기 때문에 시간 초과가 발생한다.(1 ≤ N, M ≤ 20,000)따라서 A 집합의 원소가 B 집합의 어느 분위수에 해당하는지를 계산하고 그 인덱스를 더해주는 방식으로 구해야 O(NlogN)이 되어서 시간초과가 발생하지 않을 수 있다. 문제를 보면 이것을 생각하기 힘들어서 고생했는데, 분위수, 순서를 구하는데 시간 초과를 피해야한다면 이분탐색으로 접근하면 될 것 같다는 느낌이 들었다. import sysT = int(sys.stdin.readline())for _ in range(T): N, M = map(int, sys.std..

문제 링크https://www.acmicpc.net/problem/4963느낀 점아주 기본 적인 dfs 구현 문제!import syssys.setrecursionlimit(12345678)answer = []while True: w, h = map(int, sys.stdin.readline().split()) if w == 0 and h == 0: break else: count = 0 maps = [] for _ in range(h): maps.append(list(sys.stdin.readline().split())) d = [(-1, 0), (-1, -1), (-1, 1), (0, -1), (0, 1)..

문제 링크https://www.acmicpc.net/problem/2644느낀 점이 문제도 아주 기초적인 dfs 구현 문제 하지만, 이것도 뒤로 돌아가는 과정을 없애주면서 진행해주어야해서 그 부분을 신경써주어야함!import sysimport collectionssys.setrecursionlimit(12345678)def dfs(startV): global visited global count global final_count queue.append(startV) visited.append(startV) while queue: q = queue.popleft() for v in graph[q]: if v not in visit..