토누 개발 일지

그리디

탐욕 알고리즘.

현재 상황에서 지금 당장 좋은 것만 고르는 방법으로 현재의 선택이 나중에 미칠 영향은 고려하지 않는다.

코딩테스트에서의 그리디

문제를 풀 수 있는 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.

ex)

'거스름돈' 문제 (그리디 알고리즘의 대표 문제)

500원, 100원, 50원의 동전으로 거스름돈을 내어줄 때 최소의 동전 갯수로 거스름돈을 내어주는 방법은?

해결방법

가장 큰 화폐 단위부터 돈을 거슬러 준다.

다음과 같이 각 문제에서의 아이디어를 떠올릴 수 있고 이것이 정당한 지 검토할 수 있으면 그리디 문제를 풀 수 있다.

내가 백준 그리디 문제들을 풀면서 느낀 점

지금 상황에서 가장 좋은 것을 고르는 그리디의 특성상 문제의 흐름을 순응적으로, 그대로 따라가기 보다는 

주어진 조건에서 가장 빠르게, 정확하게 문제를 해결할 수 있는 모든 방법을 고려해 보아야 한다.

예를들어, 백준 11047번도 주어진 단위의 동전들으로 최소 개수를 고르는 문제이며 for문을 단위가 큰 값(동전 리스트의 뒷쪽 부터 시작한다면 시간 초과를 피할 수 있다)

나는 이 문제를 1원부터 돌면서 4200원에 맞는 가장 큰 단위(1000원)를 찾도록 코드를 작성하였더니 시간초과가 나왔다.

비단 이 문제 뿐 아니라 모든 코테 문제에서 여러가지 시야를 가질 수 있도록 더 훈련해야 할 것 같다.

문제 해석

나이와 이름을 pair로 입력 받고 정렬해야하는 문제

stable sort

#include <algorithm> 헤더에 들어있는 sort 기법으로, 원래의 순서를 손상시키지 않으면서 정렬하는 기능

이 기능을 통해 나이가 같은 경우 입력한 순서대로 정렬해야하는 조건을 충족시킬 수 있다.

코드

#include<iostream>
#include<utility>
#include<algorithm>
#include<string>
using namespace std;

bool compare(const pair<int,string>& a , const pair<int,string>& b) {
    
    return a.first < b.first;  
}

int main() {
    int n;
    cin>>n;
    pair<int,string> p[n];
    for(int i=0;i<n;i++) {
        int a;
        string b;
        cin>>a>>b;
        p[i].first = a;
        p[i].second = b;
    }
    stable_sort(p, p +n,compare);
    for(int i=0;i<n;i++) {
        cout<<p[i].first<<' '<<p[i].second<<'\n';
    }
    return 0;
}

백준 1463번 C++ 풀이

다이나믹 프로그래밍 문제

3가지 연산이 가능한데 입력 받은 n을 3가지 연산을 최소로 사용해서 1로 만들어야 한다.

연산을 최소로 사용해야 한다는 부분이 포인트다.

bottom-up 방식의 dp를 이용해 풀 수 있다.

입력받는 값 n의 연산 횟수만을 출력하면 되지만 1부터 n까지 각각의 값들의 연산 횟수를 모두 알아야 한다.

dp[ x ] = y   에서 y는 x의 연산횟수를 의미한다. 

for문 안에서 min 연산을 통해 최소의 연산 횟수를 유지할 수 있게 한다.

"1을 뺀다." 라는 연산을 적용해 dp[i] 는 dp[i-1] 보다 1 큰 값을 입력한다.

예를 들어 n= 10 일때 

10 - 1  ->9     연산 1회  

             +       9의 연산 횟수  => 10의 연산 횟수   가 되기 때문.

그리고 만약 2 또는 3으로 나눠진다면 min을 사용해 나누기를 사용했을 때의 연산횟수와 기존의 연산횟수 중 최솟값을 구할 수 있다.

스택(STACK)

한쪽 끝에서만 자료를 넣고 뺀다.

가장 최근에 들어온 자료가 가장 먼저 나가는 방식. LIFO(Last In First Out 방식)

top = 스택의 맨 위 요소, 가장 최근에 삽입한 값

stack.push( ) = top에 새로운 데이터 추가

stack.pop( ) = top 삭제

삽입, 삭제의 시간 복잡도는 O(1)

c++ stl stack 존재

#include <stack>

stack<int> st;

st.push(10);

st.pop();

st.top();

st.size();

st.empty();

큐(QUEUE)

양쪽 끝에서 데이터의 삽입과 삭제가 각각 이루어진다.

가장 먼저 들어왔던 데이터부터 삭제되는 선입선출 방식.FIFO(First In First Out)

queue.push( ) = back쪽에 새로운 데이터 추가

queue.pop( ) = front 데이터 삭제

queue.front( ) = 가장 오래된 데이터

queue.back( ) = 가장 최근에 들어온 데이터

c++ stl queue 존재

#include <queue>

queue<int> q;

q.push(10);

q.pop();

q.front();

q.back();

q.size();

q.empty();

얼마 전에 드디어! 백준 실버 등급에 도달했다.

작고 소중한 나의 실버 등급

브론즈에 있을 때는 실버가 그렇게 예뻐보였는데 실버에 오니 골드가 너무 멋있어 보인다. 골드 다는 그날까지 열심히 꾸준히 풀어야지

지난주에 개강도 하고 며칠 못 풀다가 오늘 실버5문제로 다시 백준 풀기를 이어가 줬다.

백준 1978번

나는 등급 별로 푼 사람 수가 많은 순서대로 문제를 푸는데

오늘 푼 문제는 실버치고 그다지 어렵지 않은 문제라서 후딱 이해하고 풀어낼 수 있었다.

주어진 숫자가 소수인 지 아닌 지 체크하는 방법만 알고 있다면 풀 수 있는 문제!

소수란 1과 자기 자신만을 약수로 가지는 수이다.

예를들어 2,3,5,7,11,13 등등등이 있겠지

문제를 보자마자 소수의 특징을 이용해서 소수 갯수를 카운트할 수 있는 방법이 있을텐데 싶었다.

1과 자기 자신만을 약수로 가져야 하므로 2 ~ 자기자신-1 인 수로 나누었을 때는 나머지가 0이면 안된다.

이 방법을 적용해서 소수의 갯수를 세는 코드를 작성해 보았다.

key가 1일 때가 소수임을 의미하는 때 이다.

처음에는 위와 같이 코드를 짰다. 2부터 a-1까지 중에 나머지가 0인 경우가 있다면 체크하는 방법이었다.

이렇게 코드를 짜면서 자연수 1을 입력하는 경우에는 for문에서 어떻게 돌게 되는 지 헷갈려서 a가 1인 경우를 따로 빼서 작성하였다.

그리고 구글링하여 아래 코드 같은 방법도 찾아냈는데 훨씬 깔끔하게 작성된 것 같아서 아래와 같은 방법으로도 구현해 봤다. 소수의 정의인 1부터 자기자신까지의 나머지를 모두 체크하고 0인경우가 2번인 경우에만 갯수를 센다.

백준 2941번 문제

string :: npos 는 -1의 값을 가지는 상수로

find() 함수에 의해서 found되지 못하는 경우 npos 값이 리턴된다.

이 문제는

string 의 find 함수와 replace 함수를 이용하면 쉽게 문제를 풀 수 있다.

idx = str.find(croation[i]);

croation[i]에 위치한 문자 x를 string str에서 찾아 변수 idx에 저장한다.

if ( idx == string::npos )

break;

만약 값을 찾지 못했다면 while문을  break 한다.

str.replace ( idx, croation[i].length(), "#" );

크로아티아알파벳 덩어리를 길이 1을 가지는 문자 #으로 변경해준다.

백준 1157번

2월이 되고 후쿠오카 여행을 다녀 온 후 다시 백준 문제 풀기를 시작했다.

오랜만에 해서 그런 지 이제 난이도가 어려워 진 건지 ㅠㅠ 백준 문풀 속도가 더뎌졌다.

더 열쉬미 해야겠지

알파벳 수를 세야하는 1157번 문제 아스키 코드를 사용해야 한다. 

코드 4번쨰 줄의 int 배열을 main함수 안에다가 선언해서 자꾸 틀렸습니다가 떴다.

왜 그런지 몰라 답답해하고 있었는데 지수언니와 이야기 하다가 이유를 알아냈다! 배열을 지역변수로 선언하면 쓰레깃값이 저장되어 초기화를 해주어야 하는데 초기화를 안해줘서 아래에서 ++을 쓰면서 잘못된 값을 저장한 것이다.

전에도 초기화를 깜빡한 적이 있었는데 진짜 앞으로는 잊지 말자 초기화!!

어느새 찔끔 찔끔 브론즈2까지 올라왔당 얼른 실버에 가고 싶다 촌시런 갈색 말고 멋있는 은색 달고 싶당

장범준 실버판테온 들으면서 정리해야지

#백준 2577번

풀이 방법:

곱한 값을 문자열로 저장, 크기가 10인 배열을 생성하고, 문자열에서 1~9까지의 각 값이 체크 될 때 해당 배열 칸의 값을 1씩 증가 시킨다. 

숫자를 문자로 입력받는 방법은  백준 11720번 띄어쓰기 없는 수 입력 받기 문제에서 사용했던 방법,

각 수들의 빈도 수를 배열을 만들어 체크하는 방법도 백준 3052번 문제에서 사용했던 방법이다

문제를 읽고 딱 풀이 방법들이 생각나고 하는 걸 보니 나름 실력이 느는 것 같아 뿌듯했다ㅎ

그러나 내가 몇 번 헤맸던 부분들이 있다...

# int 타입 string 으로 변환

to_string 함수를 사용해야 한다.

형식:          string    string변수명    =    to_string (  int형 변수명  );

반대로 string 을 int 로 바꿀 때는 stoi 함수를 사용하면 된다.

이런 방법들은 무조건 외워놓아야 할 것 같다 외우지 않으면 그냥 떠올리기는 쉽지 않을 듯.

# 숫자 -> 문자 변환

이전에도 사용했던 방법!

문자로 저장된 숫자 - '0'  을 하면 문자로 저장됐던 숫자 가 숫자 타입으로 돌아온다!