[강의]백준 알고리즘 1회차

intro

질문은 question.startlink.help

  • 강의자료는 앞으로 3일전정도에 미리 올릴 생각임.
  • 수업시간에 사용한 (필기자료) 모든 자료는 재업로드 예정

수업 Tip

  • 예습: 문제만 읽고 방법을 생각(10분 내외)
  • 복습: 스스로 해결 + (중요)코딩

강의내용

시간복잡도

  • 시간복잡도 계산방법 - 코드를 보지않고 미리 계산! (코드를 먼저 짤 경우 시간이 오래걸린다.)
  • 대략 1억 = 1초라고 생각하면 된다.
  • N을 미리알면 시간복잡도도 어느정도 예상가능 (EX: N= 1,000,000인 경우 N^2은 100억이니 절대안됨.)

메모리

  • 보통 메모리제한은 걱정할 필요 없다.
  • 사용한 변수의 공간으로 계산.
  • 메모리초과 = 코딩실수, 불필요한 저장, 중복된 저장
  • stack overflow: 대부분은 코딩실수
  • 즉, 메모리는 나중에 생각해도 된다. 시간을 지키면 저절로 따라올 것

DFS/BFS

목적1. 한 정점에서 시작해 연결된 모든 정점을 한 번씩 방문하는 것.

  • 위의 목적인 경우에는 둘 중에 아무거나 선택해도 무방하다
  • BUT, 모든 가중치가 1인 경우 최소시간은 BFS로 구할 수 있다.
  • 따라서 문제를 그래프형태로 모델링하고 위 방법을 사용하면 된다.

q. bfs로는되고 dfs로는 안되는 것?

DFS는 주로 재귀함수, BFS는 주로 큐로 구현

void dfs(int x){
	
	if(정답을 찾음) 정답을 찾은처리
	if(check[x]) return;
	check[x]=true;
	if(불가능한경우) return;
	for(int i=0; i<n; i++){
		dfs(x);
	}
}
  • BFS는 간선의 갯수가 많지 않아야 한다. (1억 미만)
  • 간선의 갯수가 1천만을 넘는 순간 의심을 해보면 좋다.
void bfs(int 시작){
	queue<int> q;
	q.push(시작); check[시작] = true; dist[시작] = 0;
	while(!q.empty()){
		int x = q.front(); q.pop();
		for(가능한 모든 다음 정점 y){
			if(check[y] == false) {
				q.push(y); check[y] = true; dist[y]=dist[x]+1;
			}
		}
	}
}

브루트포스

  1. 모든 방법의 수를 계산 (직접)
  2. 방법을 다 만든다.
  3. 2에서 만든 방법을 1번씩 연산

제일 중요한 건 재귀함수. 딴거 다 까먹어도 이거 하나로 다 구현할 수 있다.

  • 보통 시간복잡도는 O(전체경우의 수 * 하나를 시도하는데 걸리는 시간)
  • 전체 경우의 수는 백만단위 혹은 그 이하인 경우가 많다.

브루트포스 using 재귀함수의 기준 (선택/순서)

  • 선택의 경우 1~N까지 있는 경우 1을 선택할 지 말지 2를 선택할 지 말지
    (순서가 기준이 되는 경우 N개 = N! 보통 N<=10)
  • 순서의 경우 1~N까지 있는 경우 1을 먼저할 지 말지 2를 먼저할 지 말지 (선택이 기준이 되는 경우 N개 = 2^N 보통 N<=20)

N이 10, 20정도인 이유: 2^20 = 약 1억, 10! = 약 1억이라서! 꼭 정답은 아님.

문제풀이

양념 반 후라이드 반(16917, 브루트포스)

현진 치킨에서 판매하는 치킨은 양념 치킨, 후라이드 치킨, 반반 치킨으로 총 세 종류이다. 반반 치킨은 절반은 양념 치킨, 절반은 후라이드 치킨으로 이루어져있다.

  • 양념 치킨 한 마리의 가격은 A원
  • 후라이드 치킨 한 마리의 가격은 B원
  • 반반 치킨 한 마리의 가격은 C원이다.

상도는 오늘 파티를 위해 양념 치킨 최소 X마리, 후라이드 치킨 최소 Y마리를 구매하려고 한다. 반반 치킨을 두 마리 구입해 양념 치킨 하나와 후라이드 치킨 하나를 만드는 방법도 가능하다. 상도가 치킨을 구매하는 금액의 최솟값을 구해보자.

문제를 어렵게 하는 것 = 반반! (weird condition..)

모른다는 것은 아주 중요하다 이 문제에서는 반반을 몇개 사야할 지 모르므로 이를 변수로 두어 문제를 해결해보자.

  • 반반치킨 i개 구매 = 후라이드 X-i/2 = 양념 = Y-i/2개 구매!
  • 반반치킨 i개를 정하면 그냥 후라이드와 양념만 사면 끝나는 간단한 문제가 된다.
  • i의 범위는 (0,100000)이다
  • 즉, 다 계산해보면 된다.

수학실력을 발위하면 i를 연산하는 방법을 줄일 수도 있다 ^^..

봄버맨(16918)

시뮬레이션문제 (문제에 써 있는 것을 그대로 구현하면 끝남)

  • 2차원배열 생성
  • A[i][j]=0인 경우 빈칸
  • A[i][j]=N인 경우 지난시간 또는 남은시간을 입력해서 구현하면 된다.

[중요]로마 숫자 만들기(16922, 브루트포스)

  • 로마 숫자는 I, V, X, L을 사용한다. (각 1, 5, 10 ,50)
  • 로마숫자 N개를 사용해서 만들 수 있는 서로다른 수의 개수를 구하는 문제(N<=20)
  • 정말 최애에에에에대의 경우 4^20까지 나온다. (1억 훌쩍 넘음) 즉, 방법이 잘못되었다 혹은 방법의 수를 줄인다.

순서만 다른 것은 의미가 없다! 따라서 경우의 수는 N^4이다.(XXL = XLX = LXX) 즉, 순서보다 선택이 중요하다. I= A개, V= B개, X= C개, L= D개 선택하자.

  • 가능한 방법의 수를 더 줄일 수 있다.
  • A + B + C + D = N;
  • A + 5B + 10C + 50D;
  • D = A, B, C를 구하면 고정되는 값이므로 삼중포문 O(N^3)까지 줄일 수 있다.

십자가 찾기(16924, 브루트포스)

중요한 조건

  • 사용하는 십자가의 수 <=N,M <= 100
  • 큰 십자가는 작은 십자가를 포함한다.
  • 모든 별이 중심이라고 생각하고 가장 큰 십자가를 찾으면 된다!
  • O(NM*(N+M)) = O(N^3)

[필수]뱀과 사다리게임(16928, BFS)

  • 사실상 위에 나왔던 BFS랑 같은 소스이므로 구현해보자.
  • 1 TO 100 이동하는 게임
  • 사다리 = +, 뱀 = -
  • 주사위 값을 정할 수 있을 때 100까지 갈 수 있는 최단거리(최소)
  • 칸 = vertex, 칸 TO 칸 = edge
  • 구하는 것 = 주사위를 굴리는 최소 횟수 (가중치=1)

최소: 최소라는 키워드가 나오면 BFS를 일단 생각해본다.

  • X의 다음 경우의 수 (X+ 1~6, 사다리, 뱀)
  • 새로운 배열 next[x]를 만들어서, x에 도착한 이후에 가야할 곳을 모두 기록
#include <iostream>
#include <algorithm>
#include <queue>
#define next _next
using namespace std;
int dist[101];
int next[101];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i=1; i<=100; i++) {
        next[i] = i;
        dist[i] = -1;
    }
    while (n--) {
        int x, y;
        cin >> x >> y;
        next[x] = y;
    }
    while (m--) {
        int x, y;
        cin >> x >> y;
        next[x] = y;
    }
    dist[1] = 0;
    queue<int> q;
    q.push(1);
    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int i=1; i<=6; i++) {
            int y = x+i;
            if (y > 100) continue;
            y = next[y]; //뱀이나 사다리를 이용한 것을 담는 배열
            if (dist[y] == -1) {
                dist[y] = dist[x] + 1;
                q.push(y);
            }
        }
    }
    cout << dist[100] << '\n';
    return 0;
}

겉넓이 구하기(16931, 브루트포스)

  • N*M <= 100이므로 브루트포스로 해결해도 된다.
  • 3차원 배열 생성 후, 빈칸이 있으면 겉넓이가 1씩 늘어난다.
  • 또는, 보는 방향을 돌려가면서 하면 된다. (내가 생각한 것 ㅎ)

왜?: 풀기싫게 생겼는데 생각보다 쉽다는 것을 보여주려고.

2x2X2 큐브 (16939, 특이)

  • 한 번 돌려서 큐브가 완성되면 1, 아니면 0 을 출력하는 문제.
  • 설명은 쉬운데 코딩은 어려운 문제…
  • 모든 경우의 수 해봤자 12가지 밖에 안된다….
  • 노가다 ^^,,,

데스나이트(16948, BFS)

  • 이동할 경우 이동횟수가 1개 늘어난다 = 가중치가 1이다. (BFS)
  • d[x]={-2,-2,0,0,2,2}
  • d[y]={-1,+1,-2,+2,-1,+1}

매직 스퀘어로 변경하기(16945, 사전지식 or 브루트포스)

  • 마방진(배열의 모든 행, 열, 대각선의 합이 같은 행렬)
  • 크기가 3X3인 배열을 매직스퀘어(마방진)으로 변경하는 최소비용을 구하는 문제
  • 먼저, 가능한 배열의 개수를 구할 수 있다(9!(약 30만개), 9칸이 있고 어떤 수를 넣을지 결정)
  • 매직스퀘어를 모두 찾아 현재의 상태와 비교하여 MIN값을 찾으면 된다.
  • 매직스퀘어는 8개 밖에 없으므로 사전지식이 있으면 훨씬 쉽게 풀린다.

TIP: 가끔 사전지식이 도움이 되는 경우가 있다. (ex:마방진, 정육면체 전개도)

늑대와 양(16956)

울타리를 세우기만 하면 된다. 최소를 구하는 것이 아니다

  • 불가능한 경우: 늑대와 양이 인접한 경우
  • 위를 제외하면 모두 가능하므로 모든 칸을 울타리로 채운다.
  • 또는 양을 울타리 안에 넣는다.

꿀TIP: 목표가 코딩테스트면 굳이 어려운 문제를 풀필요 없다! (대회나가는게 아니므로)

움직이는 미로 탈출(16954, BFS)

  • 벽은 1초에 한 칸씩 아래로 내려온다. (까다로운 조건)
  • 크기 8X8 체스판에서 가장 왼쪽 아래칸에서 가장 오른쪽 위칸으로 이동 가능한지?
  • 벽의 크기가 8X8이므로 8초동안의 벽을 모두 기록한다.

BFS에서는 할 수 있는게 같아야 같은 정점이다. (강의자료 택시, 버스 참고)

  • 따라서 칸의 정보(r,c,t)로 시간에 대한 정보도 필요하다.

두 스티커(16937, 기초)

  • 모눈종이에 2개의 스티커를 붙일 때 붙여진 넓이의 최댓값을 구하는 문제.
  • N개의 스티커 중 2개만을 고르므로 답이 간단해진다.
  • 즉, N개의 스티커 중 2개를 고르고 붙일 수 있는지 확인 후 MAX값을 구한다.

꿀TIP: 방법을 생각하기 까다로운 문제 중 쉬운 문제다. 이런 문제를 많이 풀면 문제해결능력이 올라갈 듯?

  • 코딩테스트에서는 조건을 추가해서 난이도를 조절한다.

차량 번호판1(16968, 경우의 수, 순서가 중요)

  • 차량 번호판은 길이가 4이하, c(문자), d(숫자)로 이루어진 문자열이다.
  • c = a~z (26개)
  • d = 0~9 (10개)
  • 같은 문자 또는 숫자는 연속될 수 없을 때 가능한 차량 번호판의 갯수.
//index: 몇 번째
//last : 바로 전에 있던 문자.
//다음 재귀 호출 시, index++, last = i로 넣고 재귀
int go(string &s, int index, char last) {
	if (s.length() == index) {
		return 1;
	}
	char start = (s[index] == 'c' ? 'a' : '0');
	char end = (s[index] == 'c' ? 'z' : '9');
	int ans = 0;
	for (char i=start; i<=end; i++) {
		if (i != last) {
			ans += go(s, index+1, i);
		}
	}
	return ans;
}

꿀TIP: 재귀함수를 만들 때 어려운 경우 글로 써볼 것

댓글남기기

참고