초코chip의 코딩 생활

정리배낭 문제목표값(v)를 만족시키는 부분집합 찾기 문제 평범한 배낭 - 골드5 배낭 문제: 목표값을 만족시키는 최적의 부분집합 찾기풀이법:원소의 개수(1~i), 목표값(k)목표값 1~k까지, i번째 원소를 선택한 경우, 선택하지 않은 경우 2가지 경우를 비교하면서 dp 테이블을 채우기if( 채울 수 있는 경우 ) ==>  w[i] dp[i][k] = max( dp[i-1][k](i번쨰 원소를 선택하지 않을 경우), dp[i-1][k - w[i]] + v[i](i번쨰 원소를 선택할 경우) ) if (채울 수 없는 경우) ==> w[i] > kdp[i][k] = dp[i-1][k] (이 경우 i번째 원소를 선택하지 않을 경우만 보면 됨)why?: 왜 i번째 원소를 선택하지 않을 경우가 i-1, k인가?  ..

정리  자료구조 주의사항!!우선순위큐는 삽입, 삭제 시에만 재정렬이 되는거지, 내부의 값을 수정했을때는 정렬이 적용되지 않음이럴땐 건실하게 그냥 리스트 쓰고, 변경했을때 정렬 알고리즘 써라큐, 스택, 우선순위큐 자료구조들은 get을 통한 접근이 불가능하다!이러고 싶으면 링크리스트 써라! 링크리스트는 offer(), poll() 연산 다 지원함remove() 연산을 사용하면 삭제되는 값을 반환해줌 n만큼 이동을 해야하는데, 계속 변동성이 생기는 경우// diff 만큼 이동해야하는데 중간에 빠지는값 떄문에 diff - 빠지는값 만큼 이동해야하는 경우// adjusts란 배열에 빠진 값들을 저장해서 빠진 값들 중에 중간 값이 몇개 있는지 체크 -> 그 값을 적용int diff = t - dq.peekFirst..

정리그래프 탐색바이러스 - 실버3https://www.acmicpc.net/problem/2606 문제 유형:노드 형태의 그래프 형태시작점에 연결된 노드의 개수를 세는 문제노드 관점의 그래프 자료구조를 사용했을떄 dfs/bfs 아무거나 상관x그냥 연결된 모든 노드를 탐방을 하고 연결된 노드 개수를 세는 문제 -> 스택 or 큐에 넣을때마다 count 증가 단지번호붙이기 - 실버1https://www.acmicpc.net/problem/2667 문제 유형: 2차원 배열 형태의 그래프 형태연결된 모든 노드의 개수를 세는 문제즉, 모든 노드를 시작점으로 다 탐색을 해야함 해결책:graph[1][1] ~ graph[n][n]까지 모든 노드를 시작 지점으로 하고 탐색을 진행단, 이미 방문한 노드이거나 탐색 불가 ..

트리 개념 정의: 데이터를 계층적인 구조로 표현할 때 사용하는 자료구조 용어 루트 노드(root node): 부모가 없는 최상위 노드 단말 노드(leaf node): 자식이 없는 노드 크기(size): 트리의 모든 노드 개수(N) 기본적으로 트리 크기가 N이면 간선은 N-1개 깊이(depth): 루트 노드로부터 거리 높이(height): 깊이 중 최댓값 차수(degree): 각 노드의 자식 (간선) 개수 이진 탐색 트리(Binary Search Tree) 개념 정의: 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조 특징: 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 탐색 진행 흐름 시간복잡도: O(logN) 단, 트리 높이가 균등할때만 그럼 방법 if target 값이면 탐색..

기본편 개념 정의: 두 노드의 공통된 조상 중 가장 가까운 조상을 찾는 문제 동작 과정: 모든 노드에 대한 깊이(depth) 계산 최소 공통 조상을 찾을 두 노드를 확인 - LCA(a,b) 연산에 대하여 아래 과정을 반복 먼저 두 노드의 깊이(depth)가 동일하도록 거슬러 올라감 이후 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라감 시간 복잡도: O(N) - 매 쿼리마다 부모 방향으로 거슬러 올라가기 때문에 언제 사용?: m번의 LCA연산으로 총 O(MN) 시간 복잡도가 괜찮을 경우 메모리 여유가 없을 경우 구현 //n: 노드 개수, m: LCA연산 횟수 static int n, m; static int[] parent = new int[n+1]; // 부모 노드에 대한 정보 s..

개념 정의: 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스리지 않도록 순서대로 나열하는 것 즉, DAG(Direct Acyclic Graph): 순환하지 않는 방향 그래프에 대해서만 가능 시간 복잡도: O(V + E) - 노드 개수(V), 간선 개수(E) 동작과정 요약 진입차수가 0인 모든 노드를 큐에 삽입 큐가 빌 때까지 아래 과정 반복 큐에서 원소를 꺼내 해당 노드에서 나가는 간선 그래프에서 제거 새롭게 집입차수가 0이 된 노드를 큐에 삽입 최종적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재 그래프 기본 개념 집입차수(Indegree): 특정 노드로 들어오는 간선 개수 진출차수(Outdegree): 특정 노드에서 나가는 간선..

서로소 집합 자료구조 서로소 집합 정의: 공통 원소가 없는 두 집합 예시) 서로소o: {1,2} {3,4} 서로소x: {1,2} {2,3} 서로소 집합 자료구조 정의: 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하는 자료구조 2가지 연산 지원 합집합(Union): 2개의 집합을 하나의 집합으로 합치는 연산 찾기(Find): 특정 원소가 속한 집합이 어떤 집합인지 알려주는 연산 합집합 연산을 통해, 노드 A와 B를 연결 A와 B의 루트 노드인 A`과 B`을 찾기 A`과 B`을 부모 노드로 설정 모든 합집합 연산을 처리할때까지 1번 연산 반복 진행 흐름 서로소 집합을 합치는 과정은 다음과 같이 진행된다. 예시) if 노드가 1~6번까지 존재하고, 4가지 합치는 연산이 존재하는 경우 1. 부모 테이블..

개념 최단 거리 문제 종류 모든 간선이 양수인 경우 - 다익스트라 알고리즘 음수 간선이 있는 경우 - 벨만 포드 알고리즘 음수 간선 순환이 없는 경우 - 다익스트라 O 음수 간선 순환이 있는 경우 - 다익스트라 X 벨만 포드 알고리즘 시간 복잡도: O(VE) - 다익스트라 알고리즘에 비해 느림 동작과정 간단 요약 출발 노드 설정 & 최단 거리 테이블 초기화 아래 과정을 N-1번 반복 전체 간선 E개를 하나씩 확인 ( 다익스트라는 특정 노드에 붙어있는 간선만 확인함 ) 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신 만약, 음수 간선 순환이 발생하는지 체크하고 싶다면, N-1 반복을 다시 한 번 더 수행 이때, 최단 거리 테이블이 갱신된다면 음수 간선이 존재하는 것 vs 다익스트라..

개념 정의: 그래프 구조에서 가장 짧은 경로를 찾는 알고리즘 다익스트라 알고리즘 개념 정의: 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산하는 알고리즘 최종적으로 각 노드까지의 최단 거리 정보가 저장 시간 복잡도: O(ElogV) : E - 간선 개수, V - 노드 개수 특징: 그리디 알고리즘: 매 상황에서 방문하지 않는 가장 비용이 적은 노드를 선택하여 반복 한 번 처리(방문)된 노드의 최단 거리는 고정 결과 각 노드까지의 최단 거리 정보가 저장 동작과정 간단 요약 출발 노드 설정 & 최단 거리 테이블 초기화 아래 과정 반복 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신 진행 흐름 // 노드의 개..

개념 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 대표적인 그래프 탐색 알고리즘 DFS/BFS 재귀함수(Recursive Function) 자기 자신을 다시 호출하는 함수 스택 구조로 함수들이 쌓임 스택 구조로 함수가 쌓이기 떄문에 스택 자료구조 대신 재귀함수를 이용하는 경우가 있음 모든 재귀함수는 반복문을 이용하여 동일한 기능 구현 가능 재귀 함수는 반드시 종료 조건을 설정 해야함 DFS(Depth-First Search) 깊이 우선 탐색 그래프가 있을때 방문 기준을 문제 조건을 잘 보고 설정 해야함 탐색 노드를 스택에 삽입하고 방문 처리 진행 방문 기준으로 다음 인접 노드를 스택에 넣고 방문 처리 진행 위 과정 계속 코드 주의!) 노드 연결시 양방향 그래프이면 서로 연결을 해줘야함 boolea..