📌문제 유형: 그래프 이론 https://www.acmicpc.net/problem/11403   📌풀이  문제의 조건을 분석하면, 아래와 같이 볼 수 있다. 1. 방향 그래프 2. i->j로 가는 방법이 있는지를 모든 정점에 대해 알아봐야 함.  이때 한 방향으로 계속 깊게 파고 들어야 하니 DFS가 맞다고 판단했다.  각 정점에 대해서, dfs()를 수행하고 갈 수 있는 정점이면 output 1차원 배열에 저장하면 된다. 하나의 정점 n에 대해 output = [0] * N으로 정의되어 있고, graph[n][i] == 1 (갈 수 있는 길이 있고), output[i] == 0 (아직 방문 안했으면) 그 정점 i에 대해 dfs()를 재시행한다.  이걸 모든 정점에 대해 반복하면 완성 !!  ⭐ 아..

📌문제 유형: 그래프 탐색 (BFS)https://www.acmicpc.net/problem/14940   📌 풀이  전형적인 BFS 문제이다. 단, 시작점이 (0,0) 이 아니라 2 값을 갖고 있는 위치부터라는 점! 따라서 먼저 2의 값을 가진 위치를 찾아야 한다.  그 뒤에 모든 지점까지의 최단거리를 출력하라고 한다. 최단거리는 BFS로 구할 수 있다.  이때 움직일 수 있는 방향이 상하좌우이므로, dx/dy를 선언해 bfs() 안에서 for문을 통해 한 지점이 갈 수 있는 상하좌우 4곳을 살펴볼 수 있도록 한다. 이때 갈 수 있는 곳은 queue에 담는다.  여기서 포인트는, 거리 값을 visited에 누적합으로 표현한다는 점이다.  1. 모든 지점에 대해 visited[i][j] = -1로 초..

📌 문제 유형: DPhttps://www.acmicpc.net/problem/1463   📌 풀이 문제를 읽으면서 딱 눈에 들어오는 것은, 시간 제한이 0.15초 밖에 안된다는 점이다. 그리고 N이 1~10^6이라면, 완전탐색으로는 시간 초과가 날 것이라는 걸 느끼게 된다.  이 상태에서 문제를 좀 더 살펴보자.  3으로 나누어 떨어질 때, 2로 나누어 떨어질 때, 둘 다 아닐때 이렇게 3가지 경우에 대해 연산을 제한해 두고 있다. 이 3개의 연산을 적절히 사용해 연산 횟수를 MIN로 만드려고 한다. 드는 생각들! 1. 3의 배수일 때 (2의 배수는 아님)2. 2의 배수일 때 (3의 배수는 아님) 3. 둘 다 아닐 때 - 1을 뺀다. 4. 6의 배수일 때 ==> 이 경우가 추가되어 고려될 수 있다. ..

📌 문제유형: DP https://www.acmicpc.net/problem/1003   📌 풀이  이 문제에서 포인트는 !!! 시간 제한이 0.25초 밖에 안된다는 점이다. 따라서 재귀함수로 작성하게 되면, 1시간초과에 걸리게 된다.  그 해결 방법은 동적 계획법(DP)에 있다.  즉, 메모제이션을 활용해야 한다. 메모제이션이란 앞서 계산했던 값을 저장해두어, 추후 다시 필요하게 될 때 다시 계산하는 것이 아니라 이미 계산된 값을 불러오는 것이다.  위의 문제는, n에 대한 피보나치 수열이 계산될 때 0과 1이 몇 번씩 필요로 되는가에 있다.  DP를 풀 때 1. 하나의 예제를 가지고 직접 손으로 적어보면서 실마리를 찾는다. 2. 규칙성을 찾아본다. 3. 이를 점화식으로 세워본다. (앞에서 #를 선..

** [한권으로 합격하는 취업 코딩테스트] 책을 참고해 작성했습니다.** 주의점, 기억해야할 것을 위주로 작성합니다.  선형 탐색 Linear Search  - 순차탐색의 다른 말 - 배열에 여러 값들을 넣어 두고, 그 중에서 어떤 값을 찾을 때 반복문을 돌려 하나하나 비교하며 찾는 것 - O(N) 이분 탐색 Binary Search  - 탐색할 부분이 하나만 남을 때까지 탐색 범위를 줄여가는 방식 - 조건: 정렬된 배열- left = 0 , right = len(arr)-1, mid = (left + right) // 2로 하는 게 일반적. - arr[mid] > target 이면 왼쪽 탐색 (right = mid - 1) - arr[mid] - O(logN)* 파이썬 라이브러리 bisect from ..

📌 문제유형: 스택  📌  풀이코드 # 스택에 하나씩 넣는데, 만약 맨 위에 있는 거랑 같은 거면 pop# 그냥 완전탐색.. def solution(s): answer = -1 stk = [] for i in range(len(s)): ''' 스택이 비어있으면 넣고, stk[-1] 이랑 다르면 넣고 다음 문자로 넘어가기 스택이 안 비어있고, stk[-1]이랑 같으면 pop하고 다음 문자로 넘어가기 ''' if not stk: stk.append(s[i]) continue if s[i] == stk[-1]: stk.pop() else: ..