문제 링크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://leetcode.com/problems/3sum/description/?source=submission-noac느낀 점좋은 문제라고 생각했다. 투 포인터 문제 풀이 방식을 익힐 수 있다고 생각했기 때문이다. 하지만, 이전 원소와의 중복을 제거해주지 않으면 시간 초과가 나버리거나 중복으로 인해 정답이 틀리는 고약한 문제였다.. 나는 중복 배열을 없애기 위해 리스트를 만들고 존재하는지를 검사해주었는데, 그것 때문에 시간 초과가 계속 났음..class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: answer = [] nums.sort() for i in range(len(..

문제 링크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)..