[알고리즘] 문제 모음집

( cf . PC 로 보는게 훨씬 편합니다 )

[ 2022.1.28 ~ 4.1  /  2023.11 ~ 2024.2 /  ]

[예정 : 학교 수업 / 취업 전 ]  

[도움이 될만한 글]
공부할때 어디까지 참고해야 하는가?
https://blog.encrypted.gg/1062
 
[코딩테스트 대비 특강]
https://infossm.github.io/blog/2019/03/07/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EB%8C%80%EB%B9%84-%ED%8A%B9%EA%B0%95/
BFS,DFS,백트래킹 위주로,
 
[전체 문제]
https://github.com/encrypted-def/basic-algo-lecture/blob/master/workbook.md
 

[틀렸을 때 vs 안떠올랐을 때]

 

[틀렸을 때]
배열 크기를 제대로 잡았는가?
int 범위를 벗어나지는 않는가?
정렬되어있다는 조건이 없는데 정렬되어있다고 착각하지 않았는가?
for문 범위를 제대로 잡았는가?
N = 0 or 1일 때 제대로 처리했는가?
시간이 아슬아슬하다면 최적화를 더 할 수 없는가?
[안떠오를 때]
비슷한 문제를 풀어본 적이 있는가?
단순한 방법에서 시작할 수 있을까?
내가 문제를 푸는 과정을 수식화할 수 있을까?
문제를 단순화할 수 없을까?
그림으로 그려볼 수 있을까?
수식으로 표현할 수 있을까?
그래프로 표현할 수 있을까?
문제를 분해할 수 있을까?
뒤에서부터 생각해서 문제를 풀 수 있을까?
순서를 강제할 수 있을까?
특정 형태의 답만을 고려할 수 있을까?

 
 

[만들어야 하는 템플릿 리스트]

fill(벡터 , array 일때)

fill( 시작 위치 , 끝위치 ( last 포함 x ) , 채우고자 하는 값 ) ;

vector 

 

 

순열 , 조합 (next_permutation)
BFS , DFS
(+ 문자열 입력 받기 )
(+ string to int / string 에서 isdigt 로 정수인지 자리별로 확인 / int to string)
(+ 붙어있는 숫자를 배열로 받고싶을때 )
벡터,큐,덱 --> 기본 사용법 정리
도형 rotation 
array rotation( 왼쪽 - 오른쪽 밀기 ) - ex) 시뮬레이션 - 톱니바퀴: https://notepad96.tistory.com/59
STL sort 사용 ( compare 함수 위주로 )
a.erase(unique(a.begin(), a.end()), a.end()); // a에서 중복된 원소를 제거하는 명령
 
 
입력을 받는데 몇개를 받아야하는지 주어지지 않고 더이상 입력을 받지 않을때 입력이 멈추는 상황

 EOF 를 사용하여서 입력을 처리하면 된다. 
https://velog.io/@c-jeongyyun/CPP-EOF-%ED%8C%90%EB%8B%A8%ED%95%98%EA%B8%B0

[C++] EOF 판단하기

 

해시 단원의

<사이버 개강총회> 문제를 참고하자 !

 
배열 안에 벡터를 받고 싶다. 
vector<int> arr[50][50] 으로 사용하면 한 칸 안에 벡터가 설정된다
활용한 문제 : 16235 나무 제텤크

DFS(그래프 단원) 

재귀 DFS  vs 비재귀 DFS vs 재귀 DFS (비재귀 DFS 처럼 사용하기)
 

원래 쓰는 편안한 형태의 DFS

비재귀 처럼 방문하기 위해서 수정한 DFS

 
이를 보면, 이전의 코드에서는 nxt를 스택에 넣은 직후에 바로 방문 여부, 즉 vis[nxt]를 true로 만들어 스택에 각 정점이 무조건 1번씩만 들어가도록 만들었습니다. 반면 지금의 코드는 스택에 넣을 때 방문 표시를 남기는게 아니라 스택에서 값을 뽑은 후에 방문 여부를 true로 만들도록 했습니다. 이렇게 수정하면 우리가 관념적으로 생각하는 DFS와 동작이 일치합니다. 이렇게 구현을 하면 스택 자체에는 각 정점이 무조건 1번씩 들어가지는 않고 여러 번 들어갈 수도 있지만 09번 줄의 처리로 인해 결국 연결된 정점을 보는 작업은 각 정점마다 최대 1번씩만 하기 때문에 시간복잡도는 동일하게 O(V+E)입니다. 만약 실수로 09번 줄을 빼먹는다면 연결된 정점을 보는 작업을 각 정점마다 여러 번 진행할 수 있기 때문에 코드의 시간복잡도가 굉장히 안좋아지거나 무한루프에 빠질 수 있습니다. 이런 경우 제출했을 때 시간 초과가 나거나 스택에 push가 계속 일어나서 메모리 초과가 발생할 수 있으니 조심해야 합니다.
(실제로 시간 차이가 많이 나니까 조심하자 - 11724 번 속도 차이 보면 이해가 됨 )

---

글자색에 따른 복습 기준 

빨강 : 이해 x 복습 o
주황 : 이해 ^ 복습 o
노랑 : 이해o 복습 x 
검정색 : 안푼문제들 
 
 

0. 기초 코드 요령

1267번
2490 <= 미세한 아이디어
 
 

1.배열

문제집 링크
분류                                       문제                      문제 제목                                       정답 코드

연습 문제	10808	알파벳 개수	정답 코드
기본 문제✔	2577	숫자의 개수	정답 코드
기본 문제✔	1475	방 번호	정답 코드
기본 문제✔	3273	두 수의 합	정답 코드, 별해 1
기본 문제	10807	개수 세기	정답 코드
기본 문제	13300	방 배정	정답 코드
기본 문제	11328	Strfry	정답 코드
기본 문제	1919	애너그램 만들기	정답 코드

+) 다시볼때 잘 했나 볼 것, 
3273 --> https://ksh0416.tistory.com/52
ㄴ> 2회차에서는 투포인터로 풀었는데 다시한번 보기
ㄴ> input 으로 int 형 차례대로 받을 때 주의하기.
11328
ㄴ> 문제의 예외 케이스를 생각하지 못한 경우에 이런 실수 계속 나올 수 있음 
 
 

2.연결 리스트

문제집 링크
분류                                       문제                      문제 제목                                       정답 코드

연습 문제	1406	에디터	정답 코드
기본 문제✔	5397	키로거	정답 코드
기본 문제✔	1158	요세푸스 문제	정답 코드, 별해 1, 별해 2

*연결리스트 주의점. 
list.eraser(iter) 사용 할 때 
iter = list.eraser(iter) 이런식으로 사용해야함
(eraser 함수 자체가 그 iter 의 연결리스트를 삭제한 뒤 다음 것을 반환함)
 
 
 
1158
ㄴ> 뭔가 계속 꼬임 , 다시풀면서 한번 할 실수 안하는게 좋을듯 
이런 류의 문제를 자꾸 절음.
erase 반환값 = 다음 iter 값 반환 (  * 주의 )
얘땜에 처음을 어떻게 처리할지 머리가 아파서 구현이 계속 꼬임 근데왜 erase return 값을 생각안했지
 
글고 처음에 절었던 이유가 뭐랄까 좀 너무 쉽게 생각한듯
특히나 리스트 전체 길이가 가변적이기 때문에 그걸가지고 사용하려면 더 주의가 필요함.
 
또 아쉬웠던 점은 , 잘못된걸 알았을때 빨리 수정하지 못한거? 
그냥 여러모로 좀 능력이 부족했던거 같다. 
 
사실 스택으로 풀면 더 빨리 풀 수 있을 것 같기는 한데
 
 
array list   - vecotr - list 
ㄴ> 이거 셋 차이점 및 공통점 비교 다시하기
 
vector = 동적 array
array = 정적 array ( 흔히 arr[100] 이라고 선언하는 - 당연히 vector 도 index 로 참조는 가능하다. )
(연결) list = 리스트 
각 시간복잡도 및 공간복자도 면접전에 다시 확인 ?
 
배열 연결리스트      ==  선형구조
트리, 그래프, 해쉬   == 비선형 구조 
 

[ Restricted Structure ] 

: 특정 위치에서 원소를 빼거나 더할 수 있음
1. 스택
2. 큐
3. 덱

 

3.스택

문제집 링크
분류                                       문제                      문제 제목                                       정답 코드

연습 문제	10828	스택	정답 코드
기본 문제✔	10773	제로	정답 코드
응용 문제✔	1874	스택 수열	정답 코드
응용 문제✔	2493	탑	정답 코드
응용 문제	6198	옥상 정원 꾸미기	정답 코드
응용 문제	17298	오큰수	정답 코드
응용 문제(풀긴품)	3015	오아시스 재결합	정답 코드
응용 문제(아예 못품)	6549	히스토그램에서 가장 큰 직사각형	정답 코드

1. 스택 문제의 특징 파악

스택을 사용하는 문제는 대부분 다음과 같은 특징을 가집니다:

• 가장 최근에 추가된 요소를 먼저 처리해야 할 때 (LIFO: Last In, First Out)
• 특정 조건이 만족될 때까지 요소를 저장해두고, 조건을 충족하면 제거하는 과정이 필요할 때
• 과거의 상태를 기억하거나 참조해야 할 때

예시 문제 유형:

• 괄호의 유효성 검사 (올바른 괄호, 중첩 검사 등)
• 오큰수 (특정 조건을 만족하는 가장 가까운 값 찾기)
• Histogram 문제 (직사각형 최대 면적 계산)
• 탑 문제 (레이저 송신처럼 신호 수신)

2. 스택 문제 접근 방법

1. 문제의 요구사항 분석
   • 문제에서 이전 요소를 기준으로 현재 요소를 처리해야 한다거나, 과거의 상태를 추적해야 한다면 스택이 적합한지 의심해 봅니다.
   • "가장 가까운", "직전의", "연속된"과 같은 표현이 나오면 스택을 생각해볼 수 있습니다.
2. 스택을 사용해야 하는 이유 정의
   • 문제를 스택으로 풀 수 있는 이유를 명확히 정의합니다.
   • 예: 탑 문제에서는 레이저가 왼쪽으로 발사되고 가장 가까운 높은 탑이 필요하므로, 스택으로 과거 상태를 추적할 수 있습니다.
3. 스택을 언제 사용하고 비울지 정의
   • 요소를 스택에 추가하는 조건과, 스택에서 제거(pop)하는 조건을 명확히 정의합니다.
   • 예: 높이가 낮은 탑은 현재 탑에 의해 가려지므로 제거해야 함.
4. 시간 복잡도 고려
   • 스택의 특성상 각 요소는 한 번 push되고 한 번 pop되므로, 보통 O(N)O(N)O(N) 시간 복잡도로 설계할 수 있습니다.
   • 만약 중첩 루프를 사용하거나 스택이 제대로 갱신되지 않으면 비효율적인 코드가 될 수 있습니다.

 
3015 
: 얘는 처음에 그냥 너무 어렵게 풀어버린 것 같기도 하다. 얼추 생각은 비슷했던 것 같은데 더 좋은 방향이 있었다..
시간을 굉장히 많이 썼는데 잘 못풀어서 좀 아쉽다. 
문제를 보고 스택을 떠올리는 것도 만만치 않은데 디테일한 구현도 어려웠고 long long 써야하는 부분이 정답 부분에 있다는 것도 좀 많이 어려웠던 것 같다. 
pair<int,int> 에서 뒤쪽 int 에 지금까지 이 원소 + 이전 원소들이 볼수 있는 총합을 저장하는게 아니라
그냥 단순하게 같은 크기의 원소를 저장하고 , 이전원소들이 볼 수 있는 총합(더 작은 원소들) 은 ans 에 그때그때 더해주는 방식으로 하는게 더 좋았다. 
 
 

4.큐

문제집 링크
분류                                       문제                      문제 제목                                       정답 코드

연습 문제	10845	큐	정답 코드
기본 문제✔	18258	큐 2	정답 코드, 별해 1
기본 문제✔	2164	카드2	정답 코드

상아탑	1966	프린터 큐	https://www.acmicpc.net/problem/1966

 
 
 

5.덱

문제집 링크
분류                                       문제                      문제 제목                                       정답 코드

연습 문제	10866	덱	정답 코드
기본 문제✔	1021	회전하는 큐	정답 코드
응용 문제✔	5430	AC	정답 코드, 별해 1
응용 문제	11003	최솟값 찾기	-

 
최솟값 찾기 , AC - 둘다 파이썬으로만 구현 ( cpp 로 구현 힘듬 )
<최솟값 찾기> https://ksh0416.tistory.com/54
 
 

6.스택의 활용(수식의 괄호 쌍)

문제집 링크
분류                                       문제                      문제 제목                                       정답 코드

연습 문제	4949	균형잡힌 세상	정답 코드
기본 문제✔	3986	좋은 단어	정답 코드
기본 문제	9012	괄호	정답 코드
응용 문제✔	10799	쇠막대기	정답 코드
응용 문제✔	2504	괄호의 값	정답 코드

 
2504: 이런거 구상 할 때 뭔가 너무 까다롭게 생각하는 것 같으면서도.. 으음.. 
 

7. BFS

문제집 링크
분류                                       문제                      문제 제목                                       정답 코드

연습 문제	1926	그림	정답 코드
연습 문제	2178	미로 탐색	정답 코드
연습 문제	7576	토마토	정답 코드
연습 문제	4179	불!	정답 코드
연습 문제	1697	숨바꼭질	정답 코드
기본 문제✔	1012	유기농 배추	정답 코드
기본 문제✔	10026	적록색약	정답 코드
기본 문제✔	7569	토마토	정답 코드
기본 문제✔	7562	나이트의 이동	정답 코드
기본 문제✔	5427	불	정답 코드
기본 문제	2583	영역 구하기	정답 코드
기본 문제	2667	단지번호붙이기	정답 코드
기본 문제	5014	스타트링크	정답 코드
기본 문제	2468	안전 영역	정답 코드
기본 문제	6593	상범 빌딩	정답 코드
응용 문제✔	2206	벽 부수고 이동하기	정답 코드
응용 문제✔	9466	텀 프로젝트	정답 코드
응용 문제✔	2573	빙산	정답 코드
응용 문제✔	2146	다리 만들기	정답 코드, 별해 1
응용 문제✔	13549	숨바꼭질 3	정답 코드, 별해 1
응용 문제✔	1600	말이 되고픈 원숭이	정답 코드
응용 문제	13913	숨바꼭질 4	정답 코드
응용 문제	14442	벽 부수고 이동하기 2	정답 코드
응용 문제	16933	벽 부수고 이동하기 3	정답 코드
응용 문제	16920	확장 게임	정답 코드
응용 문제	11967	불켜기	정답 코드
응용 문제	17071	숨바꼭질 5	정답 코드
응용 문제	9328	열쇠	정답 코드
응용 문제	3197	백조의 호수	정답 코드
응용 문제	20304	비밀번호 제작	-

 
(2146)
BFS 의 시간복잡도(1번) 은 O(N^2) 
기존 방법보다 더 좋은 방법이 있다. 
특히 좀 더 개선해야 할 부분은 동시에 큐에 넣기( 토마토 , 불 문제와 동일 )
그러고 동시에 만나는 점을 계산하기위해 구현하는 능력 ! 
 
(1600)
문제에 대한 아이디어 및 계산
특히 변수가 여러개거나 x,y 가 바뀌거나 , 세개 변수 이용할때 특히나 변수 순서 조심할 것......
 
(벽 부수기 시리즈 )
이전의 문제들로 인해서 한차원을 더 추가해서 계산해야 하는 건 알았지만, BFS 의 본질적인 이해.
여기서는 정확히 "너비 탐색" 에서는 당연히 동차 일때 같은 위치에 있으면 가장 먼저왔다는 의미를 어느순간 퇴색시켜 버린 것 같은데, bfs에 대해서 다시 이해해볼 필요가 있다. 
 
 
(5427)
https://ksh0416.tistory.com/manage/posts/
--> m,n 헷갈리지 말기 ( 자주틀림)
 

 

(출처)

https://infossm.github.io/blog/2019/03/07/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EB%8C%80%EB%B9%84-%ED%8A%B9%EA%B0%95/

코딩테스트 대비 특강

 

 
 

(11967 번)

#include <bits/stdc++.h>
using namespace std;

#define X first;
#define Y second;

int board[105][105]; // 켜져있는지
int vis[105][105];   // 방문했는지


int dx[4] ={1,-1,0,0};
int dy[4] ={0,0,1,-1};

int n,m;
int x,y,a,b;

vector<pair<int,int>> adj[105][105];
queue<pair<int,int>> q;

bool OOB(int a, int b) { return a < 1 || a > n || b < 1 || b > n; }


int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> m;
  
  for(int i =0;i<m;i++){
    cin >> x >> y >> a >> b;
    adj[x][y].push_back({a,b});
  }

  board[1][1] = 1;
  vis[1][1] = 1;
  q.push({1,1});

  
  while(!q.empty()){
    auto cur = q.front(); q.pop();
    int x = cur.X;
    int y = cur.Y;

    // 1,1 에서 켤 수 있는 스위치 확인 - (1,2) (1,3)
    for(auto e:adj[x][y]){
      int nx = e.X;
      int ny = e.Y;
      if(vis[nx][ny]==1) continue;
      // 인접칸에 방문했는가?
      for(int i=0;i<4;i++){
        int vx = nx+dx[i];
        int vy = ny+dy[i];
        if(OOB(vx,vy)) continue;
        if(vis[vx][vy]==0) continue;
        // 방문 했을 경우
        vis[nx][ny]=1;
        q.push({nx,ny});
      }
      board[nx][ny] = 1; // 킬수 있는 스위치 체크 
    }

    // 만약 새로 킨 (board 가 1이 된) 스위치를 방문 할 수 있는지 체크 (다시 BFS)- 시간 복잡도에는 큰 영향이 없음

    for(int i = 0 ; i <4 ;i++){
      int nx = x+dx[i];
      int ny = y+dy[i];
      if(OOB(nx,ny)) continue;
      if(vis[nx][ny]) continue; 
      // 여기가 제일 크리티컬하게 생각하지 못한부분,
      // 뭐랄까 이후에 방문할 수 있을 경우를체크 할때 현재 지점만 기준으로 체크하면 된다. 

     // 왜냐하면 BFS 이기 때문에 결국 순차적으로 접근(그니까 너비 탐색으로 결국은 멀어도 나중에는 결국 순서대로 접근 할 수 있기 때문이다... 아직도 너비 탐색에서 이런걸 헤메네) 

      if(board[nx][ny]==0) continue;
      vis[nx][ny]=1;
      q.push({nx,ny});
    }
  }

  int ans = 0;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) ans += board[i][j];
  cout << ans;

  
  

  
}

 

8. DFS

개인적.	1987	알파벳

 
1987 : DFS 로 나와서 좀 당황하기도 했고.. 백트래킹으로 풀까 생각했었는데 좀 아쉽다. 다시풀어볼것.
 

9.재귀 

문제집 링크
분류                                       문제                      문제 제목                                       정답 코드

연습 문제	1629	곱셈	정답 코드
연습 문제	11729	하노이 탑 이동 순서	정답 코드
연습 문제	1074	Z	정답 코드
기본 문제✔	17478	재귀함수가 뭔가요?	정답 코드
기본 문제✔	1780	종이의 개수	정답 코드
기본 문제✔	2630	색종이 만들기	정답 코드
기본 문제✔	1992	쿼드트리	정답 코드
응용 문제✔	2447	별 찍기 - 10	정답 코드, 별해 1
응용 문제✔	2448	별 찍기 - 11	정답 코드
응용 문제	14956	Philosopher’s Walk	정답 코드

 
연습문제 3개 --> 다시 한번씩 봄.
1992 쿼드트리 --> 다시 ( 완 )
 
<재귀>

재귀 

절차 지향적 사고 대신에 귀납적으로 생각해서 풀기

ㄴ> 1에서 작동확인(base line )

ㄴ> k 에서 확인 -> k+1 에서 확인

 

재귀 - 메모리 구조 stack 에 쌓임. --> 메모리 양 조심하기

 
 
 

10.백트래킹 

문제집 링크
분류                                       문제                      문제 제목                                       정답 코드

연습 문제	15649	N과 M (1)	정답 코드
연습 문제	9663	N-Queen	정답 코드
연습 문제	1182	부분수열의 합	정답 코드
기본 문제✔	15650	N과 M (2)	정답 코드, 별해 1
기본 문제✔	15651	N과 M (3)	정답 코드
기본 문제✔	15652	N과 M (4)	정답 코드
기본 문제✔	15654	N과 M (5)	정답 코드
기본 문제✔	15655	N과 M (6)	정답 코드
기본 문제✔	15656	N과 M (7)	정답 코드
기본 문제✔	15657	N과 M (8)	정답 코드
기본 문제✔	15663	N과 M (9)	정답 코드
기본 문제✔	15664	N과 M (10)	정답 코드
기본 문제✔	15665	N과 M (11)	정답 코드
기본 문제✔	15666	N과 M (12)	정답 코드
기본 문제✔	6603	로또	정답 코드, 별해 1
기본 문제	1759	암호 만들기	정답 코드, 별해 1
응용 문제✔	1941	소문난 칠공주	정답 코드
응용 문제✔	16987	계란으로 계란치기	정답 코드
응용 문제	18809	Gaaaaaaaaaarden	정답 코드
응용 문제	1799	비숍	정답 코드

 
 

복면산	https://www.acmicpc.net/problem/15811	학교 스터디 문제

 
 
9663 번 N-Queen : 좌표를 그런식으로 계산 할 수 있다는 걸 예전에 한번 해봣던 거 같은데 그때보다 더 좋게 풀어갔음. 좋은 아이디어인듯 ( 자주 쓰일수도있을거같고 ) 
ㄴ> 1년정도 이후에 풀어보니까 생각이 잘 나가지고 지웠음.
 
NEXT_PARAMETER 사용해서 N과 M 시리즈 다시 구현해보기  : 1,2,5,6 번
ㄴ> 완 
ㄴ> cf. https://taehun0933.tistory.com/18
 
1941
얘는 안보고 꼭 풀어보고 싶어서 체크해둠. 현재진행형.
----
결국 아이디어 보고 구현은 내가 직접함.
뭔가 단계별로 짤라서 생각하면 생각보다 풀이를 떠올리기는 쉬웠던 것 같은데 좀 아쉽다.
이게 문제를 너무 오래 고민했음에도 불구하고 생각이 내 밖을 벗어나지 못하는 것으로 보아... 아직좀 부족한듯 싶다
 
구현 주의점 : 초기화 안하면 답이 이상하게 나옴조심할것
 
 
 
+ (강의) - 백트래킹에서 시간복잡도와 관련해서.

A1에 퀸을 놓으면 바로 B1, B2에 퀸을 놓는 경우는 해볼 필요가 없어지는 것과 같은 상황을 백트래킹에서 가지치기라고 부르는데 가지치기가 빈번하면 백트래킹의 시간복잡도를 가늠하기가 많이 힘듭니다. 그렇기 때문에 문제를 보고 시간복잡도가 가늠이 잘 안가는데 N이 많이 작아 백트래킹으로 푸는 문제일 것 같다는 생각이 들면 직접 구현한 뒤 가장 시간이 오래 걸릴만한 케이스를 직접 돌려봐서 시간 초과가 나는지 안나는지를 보면 됩니다. 이 문제라면 N = 14를 넣어보는 것입니다. 만약 시간이 애매하면 최대한 최적화할 수 있는 것들을 찾아서 고치고 제출을 하면 됩니다. 시간을 로컬에서 측정할 때에는 반드시 Release 모드로 실행을 해야 하고 보통은 서버가 로컬보다 빠르다는 점도 기억하시면 좋습니다. Release 모드가 무엇인지는 구글에 한 번 검색해보세요.

 
 
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
 

11.시뮬레이션 <-- ing

문제집 링크
분류                             문제             문제 제목                                                                             정답 코드

연습 문제	15683	감시	정답 코드
연습 문제	18808	스티커 붙이기	정답 코드
연습 문제	12100	2048 (Easy)	정답 코드
연습 문제	15686	치킨 배달	정답 코드
기본 문제✔	11559	Puyo Puyo	정답 코드
기본 문제✔	14891	톱니바퀴	정답 코드
기본 문제✔	14499	주사위 굴리기	정답 코드
기본 문제✔	13335	트럭	정답 코드
기본 문제✔	16985	Maaaaaaaaaze	정답 코드
기본 문제✔	14503	로봇 청소기	정답 코드
기본 문제✔	3190	뱀	정답 코드
기본 문제✔	14500	테트로미노	정답 코드, 별해 1
기본 문제✔	13460	구슬 탈출 2	정답 코드
기본 문제✔	14502	연구소	정답 코드, 별해 1
기본 문제✔	14888	연산자 끼워넣기	정답 코드, 별해 1
기본 문제✔	14889	스타트와 링크	정답 코드
기본 문제✔	14890	경사로	정답 코드
기본 문제✔	15684	사다리 조작	정답 코드
기본 문제✔	15685	드래곤 커브	정답 코드
기본 문제	17281	⚾	정답 코드
기본 문제	5373	큐빙	정답 코드
기본 문제	16234	인구 이동	정답 코드
기본 문제	16235	나무 재테크	-
기본 문제	16236	아기 상어	정답 코드
기본 문제	17140	이차원 배열과 연산	-
기본 문제	17141	연구소 2	정답 코드
기본 문제	17142	연구소 3	정답 코드
기본 문제	17143	낚시왕	-
기본 문제	17144	미세먼지 안녕!	-
기본 문제	4991	로봇 청소기	-
기본 문제	16986	인싸들의 가위바위보	정답 코드
기본 문제	17779	게리맨더링 2	-
기본 문제	17837	새로운 게임 2	-
기본 문제	17822	원판 돌리기	-
기본 문제	17825	주사위 윷놀이	정답 코드
기본 문제	19235	모노미노도미노	정답 코드
기본 문제	20061	모노미노도미노 2	-
기본 문제	19236	청소년 상어	-
기본 문제	19237	어른 상어	-
기본 문제	19238	스타트 택시	-
기본 문제	20055	컨베이어 벨트 위의 로봇	-
기본 문제	20056	마법사 상어와 파이어볼	-
기본 문제	20057	마법사 상어와 토네이도	-
기본 문제	20058	마법사 상어와 파이어스톰	-
기본 문제	16637	괄호 추가하기	-
기본 문제	17070	파이프 옮기기 1	정답 코드, 별해 1
기본 문제	17135	캐슬 디펜스	정답 코드
기본 문제	17136	색종이 붙이기	-
기본 문제	17406	배열 돌리기 4	-
기본 문제	17471	게리맨더링	-
기본 문제	17472	다리 만들기 2	-
기본 문제	15898	피아의 아틀리에 신비한 대회의 연금술사	-
기본 문제	21608	상어 초등학교	-
기본 문제	21609	상어 중학교	-
기본 문제	21610	마법사 상어와 비바라기	-
기본 문제	21611	마법사 상어와 블리자드	-
기본 문제	23288	주사위 굴리기 2	-
기본 문제	23289	온풍기 안녕!	-
기본 문제	23290	마법사 상어와 복제	-
기본 문제	23291	어항 정리	-

 

구시현발

감시 & 스티커 붙이기 - 첫 구현 문제라서 그런지 좀 계속 절어서 다시한번 언젠가 구현해보는게 좋지 않을까 싶다. 
구현은 어떻게든 가능하나... 더 좋은 방법이 계속 존재한다
 
감시 (15683)
: 너무 막품.. , 백트래킹 말고 그냥 반복문으로 풀기 , 4진수의 활용? ( 방향 )--> 다른 문제에 한번 더나왔는데 그떄도 잘 못썼던 것 같음
 
스티커 붙이기 (18808)
: 도형회전 , break (테크닉?) , 구현할떄 디테일
 
치킨배달
: 구현은 쉬웠으나, permutation 에서 좀 절었고, 이런 문제가 나오면 빨리 풀어서 넘기는게 좋음. 구현 속도를 좀 더 빠르게?
 
Puyo Puyo
(코드) --> 개선할 점 적어둠

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second

int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
string s[15];

int vis[15][15];
int ans = 0;

void down(){  // 여기도 일단 맘에 안듬 왜이렇게 짰지
  for(int j = 0 ; j< 6 ;j++){
    for(int i=11 ; i>=0 ; i--){
      if(s[i][j] == '.'){
        // 자신보다 위에있는 원소 찾아서 내리기
        for(int k = i ; k>=0 ; k--){
          if(s[k][j]=='.') continue;
          else{
            swap(s[k][j] , s[i][j]);
            break;
          }
        }
      } 
    }
  }
}




int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  // 1. 블럭 내리기
  // 2. 블럭 터트리기 계산하기 -> BFS
  // 3. 멈추는 경우 -> BFS QUEUE 가 비었을때

  for(int i = 0; i<12 ; i++){
    cin>> s[i];
  }

  
  bool ispuyo = false;
  do{
    ispuyo = false;
    down();
    
    for(int j = 0 ; j < 6 ; j++){
      for(int i=11;i>=0;i--){
          queue<pair<int,int>> q;
          if(vis[i][j]==1) continue;
          vector <pair<int,int>> v; 
          char c = s[i][j];
          q.push({i,j}); v.push_back({i,j});
        
          vis[i][j] = 1;   
        
          while(!q.empty()){
            auto e = q.front(); q.pop(); 
            for(int dir = 0 ; dir < 4 ; dir++ ){
              int nx = e.x + dx[dir];
              int ny = e.y + dy[dir];
  
              if(nx<0 or nx>=12 or ny<0 or ny>=6 ) continue; // 좌표 디테일 확인
              if(vis[nx][ny] == 1) continue;
              if(s[nx][ny]=='.' or s[nx][ny]!=c ) continue; // S[nx][ny]=='.' 조건이 없으면 시간초과로 터짐
              vis[nx][ny] = 1;
              q.push({nx,ny});
              v.push_back({nx,ny});
            }
          }

        // 좀 더 조건을 타이트하게 쓰는 것도 좋을듯? 근데 너무 헷갈려..;; --> 메모하면서 확인~
          for(int j = 0 ; j < 14; j++){
            for(int i = 0 ; i< 14; i++){
              vis[i][j] = 0;
            }
          }
  
          if(v.size() >= 4){
            for(auto e : v){
              s[e.x][e.y] = '.';
            }
            ispuyo = true;
          }
          // 만약에 cnt + 4 이상이라면 --> 삭제 해주기  <----> cnt 로 따로 세주는게 아니라 v.size 로 바로 ~
        
        }
      
      }

      // 제발 조건 잘읽기
      if(ispuyo) ++ ans;
  }while(ispuyo);
  

  

  cout << ans;
  
  
  
}
 
 

톱니바퀴 : STL rotation 있음 
cf.
https://notepad96.tistory.com/59

 rotate 함수는 인자로 (시작 반복자, 첫 위치로 올 Forward 반복자, 종료 반복자) 를 받는다.
- 왼쪽으로 2칸 씩 회전시키기 위해서는 2번 째 인수로 v.begin() + 2를 준다.
- 오른쪽으로 3칸 씩 회전시키기 위해서는 2번 째 인수로 v.end() - 3을 주었다. 
 
주사위 굴리기 :
주사위 굴릴 때 (i+k) % 6 처럼 다시 돌아오는걸(?) 표현 할 수 있다. 
너무 당연한건데 부분 부분을 고민 할 때 좀 매몰되는 듯? 
+ 풀긴 풀었지만은 구현 할 때 공통적인 부분을 풀어서 작성하는게 아니라 좀 묶어서 작성해야되는데 ( 일괄적으로 함수를 통해서?) 이런 부분이 아직도 좀 아쉽다  뭔가 짜보고 나서 아 이렇게 하면 될 것 같은데? 라는 생각이 드는데 막상 
시작할때 그런 발상이 조금 저는 것 같다. 좀 더 생각을 한 후에 구현하도록 하자
 
 
13335 다리:
직관적인 구현인데 그냥 구현을 못해버림........;
 
14503 트럭
진짜 아 board[][]= 이여야하는데 == 으로 써서 계속틀림 이거 붙잡고 3시간을 썼네 아 열받아

14500 테크도미노
일단 나는 백트래킹으로 풀었는데 이 방법 말고 시뮬레이션으로도 풀어보기
답 코드를 보면 좀 참고할 점들이 있는데
1. vector 이중문 사용 ( 더 필요하면 여기서 참조 https://leeeegun.tistory.com/m/3 )
2. 일렬로 된 걸 2차원으로 바꿀때  아이디어 총 길이가 16이고 4 by 4 로 변환할 때 : {i/4,i%4} 와 같이 사용하면 x,y, 좌표처럼 나타 낼 수 있다
 
사다리 조작
음.. 하자마자 작성해서 생각이 잘 안나는데 고민을 했던 부분이 일단
1. "다리" 가 놓인 부분을 어떻게 표현할 것인가. ( vector <pair<int,int>> ? 2d array? ) --> 이게 가장 큰 고민이였다. 나도 2d array 로 해야할 것 같아서 선택하긴 했는데 확신이 없어가지고 중간에 답을 한번 체크했다. 이부분이 좀 아쉽다. 
 
+절었던 부분
처음에 코드를 작성했을때 return 으로 바로바로 나오게끔 설정을 해서 작성을 했었는데 
조금만 더 생각해보면 그렇게하면 다음 최소를 거치지 않을 수도 있기 때문에 min 을 사용해서 계산해야한다
쓸데없는 계산을 하고싶지 않은 마음은 알겠지만 틀린생각이다. 
 
경사로
역대급으로 꼬임 ..
얘는 어디서 틀렸는지 부터 시작해서 좀 자세하게 따로 포스팅을 해야될듯 아 진짜 머리아프네 
아이디어는 너무 쉬운데 걍 구현에서 꼬여버리고 
구현하다 보니까 생각에서 틀린점이 있고
그러다보니까 계속 꼬이고 
막상 구현을 해보니까? 개복잡함
심지어 아직 어디서 틀린지 잡지도 못했고.. 화나네 그냥
 
 
드래곤 커브 
https://ksh0416.tistory.com/98

어디서 생각이 꼬였는지 좀 더 상세히 적어 두었다. 
다시 풀때도 한번 참고하자
 
⚾
 음.. 오랜만에 풀어서 일단 백트래킹이 생각이 잘 안났다.. 이후에는 괜찮았던 것 같아 보여도
아직도 구현에서 좀 헤매는것 같다 시간을 많이 썼다
여러모로 풀만한 문제였던 것 같은데 못푸니까... 다음에는 꼭 풀자..
 
나무 제테크
1.배열 안에 벡터 선언하는법
vector<int> arr[50][50] --> arr[x][y] 한칸이 vector 로 선언 되어 있는 것임
2. 배열 erase 
배열 erase 할때 시작 지점은 인덱스 ( 순서 )
첫번째 원소부터 삭제하고 싶으면 (0이면) begin()
두번째 원소부터 원하면 begin()+1
 
아기상어
https://ksh0416.tistory.com/104
너무 오래 고민해서 따로 글도 써놨다.. 다시풀때는 코드를 간결하게 푸는걸 목적으로 하자

12. 정렬 I

문제집 링크
문제 분류문제문제 제목정답 코드

기본 문제	2750	수 정렬하기	정답 코드
기본 문제	2751	수 정렬하기 2	정답 코드
기본 문제	10989	수 정렬하기 3	정답 코드
기본 문제	11931	수 정렬하기 4	정답 코드
기본 문제	15688	수 정렬하기 5	정답 코드
기본 문제	10814	나이순 정렬	정답 코드
기본 문제	11650	좌표 정렬하기	정답 코드
기본 문제	11651	좌표 정렬하기 2	정답 코드, 별해 1

 
max_element 사용 방법 :  https://atomic0x90.github.io/c++/2021/07/31/c++-max-element-min-element.html#google_vignette

1. max_element(start, end)를 이용하면 [start, end) 범위 중에 가장 큰 값의 iterator를 반환한다.
2. *max_element(start, end)를 이용하면 [start, end) 범위 중에 가장 큰 값의 value를 반환한다.
3. min_element(start, end)를 이용하면 [start, end) 범위 중에 가장 작은 값의 iterator를 반환한다.
4. *min_element(start, end)를 이용하면 [start, end) 범위 중에 가장 작은 값의 value를 반환한다.

정렬 종류
1. Merge sort - O(NlgN) 
cf. stable sort 사용함.: https://velog.io/@cookncoding/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%9C%EB%85%90-Stable-Sort-Inplace
 
2. quick sort -  O(NlgN)
- 추가적인 메모리를 사용하지 않음( in - place sort )
- 배열안에서 자리만 바꾸기 때문에 cache hit rate 가 높음
 
- 만약에 STL 을 사용 못할때 quick sort 말고 merge sort 사용할 것 
최악의 경우(이미배열이 정렬되어있는경우) 시간 복잡도가 O(N^2) 되어 버리기 때문
STL 에서는 quick sort 를 사용하는데 이때
피벗 랜덤설정 , 피벗 후보 3개 정해서 중간값으로  , 최악의 경우에도 O(NlgN )을 보장하기 위해 일정 깊이 이상에서는 힙sort 로 변환  --> introspective sort 라고 함
 

 

13.정렬 II 

문제집 링크
문제 분류문제문제 제목정답 코드

연습 문제	1431	시리얼 번호	정답 코드
연습 문제	11652	카드	정답 코드
기본 문제✔	5648	역원소 정렬	정답 코드
기본 문제✔	1181	단어 정렬	정답 코드
기본 문제✔	2910	빈도 정렬	정답 코드
기본 문제	10814	나이순 정렬	정답 코드
기본 문제	11656	접미사 배열	정답 코드
기본 문제	10825	국영수	정답 코드
응용 문제✔	7795	먹을 것인가 먹힐 것인가	정답 코드, 별해 1

1181 단어정렬 (블로그 정리) : 문자열 - 배열 처리 cpp 이용해서 ( 더 깔끔하게 할 수 있음 / cmp 설정 / erase함수 / 문자열 비교 등) 
 
STL sort 사용법 : 

 
 

14.다이나믹 프로그래밍 <--ing

문제 분류문제문제 제목정답 코드

연습 문제	1463	1로 만들기	정답 코드
연습 문제	9095	1, 2, 3 더하기	정답 코드
연습 문제	2579	계단 오르기	정답 코드, 별해 1, 별해 2
연습 문제	1149	RGB거리	정답 코드
연습 문제	11726	2×n 타일링	정답 코드
연습 문제	11659	구간 합 구하기 4	정답 코드
연습 문제	12852	1로 만들기 2	정답 코드
기본 문제✔	1003	피보나치 함수	정답 코드
기본 문제✔	1932	정수 삼각형	정답 코드
기본 문제✔	11727	2×n 타일링 2	정답 코드
기본 문제✔	2193	이친수	정답 코드
기본 문제✔	1912	연속합	정답 코드
기본 문제✔	11055	가장 큰 증가 부분 수열	정답 코드
기본 문제✔	11053	가장 긴 증가하는 부분 수열	정답 코드
기본 문제✔	9461	파도반 수열	정답 코드
기본 문제✔	14501	퇴사	정답 코드, 별해 1
기본 문제✔	15486	퇴사 2	정답 코드
기본 문제✔	10844	쉬운 계단 수	정답 코드
기본 문제	2748	피보나치 수 2	정답 코드
기본 문제	2240	자두나무	정답 코드, 별해 1
기본 문제	14002	가장 긴 증가하는 부분 수열 4	정답 코드
기본 문제	2156	포도주 시식	정답 코드, 별해 1
기본 문제	15988	1, 2, 3 더하기 3	정답 코드
기본 문제	2302	극장 좌석	정답 코드
기본 문제	11052	카드 구매하기	정답 코드
기본 문제	9465	스티커	정답 코드
기본 문제	11057	오르막 수	정답 코드, 별해 1
기본 문제	2293	동전 1	정답 코드
기본 문제	1904	01타일	정답 코드
기본 문제	1788	피보나치 수의 확장	정답 코드
기본 문제	4883	삼각 그래프	정답 코드
응용 문제✔	9251	LCS	-
응용 문제✔	1699	제곱수의 합	정답 코드
응용 문제✔	9084	동전	정답 코드
응용 문제✔	1915	가장 큰 정사각형	정답 코드
응용 문제✔	10942	팰린드롬?	정답 코드
응용 문제✔	9655	돌 게임	정답 코드
응용 문제✔	2011	암호코드	정답 코드
응용 문제	2294	동전 2	정답 코드
응용 문제	2133	타일 채우기	정답 코드
응용 문제	1520	내리막 길	정답 코드
응용 문제	9657	돌 게임 3	정답 코드
응용 문제	11660	구간 합 구하기 5	정답 코드
응용 문제	2482	색상환	정답 코드

 
 DP 푸는 과정
1. 테이블 정의하기
2. 점화식 찾기
3. 초기값 가정하기 
 
구현?DP?그리디? => 언제 적재적소에 사용할 수 있는지 좀 헷갈림.

마지막으로 정리를 해보겠습니다. 코딩테스트에서 DP 문제가 나오면 오늘 문제들을 풀면서 느끼셨듯이 보통은 구현이 쉽습니다. 그래서 풀이를 찾아내기만 하면 아주 편하게 문제를 넘길 수 있는데 테이블을 잡고 식을 세우는게 쉽지 않습니다. 또 사실 연습이 부족하면 주어진 문제가 DP로 풀 수 있는 문제라는 것 자체를 눈치채지 못할 수도 있습니다. 그러면 어떻게 하면 되냐라고 했을 때 그냥 진짜 많이 풀면서 테이블을 잡고 식을 세우는 과정을 반복학습하면 됩니다. 처음엔 식이 잘 안잡혀서 풀이를 찾아보는 일이 많겠지만 별의별 희한한 테이블과 점화식을 많이 접해보고 나면 어느샌가 문제를 마주했을 때 감각적으로 테이블을 잡고 점화식을 세우게 되는 자신을 볼 수 있을 것입니다. DP는 양이 정말 많은만큼 잊을만하면 한 두 문제씩 꾸준하게 풀어두면 좋습니다. 그럼 고생 많으셨습니다.

 
 
Prefix Sum :  구간합 구하기에 사용 되는 아이디어, 다른 문제 중간중간에 녹아들어갈 때도 있다.
 
14501 퇴사: 
1. 뒤에서부터 시작하기 ( 뭔가 어색하다고 느낌. => 아직도 어색한데.. 음..)
2. 정의 : i번째 에서 상담을 시작했을때 최대값 <-- 이게 1번이랑  아이디어가 좀 헷갈리는 것 같은데 
'시작' 을 뒤에서부터 계산한다고 생각하니까 머리에서 거부하는 것 같다,,, 얜 꼭  다시 풀어봐야 할 듯?
 
 포도주 시식 , LCS ,제곱수의 합 : 아 뭔가 잘 안된다
그냥 dp 가 발상하기가 좀 어렵기도 하고 처음이라 많이 헤매는듯 
포도주시식 : 어디까지 내가 고려해야 하는지 헷갈림 -> 1번 테이블 정의하기에서 부터 꼬여서 계속 뒤에 생각하는게 어려웠던 것 같다. https://yabmoons.tistory.com/512 ( 다시봐도 모르겠으면 참조 )
 
LCS : 아직푸는중
 
제곱수의 합: 뭔가 이것도 알것같으면서 자꾸 꼬인다
 
2240 자두나무 :
2d 배열로 풀만한데
3d 배열 풀이를 보니까 확실히 dp 이면서 3d 배열이면 좀 난이도가 급상승하고 
내가 3d 배열 dp 문제를 많이 안접해보기도 했고 어려워해서 나중에 한번쯤 다시 보면서 풀어볼 만한것 같다. 
 

15.그리디 <-- ing

문제집 링크
문제 분류문제문제 제목정답 코드

연습 문제	11047	동전 0	정답 코드
연습 문제	1931	회의실 배정	정답 코드
연습 문제	2217	로프	정답 코드
연습 문제	1026	보물	정답 코드
기본 문제✔	11399	ATM	정답 코드
기본 문제✔	2457	공주님의 정원	정답 코드
기본 문제✔	1541	잃어버린 괄호	정답 코드
기본 문제✔	11501	주식	정답 코드
기본 문제✔	1744	수 묶기	정답 코드
기본 문제	2847	게임을 만든 동준이	정답 코드
기본 문제	1439	뒤집기	정답 코드
기본 문제	11000	강의실 배정	정답 코드, 별해 1
기본 문제	15903	카드 합체 놀이	정답 코드, 별해 1
응용 문제✔	2170	선 긋기	정답 코드, 별해 1
응용 문제✔	1700	멀티탭 스케줄링	정답 코드
응용 문제	8980	택배	정답 코드
응용 문제	7570	줄 세우기	정답 코드

 

단어수학 ( 상아탑 시즌2)	https://www.acmicpc.net/problem/1339
강의실 배정	https://www.acmicpc.net/problem/11000

 
그리디 :  코테에 자주 나오는 유형이 아니긴한데..
대략 그럴 것 같다는 느낌만 가지고 바로 구현해서 통과한 후 넘어갈 수도 있습니다. 하지만 제가 굳이 번거로운 증명을 하고 가려는 이유는 비록 실제 코딩테스트에서는 논리적으로 완벽한 증명을 직접 할 일은 없겠지만 증명 과정을 살펴보면 그리디 풀이를 떠올렸을 때 그 풀이가 올바른지 머릿속으로 생각하는데 도움을 받을 수 있고 그리디 풀이의 반례를 잡아내는 능력을 기를 때도 도움이 되기 때문에 그렇습니다. 
 

강의 초반부에도 말했지만 코딩테스트에서는 그리디 문제를 못 푸는 것 보다 오히려 그리디로 푸는 문제가 아닌데 그리디로 풀 수 있다고 착각하는걸 더 조심해야 합니다. 그래서 다양한 그리디 문제를 풀면서 어떤 식으로 그리디 풀이를 찾아갈 수 있는지 잘 익혀보고, 실제 코딩테스트나 대회에서는 본인의 그리디 풀이에 너무 매몰되어서 시간을 다 집어넣지는 않도록 주의합시다.
 
2457 공주님 정원 :
우리가 풀었던 아이디어 ( 회의실 배정 ) 에서 한가지 조건을 추가해서 문제를 풀면 된다. 
아이디어는 빨리 떠올렸 던 것 같은데 구현에서 살짝 애를 먹었다. 
 
이게뭔가 중간에 날짜를 4.16 -> 416 이런식으로 바꿔서 계산하는게 더 편하는 생각이 들었는데 
그냥 코드 짠 것도 있고 뭐해가지고 그냥 밀고 그대로 vector<pair< pair<int,int> , pair<int,int> >> v; 로 밀고 나갔는데 
중간에 수정하는게 좀 더 코드가 깔끔했을 것 같기는 하다. 
 
추가로 예외처리할때 문제도 좀 잘 읽자. 
+ while for if 문들어갈때 {} 많이 쓰게 되는데 정리할 방법이 좀 필요한 것 같다. 자꾸 이런것 때문에 늦어지는 느낌이 있다. 
 

 

16.수학 ( 다시 들어야 됨)

문제집 링크
문제 분류문제문제 제목정답 코드

연습 문제	1978	소수 찾기	정답 코드
연습 문제	1929	소수 구하기	정답 코드
연습 문제	11653	소인수분해	정답 코드
연습 문제	6064	카잉 달력	정답 코드
연습 문제	11050	이항 계수 1	정답 코드
연습 문제	11051	이항 계수 2	정답 코드
기본 문제✔	15894	수학은 체육과목 입니다	정답 코드
기본 문제✔	4796	캠핑	정답 코드
기본 문제✔	2960	에라토스테네스의 체	정답 코드
기본 문제✔	1193	분수찾기	정답 코드
기본 문제✔	4948	베르트랑 공준	정답 코드
기본 문제✔	1676	팩토리얼 0의 개수	정답 코드
기본 문제✔	9613	GCD 합	정답 코드
기본 문제	2292	벌집	정답 코드
기본 문제	2869	달팽이는 올라가고 싶다	-
기본 문제	10610	30	정답 코드
기본 문제	6359	만취한 상범	-
기본 문제	10250	ACM 호텔	-
기본 문제	1456	거의 소수	-
기본 문제	2839	설탕 배달	-
기본 문제	17103	골드바흐 파티션	-
기본 문제	2312	수 복원하기	-
기본 문제	9020	골드바흐의 추측	정답 코드
기본 문제	5347	LCM	-
응용 문제✔	1476	날짜 계산	정답 코드
응용 문제✔	1011	Fly me to the Alpha Centauri	정답 코드
응용 문제✔	1038	감소하는 수	-
응용 문제✔	1057	토너먼트	정답 코드
응용 문제✔	2004	조합 0의 개수	정답 코드
응용 문제✔	1292	쉽게 푸는 문제	정답 코드
응용 문제✔	1790	수 이어 쓰기 2	-
응용 문제✔	3036	링	-
응용 문제	1735	분수 합	-
응용 문제	3343	장미	-
응용 문제	1963	소수 경로	정답 코드
응용 문제	1747	소수&팰린드롬	정답 코드, 별해 1
응용 문제	1256	사전	-
응용 문제	2089	-2진수	정답 코드
응용 문제	1019	책 페이지	-

 
 

17.이분탐색 <--ing

문제집 링크
문제 분류문제문제 제목정답 코드

연습 문제	1920	수 찾기	정답 코드, 별해 1
연습 문제	10816	숫자 카드 2	정답 코드, 별해 1
연습 문제	18870	좌표 압축	정답 코드, 별해 1
연습 문제	2295	세 수의 합	정답 코드
연습 문제	1654	랜선 자르기	정답 코드
기본 문제✔	10815	숫자 카드	정답 코드
기본 문제✔	1822	차집합	정답 코드
기본 문제✔	16401	과자 나눠주기	정답 코드
기본 문제✔	2805	나무 자르기	정답 코드
기본 문제✔	18869	멀티버스 Ⅱ	-
기본 문제✔	2467	용액	정답 코드, 별해 1
기본 문제✔	3151	합이 0	-
기본 문제	14921	용액 합성하기	-
기본 문제	1253	좋다	-
기본 문제	2143	두 배열의 합	정답 코드
응용 문제✔	2473 -투포인터로 풀기	세 용액	정답 코드
응용 문제✔	2110	공유기 설치	-
응용 문제✔	7453	합이 0인 네 정수	-
응용 문제	12015	가장 긴 증가하는 부분 수열 2	-
응용 문제	2512	예산	-
응용 문제	1477	휴게소 세우기	-

 
( 추가로 풀어볼만한 문제들 )

	세 용액	https://www.acmicpc.net/problem/2473	용액 + 합이0 문제
	사격	https://www.acmicpc.net/problem/31264	(보라매 컵 대회문제)
모자이크	https://www.acmicpc.net/problem/2539	-> 모범 답안

1. lower_bound , upper_bound 의 사용법 ( 의외로 자주 헷갈리니 정리해 둘것 )

https://velog.io/@chuu1019/c-lowerbound-upperbound-%ED%86%BA%EC%95%84%EB%B3%B4%EA%B8%B0

[c++] lower_bound, upper_bound 톺아보기

 

2. 벡터 혹은 배열의 unique STL 사용법 
Unique : 배열 이 되어 있는 상태에서 중복을 제거한 배열의 마지막을 return 해 준다. 하지만 이걸로는 충분하지 않고 
erase 를 사용해야 삭제를 해준다. 

sort(uni.begin(),uni.end())
Uni.erase(unique(uni.begin(),uni.end()))
이런식으로 사용하면 uni vector 에 중복이 삭제된 값을 받게 된다.
 

---

이분탐색 STL 
https://m42-orion.tistory.com/m/69
 
Parametric search
 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

세 수의 합 (2295) : 
시간복잡도를 n^4 -> n^3 -> n^2logN 
이렇게 계단식으로 줄일 수 있는 아이디어를 뽑아 낼 수 있는 문제이다.  종만북에서도 이런식으로 아이디어를 생각해 볼 수 있다고 했는데 
그런 문제중에 가장 대표적인 문제가 아닌가 싶다
 
좌표압축, 멀티버스:
결을 같이 하는 문제이다. 큰 어려움은 없긴했는데 lower_bound 랑 binary_search 둘중에 멀써야 할지 몰라가지고 처음에 헷갈렸다. 그리고 멀티버스 문제를 좀 더 깔끔하게 풀 수있는데 이건 포인터 개념으로 좀 더 쉽게하는거라.. 다시안풀어봐도 될 수도 있다. 일단은 다시풀면 좋으니까 체크해둔다.

합이0:
세 숫자+중복 제거 조건으로 어떻게 해야 하는지 고민을 좀 오래했는데
잘 못 떠올려서 다시한번 풀어보면서 복기해야될 것 같다 
 
세 용액:
생각을 좀 잘못해서 코드를 다 짜고도 애를먹었다. 그리고 더 애를 먹은 부분이 있는데..
 abs 때문에 오버플로가 걸리면서 터지는데 해결방법은 아래 링크에 참조해 두겠다
https://www.acmicpc.net/board/view/105847
 
 

(완료)+ 강의 마지막부분 parametric search 들어야함
 + 참고 - 이분탐색 헷갈리지 않게 구현하기 
https://www.acmicpc.net/blog/view/109
 
 

이분 탐색(Binary Search) 헷갈리지 않게 구현하기

17.투 포인터 <--ing

문제집 링크
문제 분류문제문제 제목정답 코드

연습 문제	2230	수 고르기	정답 코드
연습 문제	1806	부분합	정답 코드
기본 문제✔	1644	소수의 연속합	정답 코드
기본 문제✔	2003	수들의 합 2	정답 코드
응용 문제✔	13144	List of Unique Numbers	정답 코드
응용 문제✔	22862	가장 긴 짝수 연속한 부분 수열 (large)	정답 코드
응용 문제✔	2531	회전 초밥	정답 코드
응용 문제✔	20922	겹치는 건 싫어	정답 코드
응용 문제	2461	대표 선수	-
응용 문제	2283	구간 자르기	-
응용 문제	20366	같이 눈사람 만들래?	-

회문	https://www.acmicpc.net/problem/17609

투포인터 문제는 많은 경우 이분탐색으로도 풀 수 있다. 

딱히 특별한 건 없고 그냥 아이디어만 잘 떠올리면 될듯?
라고 생각하자마자 문제를 좀 많이 헤맸는데 그래서 다시 강의를 보면서 정리하면서 처음에 잘못 생각했던 점들을 적어보겠다. 
(처음)
일단 st , en 가 따로 움직이는데 for(int st = 0 ; ~ ~ ) 로 시작하는 투포인터가 어색하다고 느꼈는데 내가 계속해서 생각하던 투포인터는 뭐랄까 st en 을 계속갱신하면서 해나가는 형태로 while 문이 익숙하다보니까 자꾸 걸려 넘어졌다. ( 이걸 뭐 어떻게 표현해야 할지 모르겠다;) 아무튼 나는 알아볼수있으니까.... 
 
(수정후)
 
 
(문제들을 풀면서 느낀점)
1. while 문 안 en 의 멈춤 조건을 설정하는게 어렵다
ㄴ> 디테일하게 봐줘야 하는데 익숙하지 않아서 좀 어렵고 엄청 짜증나는 작업이 한두개가 아니다
투포인터 풀면서 내가 while 문이나 반복문 안에서 변수 변화에 대해서 다시금 생각하게 되었다
문제를 풀면 풀수록 더 까다롭게 느껴지는데 앞으로는 신경을 좀 더 써야 할 듯 싶다.

---

 조금 있다가 연습 문제를 같이 보면 더 이해가 잘 되겠지만, 아무튼 배열에서 원래는 이중 for문으로 탐색을 해야한다면 O(N2)입니다. 그런데 포인터 2개를 두고 그 포인터를 잘 움직여서 O(N)에 해결하는게 투 포인터 알고리즘입니다. 여기서 포인터라고 하는건 C에서 사람들을 굉장히 괴롭게 했던 int*와 같은 포인터는 아니고, 그냥 커서라고 생각을 하면 됩니다. 그러면 왜 이렇게 시간복잡도를 줄일 수 있는거냐면, 이중 for문에서는 i = 0일 때 j가 0부터 n-1까지 돌고, i = 1일 때 j가 0부터 n-1까지 돌고, 이와 같이 각 i에 대해서 j가 0부터 n-1까지 돕니다. 그리고 이 과정에서 i = 0일 때 계산하면서 얻은 정보가 i = 1일 때에 전혀 쓰이지가 않습니다. 그런데 투 포인터에서는 i = 0일 때 계산하면서 얻은 정보를 i = 1일 때 활용합니다. 그 정보가 포인터의 이동으로 나타납니다.
 
근데 투 포인터 알고리즘이 실제 구현을 할 때 조금 애로사항이 있습니다. 가장 많이 실수하는게 인덱스 하나 차이로 어긋나는건데, 이를테면 0-indexed 기준으로 a[n]은 절대 참조를 하면 안되는 값입니다. 그런데 뭔가 반복문 탈출 조건을 잘못 줘서 en의 값이 n이 된 이후에도 a[en] 값을 참조한다던가 하는 일을 저지르기가 쉽습니다.
 
 
 
cf. 이분탐색의 시간 복잡도는 o(nlogn) - 투포인터의 시간 복잡도는 o(2n) --> st,en 이 배열을 한번 돌때까지 진행하기 때문

---

회전초밥 : 투포인터 말고 슬라이딩 윈도우로 풀었는데.. 내 풀이보다 좀 더 좋은 풀이가 많은 것 같아서 다음번에는 좀 더 괜찮게 풀고싶다.

 

 

18 .해시

문제집 링크
문제 분류문제문제 제목정답 코드

연습 문제	7785	회사에 있는 사람	정답 코드
연습 문제	1620	나는야 포켓몬 마스터 이다솜	정답 코드
기본 문제✔	13414	수강신청	정답 코드
기본 문제✔	17219	비밀번호 찾기	정답 코드
기본 문제✔	9375	패션왕 신해빈	정답 코드
기본 문제	16165	걸그룹 마스터 준석이	정답 코드
기본 문제	11478	서로 다른 부분 문자열의 개수	정답 코드
기본 문제	19583	싸이버개강총회	-
응용 문제✔	20166	문자열 지옥에 빠진 호석	-
응용 문제✔	1351	무한 수열	-

 
익숙하지 않은 STL 이라서 적응할 시간이 좀 필요할 것 같긴하다. 그거랑 별계로 문자열 지옥에 빠진 호석 문제는 어려워보이긴한다 
 
무한수열 -> 재귀를 안했더니 또 뭔가 이상하게 했다
갑자기 의문이 들어서 for 문으로 구현했는데 처음에 
이게 왜 재귀랑 시간복잡도가 같다고 생각했는지 모르겠네,,,심지어 메모라이제이션 써야겠다고도 처음에 생각했는데
여러모로 좀 배운걸 늦게 생각해내니까 아ㅜ쉽네
 

---

해시 충돌 회피
1) chaning
2) open addressing 
linear probing = 충돌시 1칸 옮기는 방법
장점 = cache hit rate 가 높다
단점 = clustering 이 생겨 성능에 영향을 줄 수 있다. 
 
quardratic probing = 충돌 발생 시 오른쪽으로 1,3,5,,, 칸씩 이동하는 방식
장점 - cache hit rate 가 나쁘지 않다 , clustering 을 어느 정도 회피 할 수 있다
단점 - 해시 값이 같을 경우 여전히 clustering 이 발생한다
 
double hasing = 충돌 발생시 이동할 칸의 수를 새로운 해시 함수로 계산하는 방식
장점 - clustering 을 효과적으로 피할 수 있다
단점 - cache hit rate 가 낮다

stl 사용법

위 unorder_set 은 원소가 중복이 안되지만
 
아래의 unordered_multiset 은 중복이 가능하다.
이때 조심해야 할 것은 erase 를 쓰면 중복된 모든 함수를 지우기 때문에
아래 09 번째 줄 처럼 사용하면 원소를 하나만 지울 수 있다.
 

 

map

마지막은 unordered_map입니다. unordered_map은 저희가 카드 번호를 키로 사용해서 사람의 이름을 찾았듯, 키에 대응되는 값을 찾아주는 STL이고 보면 알겠지만 인터페이스를 되게 편하게 만들어놨습니다. 맨 처음 선언을 할 때 키의 자료형과 값의 자료형을 명시하고, find, erase랑 range-based for로 iteration 도는 것만 익히고 나면 그냥 마치 배열인데 인덱스가 0, 1, 2, 3, ... 이렇게 작은 범위 내의 정수로 제한되는게 아니라 string을 쓸 수도 있고, 아주 큰 정수나 음수도 담을 수 있는 느낌으로 쓸 수 있습니다. 코드는 한 번 살펴보시고, 07번째 줄을 보면 m["hi"] = -7; 이라고 했을 때 새로운 ("hi", -7)이 추가된게 아니라 기존에 있던 123이란 값을 덮어쓴 것에서 볼 수 있듯 지금은 중복 키가 허용이 안됩니다. 반면 unordered_multimap이라고 해서 중복 키를 허용하는 STL도 있습니다. 근데 저는 이 unordered_multimap을 유용하게 쓴 적이 진짜 단 한번도 없었어서 그냥 소개를 안드렸습니다. 아마 여러분들도 unordered_map은 많이 쓰더라도 unordered_multimap은 딱히 쓸 일이 없을 것으로 보입니다.

 

 
 

19.이진 검색 트리

문제집 링크
문제 분류문제문제 제목정답 코드

연습 문제	7662	이중 우선순위 큐	정답 코드
연습 문제	1202	보석 도둑	정답 코드
기본 문제✔	21939	문제 추천 시스템 Version 1	정답 코드
기본 문제✔	23326	홍익 투어리스트	정답 코드
응용 문제✔	21944	문제 추천 시스템 Version 2	정답 코드, 별해 1
응용 문제✔	19700	수업	-
응용 문제	1539	이진 검색 트리	-

 
 

 

 
 
그냥 데이터를 배열이나 연결 리스트에 저장하면 되지 왜 굳이 이진 검색 트리를 써서 저장하는건가 하는 의문이 자연스럽게 들 수 있는데, 이진 검색 트리를 활용하면 insert, erase, find, update를 모두 O(lg N)에 처리할 수 있습니다. 예를 들어 배열에서 insert는 제일 뒤에 붙이면 되니 O(1)이라고 해도 erase는 배열 중간에 있는 원소가 제거될 상황이 나올 수 있으니 O(N)입니다. find, update 또한 전부 O(N)입니다. 그런데 이진 검색 트리는 저 연산들이 전부 O(lg N)이기 때문에 erase/find/update가 빈번하다면 이진 검색 트리를 활용할 수 있습니다. 그런데 여기까지만 보면 해시는 비록 충돌때문에 성능이 안 좋아질 수 있지만 기본적으로 저 4개의 연산이 O(1)이니까 그냥 해시가 이진 검색 트리의 상위 호환이 아닌가 하는 생각을 할 수 있습니다.

 
다행히 그렇지는 않고 해시에는 없는 이진 검색 트리의 강력한 또 다른 특성은 원소가 크기 순으로 정렬된다는 점에 있습니다. 예를 들어 해시에 1, 3, 5, 7, 9를 넣어뒀다고 해보겠습니다. 그런 상황에서 5보다 큰 최초의 원소가 무엇인지를 알고 싶습니다. 그러면 해시에서는 이 연산을 효율적으로 수행할 방법이 아예 없습니다. 해시라는 구조 자체가 원소를 크기 순으로 저장하는 자료구조가 아니기 때문입니다. 반면 이진 검색 트리에서는 5보다 큰 최초의 원소가 무엇인지를 O(lg N)에 알아낼 수 있습니다. 그렇기 때문에 insert, erase, find, update 등이 빈번하면서 동시에 뭔가 원소의 대소와 관련한 성질이 필요할 경우에는 이진 검색 트리를 사용해야 합니다.

 
 

 

그렇기 때문에 이진 검색 트리가 편향되면 그걸 해결해줄 필요가 있습니다. 이러한 트리를 자가 균형 트리(Self-Balancing Tree)라고 부르고 대표적으로 AVL 트리, Red Black 트리가 있습니다. 둘 중에서 AVL은 구현이 조금 쉬운편인데 성능 자체는 Red Black 트리가 더 좋아서 STL에 있는 이진 검색 트리는 Red Black 트리를 가지고 구현되어 있습니다.
 
진짜 간단하게 원리를 설명드리면 지금 이 그림처럼 뭔가 불균형이 발생했을 때 트리를 꺾어버립니다. 이러면 불균형을 없앨 수 있습니다. 아주 간단하게 설명하면 이런거고, 둘 중 어느 하나라도 어떻게 동작하는지를 알고 나면 드디어 실제로 써먹을 수 있는 이진 검색 트리를 구현할 수 있어서 설명을 드리고 싶긴 한데 문제는 방법이 너무 복잡합니다. 삽입/삭제가 일어날 때 마다 불균형을 확인해야 하는데 각 정점의 자식이 0개/1개/2개일 때 이런 식으로 케이스를 나눠서 각각 방식을 설명해야 하고 뭐 여러가지로 쉽지가 않습니다. 그래서 자가 균형 트리가 무엇이고, 왜 필요한지, 그리고 아주 대략적으로나마 구현이 어떤 식으로 이루어지는지만 안걸로 만족하고 자세한건 설명을 생략하겠습니다. 이렇게 편향성을 해소해주는 자가 균형 트리를 사용할 때 비로소 이진 검색 트리에서 삽입, 검색, 삭제가 모두 O(lg N)이 됩니다.

 

 
먼저 set부터 소개를 해보겠습니다. 14번째 줄 이전의 내용은 unordered_set이랑 차이가 없습니다. 단 이진 검색 트리는 내부적으로 원소가 크기 순으로 저장이 되어있긴 합니다. 그런데 15번째 줄부터 나오는 저 부분이 set이 unordered_set과 차별화되는 점입니다. unordered_set에서는 "-40보다 크면서 가장 작은 원소가 무엇인가?" 라는 문제를 풀기 위해서는 그냥 그냥 모든 원소를 다 살펴보는 방법 밖에는 없었습니다. 반면 set에는 원소가 정렬되어 있기 때문에 O(lg N)에 가능합니다. 코드를 보시면 iterator가 원소를 가리키고 있고 해당 원소에서 prev나 next나 advance와 같은 멤버 함수를 이용해서 좌우로 움직일 수 있습니다. begin()은 처음 원소의 iterator를 반환하고 end()는 마지막 원소의 한칸 뒤의 iterator를 반환합니다. end가 한 칸 뒤의 iterator를 반환하는 것도 그렇고 저 iterator 자체도 vector, list 등에서 이미 나왔던거라 그렇게 낯설 것 같지는 않습니다. 그리고 사실 C++11 이상부터는 15번째 줄처럼 굳이 저 뭔가 쓰기 싫게 생긴 자료형을 다 쓰는 대신에 그냥 17, 20, 21번째 줄처럼 auto를 쓰면 됩니다. 한 번 코드를 눈으로 잘 봐두고 lower_bound, find 같은 멤버 함수도 잘 기억했다가 써먹기 좋은 문제가 나오면 잘 써먹어보도록 합시다.
 

 
lower_bound는 이분탐색 단원에서 나왔던 그 lower_bound랑 기능이 동일한데, 특정 원소가 삽입되어도 오름차순 순서가 그대로 유지되는 가장 왼쪽 위치를 나타냅니다. lower_bound가 있다는 것에서 짐작할 수 있겠지만 순서가 그대로 유지되는 가장 오른쪽 위치를 나타내는 upper_bound랑, lower_bound와 upper_bound 쌍을 반환하는 equal_range도 그대로 있습니다. 이 멤버 함수들의 시간복잡도를 보면, set에서는 진짜 그냥 온갖 연산이 다 O(lg N)이라고 생각하면 됩니다. size, end, begin 함수는 그냥 멤버 변수로 가지고 있던 값을 바로 반환할테니 O(1)이지만 insert, erase, find, lower_bound, next, prev 등은 모두 O(lg N)입니다. 단 advance의 경우에는 한 칸을 움직이는게 O(lg N)이기 때문에 advance(it, 100); 이라고 하면 이게 그냥 O(lg N)이 아니고 한 칸 움직이는 O(lg N) 연산을 100번 수행하는 상황이란건 기억을 하고 계셔야 합니다.
 

 

다음으로는 multiset입니다. unordered_multiset과 마찬가지로 원소의 중복이 허용되는 STL이고 그 점만 유의해서 보면 set이랑 큰 차이 없이 이해가가능합니다. 10번째 줄과 같이 erase를 하면 15를 1개 지우는게 아니라 모든 15를 지운다는 점을 유의하시고, 또 16번째 줄을 보시면 find 멤버 함수가 있는데 set에서의 find 멤버 함수와는 상황이 좀 다릅니다. set에서는 어차피 1개니까 있으면 그 원소의 iterator를 반환하면 되고 없으면 s.end()를 반환하면 됐는데, multiset에서는 같은 원소가 여러 개 있을 수 있습니다. 그러면 그 중에서 뭘 반환해줄지가 좀 애매한데 표준을 보면 그 중에서 아무거나 준다고 되어 있습니다. 다만 저희가 주로 쓰는 gcc에서는 제가 확인을 해보니 적어도 제가 실험을 해본 버전들에서는 항상 제일 먼저 등장하는 원소의 iterator를 주긴 했다만 이건 구현에 달린 문제이고 기본적으로는 여러 개가 있을 때에는 그 중에서 아무거나 준다는 점을 기억하도록 합시다.
 
만약 제일 먼저 등장하는 원소의 iterator가 필요한 상황이라면 find를 쓰는 대신 lower_bound를 써야 합니다. 그리고 it2를 보면 100의 upper_bound는 100이 들어갔을 때 오름차순이 유지되는 가장 오른쪽 위치니까 시작점(-10)으로부터 3칸 떨어진 곳, 즉 multiset의 마지막 원소가 있는 곳에서 한 칸 오른쪽으로 간 곳입니다. 여기는 ms.end()입니다. 그리고 여기는 가리키는 원소가 없기 때문에 만약 *it2를 출력하게끔 했다면 런타임 에러가 발생합니다. iterator가 end()를 가리키고 있는데 거기의 값을 참조하도록 하는건 set/multiset/map에서 런타임 에러를 유발하는 주요 원인중 하나라 이런 실수를 하지 않도록 조심하고 또 런타임 에러가 발생했다면 이 이유를 생각해볼 수 있습니다. 또한 unordered_multiset과 마찬가지로 count 함수는 O(lg N)이 아닌 O(원소의 개수)만큼의 시간이 걸림에 유의하세요.
 

마지막은 map입니다. 이 친구도 key로 value를 찾는 인터페이스가 잘 되어있는 STL이고 이미 prev, next, lower_bound, upper_bound 이런건 앞에서 설명을 잘 했어서 14번째 줄만 한 번 보고 가겠습니다. it1이 가리키는 대상은 pair<string, int>이기 때문에 it1->first, it1->second로 key와 value를 가져올 수 있습니다.
 
그리고 알아두시면 피가 되고 살이 될 정보가 있는데, 첫 번째로 만약 문제를 풀다가 뭔가 set, map 느낌의 성질이 필요하면서 특히 lower_bound나 prev, next 이런걸 사용해야만 풀리는 문제라면 꼭 STL set, map으로 해결을 해야 합니다. 반면에 그냥 key로 value를 빠르게 찾거나, 원소의 삽입/검색/삭제만 빠르게 처리를 해주어야 할 경우라면 STL unordered_set, unordered_map을 사용해도 상관이 없습니다. 그리고 실제로 속도를 비교해보면 평균적으로는 set/map보다 unordered_set/unordered_map이 빠릅니다. 그럼에도 불구하고 저는 set/map을 쓰는걸 선호를 하는데, 왜 그렇냐면 unordered_set/unordered_map은 평균적으로는 빠를지언정 충돌이 얼마나 빈번한가에 따라서 속도의 저하가 발생할 수 있어서 항상 빠르게 동작한다는 보장을 할 수 없다는 치명적인 단점이 있습니다. 물론 그런 일이 흔치는 않겠지만 출제자가 의도적으로 충돌을 유발하는 데이터를 넣어둔다거나 하면 각 연산이 O(1)이 아닌 O(N)에 동작하게 되어서 꼼짝없이 시간초과가 발생합니다. 반면 set/map은 평균적으로는 느릴지언정 항상 O(lg N)이기 때문에 데이터가 어떻게 들어있던간에 실행 시간이 어느 정도인지 가늠을 할 수 있습니다. 그래서 여러분들도 unordered_set/unordered_map보다는 set/map을 쓰는게 더 좋지 않을까 하는 생각을 아주 살짝 해봅니다. 이건 제가 100% 옳은건 아니고 여러분이 판단하셔서 정하면 됩니다.
 
두 번째로 이진 검색 트리의 연산은 확인한 것 처럼 O(lg N)이 되는건 맞지만 같은 O(lg N)중에서도 상당히 느립니다. 저희가 지금까지 배운 알고리즘들 중에서 시간복잡도에 로그가 붙는걸 생각해보면 이분탐색이나 정렬 알고리즘을 떠올릴 수 있습니다. 이분탐색에서는 lg N번의 연산 동안 인덱스의 값만 왔다갔다하면 되지만 이진 검색 트리에서는 새로운 노드를 동적할당으로 생성하거나, 편향성을 해소해주기 위해 노드를 뗐다 붙였다 하거나 하는 식으로 다소 무거운 연산을 해야 할 일이 많습니다. 그렇기 때문에 이분탐색이나 정렬에서는 N = 100만이라고 할 때 N개의 데이터에서 이분 탐색을 N번 하거나 정렬을 해서 O(NlgN)짜리 연산을 수행한다고 하면 크게 부담스럽지 않게 통과가 되겠다 하고 짐작을 할 수 있는 반면 이진 검색 트리에서는 N = 100만일 때 N개의 데이터에서 연산을 N번 수행해야 한다고 하면 조금 부담이 됩니다. 상황에 따라 차이는 좀 있지만 보통 저런 상황에서 1초 제한이라고 하면 간당간당할 수가 있습니다. 그래서 이진 검색 트리는 O(lg N)이지만 좀 느리다는걸 기억해두면 좋습니다. 또 이진 검색 트리를 쓰는 문제인 것 같긴 한데, N = 100만과 같이 N이 좀 큰 상황에서 내가 생각한 풀이는 O(NlgN) 같고 시간 제한이 좀 넉넉하지 않은 상황을 마주한다면 STL set/map으로 풀었을 때 시간초과가 날 가능성도 있습니다. 이럴땐 일단 구현을 해보고 TLE가 난다면 기도하는 심정으로 STL unordered_set/unordered_map으로 교체해서 내보고, 그래도 또 TLE가 난다면 뭔가 set/map을 사용하지 않고 이분 탐색이나 정렬이나 아니면 그냥 배열의 인덱스를 가지고 푸는 다른 풀이를 고민을 해볼 필요가 있습니다.
 
 
 

20. 우선순위 큐

 

문제집 링크
문제 분류문제문제 제목정답 코드

연습 문제	11286	절댓값 힙	정답 코드
연습 문제	1715	카드 정렬하기	정답 코드
기본 문제✔	1927	최소 힙	정답 코드
기본 문제✔	2075	N번째 큰 수	정답 코드
기본 문제	11279	최대 힙	정답 코드
기본 문제	13975	파일 합치기 3	정답 코드
응용 문제✔	1655	가운데를 말해요	정답 코드
응용 문제✔	1781	컵라면	정답 코드

 
 
11286 절대값 힙 : STL comp 사용하는건데... 솔직히 보면 알겠는데 구현하라고 하니까 좀 너무 막막해서 
다시봐야 할 것 같다.
 
1655 가운데를 말해요 : 어느정도 구상은 했는데 만약에 우선순위 큐에 이문제가 없었으면 헤멨을 것 같다(시간 제한 보고 알아 차렸을수도? ) 
아무튼 이건 한번더 풀어봐야할 것 같다
 
 

 
힙은 이진 트리 모양을 가지고 있습니다. 진 트리는 앞 단원에서 언급했듯 각 정점의 자식이 최대 2개인 트리를 의미하고 힙은 이진 검색 트리와는 다릅니다. 은근히 이진 검색 트리와 힙을 헷갈려하시는 분들을 많이 봤는데 둘은 이진 트리라는 공통점만 있을 뿐이고 다른 자료구조란걸 기억하셔야 합니다.
 

삽입은 이정도면 괜찮은 것 같고, 최솟값의 확인은 더 간단합니다. 그냥 루트에 적힌 값이 최솟값입니다. 단 주의하셔야 하는게, 최소 힙에서는 최솟값을 효율적으로 확인할 수 있지만 열 번째로 작은 값의 확인이라던가 최댓값의 확인은 모든 원소를 다 보는게 아닌 한 불가능합니다. 반대로 최대 힙이었다면 루트에 최댓값이 적혀 있으니 최댓값의 확인은 가능하지만 열 번째로 큰 값의 확인이라던가 최솟값의 확인은 마찬가지로 불가능합니다. 이 점 또한 이진 검색 트리와 힙의 차이라고 볼 수 있겠습니다.
 
STL

 
priority_queue<int,vector<int>,greater<int>>  pq;
를 사용해야 최소 힙으로 사용 할 수 있다
 
 
set vs pq

 
일단 맞는 말이에요. 빅오의 관점에서 시간복잡도가 똑같고 set의 기능이 더 다양합니다. 맞는 말인데, priority_queue는 set보다 수행 속도가 빠르고 공간도 적게 차지합니다. set은 전 단원에서도 언급했지만 새 정점을 동적할당하거나 정점을 제거하고 불균형이 발생했을 때 그것에 대한 처리가 필요하기 때문에 O(lg N)이라도 꽤 시간을 많이 차지합니다. 반면 priority_queue는 트리 자체가 불균형이 없고 무조건 lg N번 비교하면서 자리를 바꾸면 끝이라 훨씬 빠릅니다. 같은 연산을 할 때 set과 priority_queue는 속도가 한 2-4배 정도 차이날 수 있습니다. 그리고 공간을 차지하는 정도도 차이가 많이 납니다. 그렇기 때문에 priority_queue에서 제공하는 연산들만 필요할 경우에는 set을 쓰는 것 보다 priority_queue를 쓰는게 좋습니다.
 
 

21. 그래프

+) STL 사용 못할때 인접 리스트 어떻게 해야하는지 다시 확인하기 . 
 

그래프

문제집 링크
문제 분류문제문제 제목정답 코드

연습 문제	11724	연결 요소의 개수	정답 코드
연습 문제	1260	DFS와 BFS	정답 코드
기본 문제✔	2606	바이러스	정답 코드
기본 문제✔	5567	결혼식	정답 코드
기본 문제✔	11403	경로 찾기	정답 코드
기본 문제✔	2660	회장뽑기	정답 코드
기본 문제	1389	케빈 베이컨의 6단계 법칙	정답 코드, 별해 1
기본 문제	1325	효율적인 해킹	정답 코드
기본 문제	6118	숨바꼭질	정답 코드
응용 문제✔	1707	이분 그래프	정답 코드
응용 문제✔	2617	구슬 찾기	정답 코드
응용 문제✔	1043	거짓말	정답 코드
응용 문제	5214	환승	정답 코드

 
 
 
 
보통 문제에서는 필요에 따라 "그래프는 연결되어 있다/그래프는 연결그래프이다", "두 정점 사이의 간선은 최대 1개 존재한다/같은 간선은 한 번만 주어진다", "간선의 두 정점은 서로 다르다/간선은 서로 다른 두 정점을 연결한다"와 같이 조건을 엄밀하게 지정하는 경우가 많습니다. 그러나 이러 추가적인 조건이 주어지지 않았다면 그림에 있는 그래프처럼 그래프가 분리되어 있거나, 같은 간선이 여러 개 있거나, 혹은 루프가 있거나 하는 형태에 대해서도 올바른 답을 낼 수 있게 코드를 짜야한다는걸 기억해야 합니다. 참고로 두 정점 사이의 간선이 1개 이하이고 루프가 존재하지 않는 그래프를 우리는 단순 그래프(Simple Graph)라고 합니다.
 
 

 

 

21. 트리

문제집 링크
문제 분류문제문제 제목정답 코드

연습 문제	11725	트리의 부모 찾기	정답 코드
연습 문제	1991	트리 순회	정답 코드
기본 문제✔	4803	트리	정답 코드
기본 문제✔	15681	트리와 쿼리	정답 코드
기본 문제✔	1240	노드사이의 거리	정답 코드
기본 문제	22856	트리 순회	정답 코드
기본 문제	1068	트리	정답 코드, 별해 1
응용 문제✔	20955	민서의 응급 수술	정답 코드, 별해 1
응용 문제✔	14267	회사 문화 1	정답 코드
응용 문제✔	2250	트리의 높이와 너비	정답 코드
응용 문제	2533	사회망 서비스(SNS)	정답 코드
응용 문제	1967	트리의 지름	정답 코드, 별해 1
응용 문제	1167	트리의 지름	정답 코드, 별해 1

 
 
 
 
 
플로이드
- 1507 번 : 아이디어를 못뽑아냄.
어디서 부터 아이디어를 뽑아냈으면 좋았을까
'최단 거리' 이기 때문에 할 수 있는 방법을 생각해봤었으면 좋았겠다.
a->b 에서 갈때
1. t 를 거쳐가는경우
2. 직접 연결되어 있는 경우 
이렇게 두가지가 있다는 점을 다시 참고해서 풀어보자
 
아이디어를 알고 나면 구현은 쉽다.
 
 
 
 
 
 
 
 
 
 
 
 
 

---

 
(모든 출처 : 바킹독 실전 알고리즘 강의 ) + (직접 참가한 대회 문제 추가 )
 
 

[+ 추가]

code up 에서 각종 문제들을 추가로도 풀어 볼 수 있다
 
https://codeup.kr/problemsetsol.php?psid=23

문제집 / C언어 기초 100제

 
최백준 강의 
https://code.plus/course/53

코딩 테스트 준비 - 문제

강의 자체를 들을껀 아니고 여기서 나온 스텝 문제들을 순서대로 풀어나갈까 한다. 

 
https://hahahoho5915.tistory.com/35

[간단정리] List, Set, Map 특징 및 차이점(+ 구현체 )

해시 - unoredered set / map
이진 검색트리 - set/map
우선순위 큐(완전 이분 트리였나) - priority_queue ;