문제링크 : https://www.acmicpc.net/problem/1920


아이디어

  • 일단 브루트포스로 모두 순회하면서 탐색할 경우
    • 쿼리 M개동안 N번을 돌아야함
    • 시간복잡도 : O(NM) = 1e10 > 시간초과
  • 이진탐색 사용해서, 해당 값 찾기
    • 찾은다음 인덱스 반환해서 같은 값인지확인

시간복잡도 계산

  • N개 정렬 : O(NlgN)
  • 쿼리 M번 : O(M)
  • 이진탐색 : O(lgN)
  • 총합 : O(NlgN + MlgN) = O(MlgN)

자료구조

  • 정수 저장 : map[100010];
    • 모든 정수 범위 : 2^31보다 작음 > INT 가능

코드(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int map[100010];
 
int binsearch(int st, int en, int tar) {
    if(st==en) {
        // 타겟이랑 값이 같은지 확인
        if(map[st] == tar) return 1;
        return 0;
    }
    
    // 이진탐색 lower bound
    int mid = (st+en)/2;
    if(map[mid] < tar) return binsearch(mid+1, en, tar);
    else return binsearch(st, mid, tar);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N; cin >> N;
    for(int i=0; i<N; i++) cin >> map[i];
    sort(map, map+N);
    
    int M; cin >> M;
    for(int i=0; i<M; i++) {
        int num; cin >> num;
        cout << binsearch(0,N-1,num) << '\n';
    }
    return 0;
}
cs

문제유형

  • 이진탐색 - 모든케이스에서 이분탐색

비슷한 문제

'알고리즘 > 백준' 카테고리의 다른 글

백준 1939 중량제한  (0) 2021.03.18
백준 1300 내리막길  (0) 2021.03.18
백준 1662 압축  (0) 2021.03.17
백준 2304 창고 다각형  (0) 2021.03.17
백준 14719 빗물  (0) 2021.03.17

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/49190


아이디어

  • 사방이 막히는 경우
    • 이미 지난 점을 다시 지나올때, 단, 이전에 도착한 방향과 똑같지 않아야함
      • 지난점을 체크하고
      • 지나온 방향도 체크해야함, 이때 역방향도 체크
    • X자를 그리며 화살표가 이동하는 경우
      • 점을 2번 이동하는 걸로 하자
      • 방이 최대 200000
      • 중복체크할때 배열로 하면 너무커짐
      • map으로 중복 체크하자

시간복잡도 계산

  • 배열 크기 전체 순회 : O(N)

자료구조

  • 중복체크 : map<pair<int, int>, bool>
    • 들어가는값 : 각각 y,x축 좌표
    • 최소값 : -2e5
    • 최대값 : 2e5
      • 중복 방향 체크 : map<tuple<int, int, int, int>,bool>
      • int pre : 이전 방향을 확인

코드(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <vector>
#include <map>
#include <tuple>
 
using namespace std;
 
map<pair<int, int>, bool> chk;
map<tuple<int, int, int, int>, bool> dirchk;
 
int dy[] = {-1,-1,0,1,1,1,0,-1};
int dx[] = {0,1,1,1,0,-1,-1,-1};
 
int solution(vector<int> arrows) {
    int cnt=0;
    
    int y = 0;
    int x = 0;
    chk[make_pair(y,x)] = 1;
    
    
    for(int i=0; i<arrows.size(); i++) {
        int tmp = 2;
        while(tmp--) {
            int ed = arrows[i];
            
            int ny = y + dy[ed];
            int nx = x + dx[ed];
            
            // 도착점이 중복값이면서, 같은 방향이 아닐경우
            if(chk[make_pair(ny,nx)] && dirchk[{ny,nx,y,x}] ==false) {
                cnt++;
            }
            
            chk[{ny, nx}] = 1;
            dirchk[{ny,nx,y,x}] = 1;
            dirchk[{y,x,ny,nx}] = 1;
            
            y = ny;
            x = nx;
        }
        
    }
    return cnt;
}
 
cs

문제유형

  • 시뮬레이션 - 새로생기는 영역 구하기
    • 새로 영역 생기는 경우 : 이미 지나온 간선 && 같은 방향으로 들어오지 않아야함
    • map 사용할경우 노드 너무많아지고, 음수 사용하기 위해 map 사용

문제링크 : https://www.acmicpc.net/problem/1662


아이디어

  • 스택을 사용하여 (을 사용하면 나오는 위치를 우선 구해놓자
    • 재귀함수를 사용해서 (만나면 앞에 숫자에서 곱하기 사용

시간복잡도 계산

  • 스택사용해서 괄호 시작 및 끝나는 위치 매핑 : O(S)
    • 재귀함수 중 순회 : O(S)
  • 총합 : O(S)

자료구조

  • 괄호 시작 및 끝나는 위치 계산용 스택 : stack(int)
    • 스택안에 들어가는 값 : 각각 문자열 인덱스
    • 최대값 : 50 > INT 가능
      • 괄호 시작 및 끝나는 위치 기록 : map[60]
    • 들어가는 값 : 문자열 인덱스
    • 최대값 : 50 > INT 가능
      • 압축안된 문자열 길이 rs
    • 한번 괄호 쌍에 필요한 문자열 최소 3개
    • 그럼 최대 50/3 = 17번이 곱해질수 있음
    • 최대 9^17 > long long 사용

코드(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <stack>
#include <string>
 
using namespace std;
typedef long long ll;
 
int map[60];
string s;
 
ll recur(int st, int en) {
    ll rs=0;
    for(int i=st; i<=en; i++) {
        
        // 만약 괄호 만나면 해당 괄호 끝에 해당하는 부분까지 곱해주기
        if(s[i] == '(') {
            // 이전글자 빼주기
            rs--;
            ll preChar = s[i-1]-'0';
            rs += preChar * recur(i+1,map[i]-1);
            // 괄호로 인덱스 이동
            i = map[i];
        } else {
            rs++;
        }
    }
    
    return rs;
}
 
int main() {
    fill(map, map+60, 0);
    
    cin >> s;
    stack<char> st;
    
    // 괄호 끝나는 위치 기록함
    for(int i=0; i<s.size(); i++) {
        char ec = s[i];
        if(ec == '(') {
            st.push(i);
        } else if(ec==')') {
            int ei = st.top(); st.pop();
            // 괄호 끝나는 위치 기록
            map[ei] = i;
        }
    }
    
    cout << recur(0, s.size()-1) << '\n';
    
    return 0;
}
 
cs

문제유형

  • 시뮬레이션 - 스택 압축
    • 괄호 통해서 압축하는문제
    • 사전에 스택으로, 각각 괄호에서 끝나는 부분 구해놓은 뒤
    • 재귀함수 통해서 괄호 나올때마다 계산해주는 문제

'알고리즘 > 백준' 카테고리의 다른 글

백준 1300 내리막길  (0) 2021.03.18
백준 1920 수 찾기  (0) 2021.03.18
백준 2304 창고 다각형  (0) 2021.03.17
백준 14719 빗물  (0) 2021.03.17
백준 14499 주사위 굴리기  (0) 2021.03.17

+ Recent posts

티스토리툴바