will과 would의 차이✅ will → 현재 시점에서의 미래를 의미 (확실성, 강한 의지) ✅ would → 과거 시점에서의 미래를 의미 (불확실성 → 가정, 공손함 등으로 확장) would의 특징기본적으로 will의 과거형이지만,불확실한 상황에서 자연스럽게 가정, 공손함 등에 사용된다 will vs would 예시의미willwould현재에서 미래"I will call you tomorrow." (내일 전화할게.)X과거에서 미래X"He said he would call me." (그가 전화할 거라고 했어.)현재의 가정 (가정법 과거: 현재상황 가정)X"If I had more time, I would travel." (시간이 더 있다면 여행할 텐데.)과거의 가정/추측 (가정법 과거완료: 과거상황 가정..
TLIANGLE PATH 문제 (0,0)부터 시작해서 아래 or 아래우측으로 이동 가능하다이동한 경로의 숫자를 모두 더한 값이최대가 되는 경로와 합을 출력하시오 구현 주의사항- 동적계획법 코드 템플릿동적계획법을 이용한 코드 작성 시에"기저사항 -> 캐시확인 -> 연산" 방식으로 작성하면 편하다 - 함수 반환 타입문제가 원하는 최대가 되는 합즉, 지금까지의 합을 반환하도록 구현하면 된다참고로, 재귀함수 특성 상 위에서 부터 합이 추가되는 것이 아닌끝에서부터 추가 되는 방식이다 (추후 확인 가능) - 기저사항N을 삼각형의 높이라고 가정하고y좌표와 x좌표로 이동을 하는 경우에높이 N-1을 초과하는 y좌표의 이동은 불가능하다그렇기에 y좌표가 N-1이 되면, 자신의 값을 반환하면서 종료해야 한다혹은 y좌표가 N이..
LIS 개념- Sequence(수열)수를 나열한 것을 의미한다ex. 1 9 2 5 7 - Subsequence(부분 수열)기존 수열의 순서는 유지한 채로 일부 숫자를 지우고 남은 수열을 의미한다ex. 기존 수열이 1 9 2 5 7이라는 가정하에1 2 5, 1 9 5 7,...- Increasing Subsequence(순 증가 부분 수열)증가하는 규칙이 지켜진 부분 수열을 의미한다ex. 1 2 5 (O), 1 9 7 (X)- LIS(Longest Increasing Subsequence, 최장 증가 부분 수열)제일 긴 Increasing Subsequence을 의미한다ex. 기존 수열이 1 9 2 5 7이라는 가정하에1 2 5 7 -> length가 4로 가장 길다 LIS 구현 주의사항 with 동적계획..
동적 계획법 (Dynamic Programming, DP)복잡한 문제를 작은 하위 문제들로 나누어 해결하고,그 결과를 저장해 두었다가 재활용함으로써중복 계산을 피하고 효율적으로 문제를 해결하는 알고리즘 설계 기법이다 동적 계획법 조건아래의 두 가지 조건을 모두 만족해야 한다1) 최적 부분 구조 (Optimal Substructure):큰 문제의 최적 해가 작은 하위 문제들의 최적 해를 포함하고 있는 구조2) 중복되는 하위 문제 (Overlapping Subproblems):동일한 하위 문제가 여러 번 반복적으로 나타나는 경우동적 계획법 방식1) Top-Down (재귀 + 메모이제이션):큰 문제에서 시작하여 재귀적으로 하위 문제를 해결하면서 결과를 저장하고메모이제이션을 활용한다 2) Bottom-Up (반..
주의사항미로 맵을 생성하는 경우에Prim 알고리즘을 사용하면 쉽게 맵을 생성할 수 있다 코드에 앞서기본적으로 타일은 WALL(빨강)과 EMPTY(초록)로 구분되어 있다Prim 알고리즘을 적용하기 전에y와 x의 2의 배수 위치에는 모두 WALL로 처리한다이렇게 하면 아래와 같이 된다 먼저 간선정보를 저장할 edges를 만들어준다그리고 랜덤맵을 만들기 위해서edges의 가중치를 랜덤으로 등록해서 만들어준다 그리고 다익스트라처럼 아래와 같은 세팅이 필요하다우선순위큐, 해당 정점이 포함되었는지를 체크하는 added, 해당 정점이 누구에게 발견되었는지를 위한 parent, 해당 정점에 닿는 최소 간선만을 기록하는 best 이렇게 모든 준비가 끝나면먼저 첫 번째 임의의 정점을 시작점으로 하며우선순위 큐에 넣으며 세..
PRIM 알고리즘과 KRUSKAL 알고리즘의 차이KRUSKAL 알고리즘은간선들을 정렬해서 선택하는 방식으로 진행했다PRIM 알고리즘은 간선들을 선택하는 것은 맞지만탐색처럼 하나의 정점에서 시작한다 PRIM 알고리즘과 DIJKSTRA 알고리즘의 차이임의의 하나의 시작점에서간선을 하나씩 선택해 나간다는 점은 동일하다 다익스트라는 현재 지점까지의 비용과 현재 지점부터 비용을합쳐서 계산한다반면, PRIM은 현재 지점에서 부터의 비용만을 체크해서 후보를 선정한다 사실상 코드는 거의 유사하며다익스트라처럼 우선순위큐를 사용한다 추가적으로,둘의 성격은 다르기에 서로 다른 곳에서 사용된다예를 들어서다익스트라는 여러 길 중에 최단경로를 탐색해서 사용한다PRIM은 사이클이 발생하지 않고 최단으로 한 가지 길을 만드는 데 ..
주의 사항미로 맵을 생성하는 경우에Kruskal 알고리즘을 사용하면 쉽게 맵을 생성할 수 있다 코드에 앞서기본적으로 타일은 WALL(빨강)과 EMPTY(초록)로 구분되어 있다Kruskal 알고리즘을 적용하기 전에y와 x의 2의 배수 위치에는 모두 WALL로 처리한다이렇게 하면 아래와 같이 된다 그리고 각 간선들을 vector로 push_back 해주는데여기서 각각 간선들의 가중치를 랜덤 하게 넣어준다 이렇게 준비를 마치면,vector를 sort해서 가중치가 적은 순으로 정렬한다그리고 Disjoint의 Find와 Merge를 이용해서사이클을 방지하며 길을 뚫어주면 된다 구현 코드void Board::GenerateMap_Kruskal(){ for (int32 y = 0; y edges; // edges ..
스패닝트리(ST)최소의 간선으로 모든 정점을 연결하겠다는 것을 의미한다사이클이 발생하지 않는 것이 특징이고간선 개수는 정점개수-1이 된다최소스패닝트리(MST)가중치(비용)가 최소로 되는 스패닝트리를 의미한다KRUSKAL MST 알고리즘Kruskal 알고리즘이란 그리디를 이용하는 것이 특징이다지금 이 순간에 최적인 답을 선택해 결과 도출한다는 것이다 Kruskal 알고리즘의 특징은 아래와 같다1) 지금 이 순간에 가장 작은 비용들을 선택하기2) 사이클은 발생하지 않도록 해야 한다 Kruskal 알고리즘의 내부 동작은 아래와 같다가장 작은 비용들을 선택하기 위해서가중치값이 작은 순으로 정렬을 해놓고 하나씩 선택을 하면 된다사이클 발생 여부를 확인하는 방법은 그룹화(집합) 개념을 이용하면 된다간선 및 정점이 ..
집합이 필요한 경우모든 유저들이 팀번호를 부여받는 경우를 생각해 보자이러한 경우에서 유저 클래스에 teamId가 있을 것이다그리고 팀 동맹 기능이 추가된 경우에 아래와 같이 코드를 작성할 수 있다찾기 연산은 빠르지만 합치기 연산은 O(N)이 문제가 된다이러한 경우에 집합을 사용하면 효율적이다void Example(){ struct User { int teamId; // TODO }; // TODO : UserManager vector users; for (int i = 0; i users[5] users[5].teamId = users[1].teamId; // 1 // 예시 2) teamId==1인 팀과 teamId==2인 팀이 동맹 for (User& user : users) { if (user..
해시테이블배열이나 리스트는 탐색이 매우 느리다반면, 탐색이 빠른 자료구조는 이진탐색트리가 있다이진탐색트리보다 더 빠른 자료구조가 바로 해시테이블이다탐색뿐 아니라 삽입/삭제/탐색 모두 O(1) 소모된다하지만, 그만큼 공간을 많이 차지한다는 것이 단점이다 테이블 개념해시테이블을 알아보기 전 테이블과 해시 개념을 천천히 알아보자테이블이란 아파트의 우편함과 같다비록 공간을 많이 차지하지만, 삽입/삭제/탐색이 빠르다 예를 들어, 아래의 코드처럼vector의 임의접근을 활용한다면userId를 통해 쉽게 탐색을 할 수 있다그러나, 문제는 유저수가 많으면 많을수록 공간을 너무 많이 차지한다는 것이다 void TestTable(){ struct User { int userId = 0; // 1~999 string..
