R.silver

코드트리 아이디: parkeb555

Breadth First Search 너비 우선 탐색 가까운 노드부터 탐색하는 알고리즘 큐 자료구로를 사용하는 것이 정석 (인접한 노드를 큐에 넣으면 먼저 들어온 것이 먼저 나가게 되므로 가까운 노드부터 탐색할 수 있다) 사용하는 경우 (유형) 연결된 그래프를 탐색하는 경우 최단 거리(최소 횟수)를 구하는 경우 (현재 노드에서 가까운 곳을 먼저 찾기 때문) 그래프의 규모가 크지 않고 시작 지점으로부터 대상이 멀지 않은 경우 cf) 경로의 특징을 저장하는 경우에는 DFS 사용 (BFS는 경로의 특징을 가질 수 없다) 동작 방식 탐색 시작 노드를 큐에 삽입하고 방문 처리 큐에서 노드를 꺼내 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리 2번을 더 이상 수행할 수 없을 때까지 반복 code ..

문제 2468번: 안전 영역 (acmicpc.net) 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 접근 방식 1. 상하좌우를 돌며 내린 비의 양보다 높은 곳이 있는지 파악한다 -> DFS 활용 2. 높다면 방문처리 한 뒤 return True 3. 낮다면 return False 이 과정을 가장 높은 지역 크기 만큼 반복 (내리는 비의 양) 주의할 점 1. 재귀 함수 범위에 주의하자 # 재귀 함수 범위를 늘려주는 코드 import sys sys.setrecursionlimit(10**7) 2. 제공된 graph를 ..

2667번: 단지번호붙이기 (acmicpc.net) 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 접근 방법 상하좌우를 모두 돌며 집이 연결되어 있는지 확인 -> DFS 사용 1. 노드 == 1이면 0으로 변경하고 상, 하, 좌, 우 확인 후 return True 2. 노드 == 0 이면 return False 3. global 변수를 사용하여 상하좌우 확인할 때 집의 개수 추가 주의 할 점 1. 상하좌우를 확인 할 때 범위를 넘어갈 수 있으므로 미리 예외 처리 하기 2. graph 값 int 로 변환하기 정..

Depth First Search 깊이 우선 탐색 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘 특정 경로로 탐색하다가 특정 상황에서 최대한 깊숙히 들어가 노드를 방문한 뒤, 다시 돌아가 다른 경로로 탐색하는 알고리즘 다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐색하는 방법 BFS 보단 느리다 (단순 검색 속도) 백트래킹과 연관된다 DFS를 사용하는 경우 모든 노드를 방문하고자 할 때 순회를 하고자 할 때 경로에 특징을 저장해야 할 때 검색 대상 그래프가 클 때 cf) 최단거리는 BFS가 유리 동작 방식 탐색 시작 노드를 스택에 삽입하고 방문 처리 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를..

최댓값 → 최솟값을 초깃값으로 최솟값 → 최댓값을 초깃값으로 sys 사용 시스템에서 지정할 수 있는 가장 크고, 작은 값을 활용 mx = -sys.maxsize mn = sys.maxsize float 사용 float을 사용하여 무한대 값을 지정 mx = float('-inf') mn = float('inf') 임의의 값 (999999 등)을 최댓값, 최솟값 등으로 설정하는 것은 가장 좋지 않은 방법이다. 파이썬은 임의 정밀도를 지원하여 사실상 무한대의 값을 지정할 수 있다. 얼마든지 지정한 값 보다 작거나, 큰 값이 들어올 수 있다. 혹은 코테 문제에서 기술되어 있는 제약 조건을 확인한 뒤 기준에 맞추어 최대, 최솟값을 처리하면 된다

Product of Array Except Self - LeetCode Product of Array Except Self - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 자신을 제외한 배열의 곱 제시된 배열에서 자신을 제외한 값들을 곱한 값들을 리턴하는 문제 주의!! 나눗셈 금지 조건 존재 배열의 모든 값들의 곱을 구하고 자기 자신으로 나누는 풀이는 불가! 풀이 옳은 풀이 자기 자신을 제외한 왼쪽 값들의 곱셈 결과와 오른쪽 값들의 곱을 곱하면 올바른 풀이를 ..

Array Partition - LeetCode Array Partition - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 배열 파티션 1 주어진 배열에서 2개의 값으로 이루어진 페어를 생성하고 페어의 값의 최솟값들의 합이 최대가 될 때의 합을 리턴하는 문제 정말로 모든 페어를 구한다 ? -> x 페어의 최소값들의 합이 최대가 되어야 한다는 조건을 이용하여 페어를 구해보자 풀이 오름차순 풀이 2개의 원소를 가진 값들의 최솟값의 합을 구해야 한다 그러나 모든 ..

3Sum - LeetCode 3Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 세 수의 합 입력받은 숫자 배열에서 세 수를 더하여 0이 되는 3수의 조합을 반환하는 문제 풀이 브루트 포스 모든 수를 조합하여 더하여 합이 0이 되는 조합을 찾으면 풀이할 수 있다. # 브루트 포스 # Time Limit Exceeded from typing import List class Solution: def threeSum(self, nums: List[int]) -..

Two Sum - LeetCode Two Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 두 수의 합 더하여 target의 값이 되는 두 값의 인덱스를 반환하는 문제 매우 쉬운 문제이나 여러 가지 방법으로 풀이할 수 있어 코딩 인터뷰에서 높은 빈도로 출제되는 문제이다. 풀이 다양한 방법으로 풀이가 가능한 문제이다. 브루트 포스로 풀이 브루트 포스 (brute-force): 무차별 대입 방식 모든 조합을 다 더해서 일일이 확인해본다면 브루트 포스 방식을 ..