'전체 글'에 해당되는 글 186건

프로그래머스 - SQL 키트

https://programmers.co.kr/learn/courses/30/lessons/59405

문제

풀이

먼저 DATETIME에 대해 오름차순으로 정렬한 값을 구하고, 그 테이블에서  첫번째 튜플을 불러오면 되는 문제이다.

LIMIT 구문을 사용하여 몇개의 Tuple을 불러올지 지정할 수 있는데, 여기서 1을 해주면 가장 상위에 있는(즉 보호소에 가장 먼저 들어온 동물) 값의 NAME을 출력할 수 있다.

코드

SELECT NAME FROM ANIMAL_INS ORDER BY DATETIME LIMIT 1

평가

LIMIT 구문을 사용하여 상위 N개의 레코드를 불러올 수 있느냐를 묻는 문제이다.

LIMIT 구문에 대해서 확실하게 배우고 넘어가도록 하자. (추후 요긴하게 쓰인다.)

프로그래머스 - SQL 키트

https://programmers.co.kr/learn/courses/30/lessons/59404

문제

풀이

ORDER BY 뒤에 여러개의 Attribution을 두면 앞에서부터 우선순위를 두고 정렬을 하게 된다.

따라서 본 문제에서는 ORDER BY NAME, DATETIME DESC; 를 통해 풀이가 가능하다.

코드

SELECT ANIMAL_ID, NAME, DATETIME FROM ANIMAL_INS ORDER BY NAME, DATETIME DESC;

평가

여러 조건을 통해 정렬하는 방법을 알고 넘어가면 될 것 같다.

프로그래머스 - SQL 키트

https://programmers.co.kr/learn/courses/30/lessons/59403

문제

풀이

ANIMAL_ID와 NAME만 불러오는 방식이므로 SELECT 문에서 ANIMAL_ID와 NAME을 가져온다는 조건을 주면 풀이가 가능하다.

코드

SELECT ANIMAL_ID, NAME FROM ANIMAL_INS ORDER BY ANIMAL_ID;

평가

단순 SELECT를 활용하는 문제이다. 사실 막히신 분들이 크게 없을 거라고 생각하여 포스팅을 안할까하다가 기왕 하는김에 모든 문제 풀이를 올리고 싶다는 생각에 올리게 되었다.

프로그래머스 - SQL 키트

https://programmers.co.kr/learn/courses/30/lessons/59037

문제

풀이

WHERE NOT 구문을 활용하여 INTAKE_CONDITION이 'Aged' 상태가 아닌 Tuple만 출력해주면 풀이가 가능한 문제이다.

코드

SELECT ANIMAL_ID, NAME FROM ANIMAL_INS WHERE NOT INTAKE_CONDITION = 'Aged' ORDER BY ANIMAL_ID;

평가

C언어처럼 != 방식이 아닌 NOT을 사용하여 조건을 지정할 수 있다는 사실을 배울 수 있는 문제이다.

프로그래머스 - SQL 키트

https://programmers.co.kr/learn/courses/30/lessons/59036

문제

풀이

WHERE 절을 통해서 특정 조건의 Tuple만 불러오는 것이 가능하다.

코드

SELECT ANIMAL_ID, NAME FROM ANIMAL_INS WHERE INTAKE_CONDITION = 'Sick' ORDER BY ANIMAL_ID;

평가

WHERE 문을 통해서 조건을 지정하는 방법을 배우고 넘어가자.

프로그래머스 - SQL 키트

https://programmers.co.kr/learn/courses/30/lessons/59035

문제

풀이

ORDER BY 뒤에 DESC를 추가해주면 내림차순으로 정렬할 수 있다.

이를 활용한 문제 풀이가 가능하다.

코드

SELECT NAME, DATETIME FROM ANIMAL_INS ORDER BY ANIMAL_ID DESC

평가

ORDER BY {Attribute Name} DESC; 의 활용법을 짚고 넘어가도록 하자.

프로그래머스 - SQL 키트

https://programmers.co.kr/learn/courses/30/lessons/59034

문제

풀이

SQL에서 *의 의미는 조건에 맞는 모든 Attribute 값을 가져오는 것을 의미한다.

따라서 SELECT * FROM ANIMAL_INS를 실행하면 모든 tuple값을 불러올 수 있다.

또한 SQL문에서 정렬을 위해 사용되는 구문인 ORDER BY 구문을 통해 ANIMAL_ID순으로 오름차순 정렬이 가능하다.

코드

SELECT * FROM ANIMAL_INS ORDER BY ANIMAL_ID;

평가

*을 활용하여 모든 레코드를 불러올 수 있다는 것을 짚고 넘어가자.

백준 - 단계별로 풀어보기 [14889] 

https://www.acmicpc.net/problem/14889

문제

풀이

dfs를 활용한 조합 알고리즘을 사용하여 N명의 사람중 N/2명을 뽑는 조합의 모든 경우의 수를 찾고, 이를 바탕으로 팀을 나눴을 때 두 팀의 능력치의 차이가 가장 최소가 될 때의 값을 저장하여 출력하면 되는 문제이다.

자세한 사항은 코드를 직접 보며 이해하자.

코드

#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;

bool team[20] = {};
int score[20][20] = {};
int N, mymin = 99999999;
void teamset(int idx, int cnt)
{
    vector<int> start; // 스타트 팀원의 인덱스값
    vector<int> link; // 링크팀 팀원의 인덱스값
    int start_score = 0;
    int link_score = 0;
    if(cnt == (N/2))
    {
        for(int i = 0; i < N; i++)
        {
            if(team[i] == true) // 선택된 사람들은 start팀에
                start.push_back(i);
            else // 그 외의 사람들은 link팀으로
                link.push_back(i);
        }
        for(int i = 0; i < (N/2); i++)
            for(int j = 0; j < (N/2); j++)
            {
                start_score += score[start[i]][start[j]];
                link_score += score[link[i]][link[j]];
            } // 각 팀의 능력치의 합 계산
        if(abs(start_score - link_score) < mymin)
            mymin = abs(start_score - link_score);
        return;
    }
    for(int i = idx; i < N; i++)
    {
        if(team[i])
            continue;
        else
        {
            team[i] = true;
            teamset(i,cnt+1);
            team[i] = false;
        }
    }
}
int main() {
    scanf("%d",&N);
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            scanf("%d",&score[i][j]);
    teamset(0,0);
    printf("%d",mymin);
}

평가

해당 문제는 단순히 Brute-Force와 비슷한 방식으로 풀게 될 경우, 반드시 시간초과가 발생하기 때문에 조합으로 발생할 수 있는 팀의 경우의 수를 한번씩만 계산하게끔하여 풀이를 진행해야한다.

대부분의 오답 사유는 시간초과일 것으로 예상되며, 시간초과가 발생하는 원인은 아마도 백트래킹 알고리즘이 각 조합에 대해서 연산을 단 한번만 하는게 아니라 중복연산이 진행중일 가능성이 높다.

백준 - 단계별로 풀어보기 [14888] 

https://www.acmicpc.net/problem/14888

문제

풀이

먼저 수열에 입력할 수를 입력받은 후, 연산자의 개수를 입력받는다.

필자의 경우 operators라는 크기 4짜리 배열을 선언하였고, 덧셈, 뺼셈, 곱셈, 나눗셈의 개수를 각각 입력받았다.

그 후, 백트래킹을 사용하여 재귀로 문제를 해결한다.

매개변수로는 여태까지 연산의 result값, 연산을 진행할 수의 인덱스를 입력받도록 하는 백트래킹 재귀 함수를 정의하여 풀이가 가능하다.

코드를 직접 보고 이해해보자.

코드

#include <iostream>
using namespace std;

int N;
int operands[11]; // 수열 
int operators[4]; // 연산자의 개수
int mymin = 1000000001;
int mymax = -1000000001;
void getanswer(int result, int idx)
{
    if(idx == N)
    {
        if(result > mymax)
            mymax = result;
        if(result < mymin)
            mymin = result;
        return;
    }
    for(int i = 0; i < 4; i++)
    {
        if(operators[i] > 0)
        {
            operators[i]--; // 연산자 하나 사용했으므로 1개 줄여줌
            if(i == 0)
                getanswer(result + operands[idx], idx+1);
            else if(i == 1)
                getanswer(result - operands[idx], idx+1);
            else if(i == 2)
                getanswer(result * operands[idx], idx+1);
            else
                getanswer(result / operands[idx], idx+1);
            operators[i]++; // 다른 연산자를 사용할 것이므로 아까 줄였던 연산자 개수 늘려줌
        }
    }
    return;
}
int main() {
    cin >> N;
    for(int i = 0; i < N; i++)
        cin >> operands[i];
    for(int i = 0; i < 4; i++)
        cin >> operators[i];
    getanswer(operands[0],1);
    cout << mymax << '\n';
    cout << mymin;
}

평가

스도쿠에 비해서 훨씬 쉽고 간단하게 풀리는 백트래킹 문제이다.

정답률은 47.4%이다.

본 문제에서는 재귀의 흐름과 매개변수를 어떤 값을 사용해야할지를 설계하는 능력이 매우 중요하기 때문에, 이러한 설계 능력을 짚고 넘어가면 좋을 것 같다.

백준 - 단계별로 풀어보기 [2580] 

https://www.acmicpc.net/problem/2580

문제

풀이

스도쿠는 각 행과 열, 그리고 3x3크기의 구역 9개에 각각 1~9 까지의 숫자가 단 한번씩만 들어가야하는 규칙을 가지고 있다. 

따라서 해당 문제를 풀이하기 위해서는 스도쿠가 유효한지 체크하는 check함수가 필요하고, check함수는

같은 행 또는 열에 혹시 같은 숫자가 있는지, 3x3크기의 구역에 같은 숫자가 있는지를 체크해주는 함수가 될 것이다.

그 후, 백트래킹을 통해서 0이 입력된 빈칸 부분에 1부터 9까지의 숫자를 차례로 넣어보고, 모든 칸을 채웠을 때 

결과를 호출하면 되는 문제이다.

자세한 풀이는 코드와 주석을 참고하자.

코드

#include <iostream>
#include <utility>
#include <vector>
using namespace std;
int board[9][9]; // 스도쿠 보드 선언
vector<pair<int, int>> points; // 빈칸의 위치 저장
int cnt = 0;
bool found = false; // 스도쿠 판 완성 플래그
bool check(pair<int, int> p)
{
    int square_x = p.first / 3; // 구역을 나눔
    int square_y = p.second / 3;
    for(int i = 0; i < 9; i++)
    {
        if(board[p.first][i] == board[p.first][p.second] && i != p.second) 
            return false; // 같은 행에 같은 숫자가 있으면 false 반환
        if(board[i][p.second] == board[p.first][p.second] && i != p.first)
            return false; // 같은 열에 같은 숫자가 있으면 false 반환
    }
    for(int i = 3*square_x; i < 3*square_x+3; i++)
        for(int j = 3*square_y; j < 3*square_y+3; j++)
        {
            if(board[i][j] == board[p.first][p.second])
            {
                if(i != p.first && j != p.second)
                    return false; // 같은 구역에 같은 숫자가 있으면 false 반환
            }
        }
    return true; // 모든 조건 만족시 유효성 검사 통과
}
void sudoku(int N) {
    if(N == cnt) // 빈칸의 개수만큼을 채워서 스도쿠 판이 완성되면
    {
        for(int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++)
                cout << board[i][j] << ' ';
            cout << '\n';
        } // 결과 출력
        found = true; // 플래그 true로 변경
        return;
    }
        for(int j = 1; j <= 9; j++)
        {
            board[points[N].first][points[N].second] = j; // 1~9 까지의 숫자를 넣어봄
            if(check(points[N])) // 결과가 유효하면 다음 빈칸을 채우러 감
                sudoku(N+1);
            if(found) // 스도쿠가 완성됬을경우 더 이상 다른 해를 찾을 필요가 없으므로 함수 종료
                return;
        }
    board[points[N].first][points[N].second] = 0;// 최적해를 못찾았을 경우 값 비워주기
     return;
}
int main() {
    pair<int, int> point;
    for(int i = 0; i < 9; i++)
        for(int j = 0; j < 9; j++)
        {
            cin >> board[i][j];
            if(board[i][j] == 0)
            {
                cnt++;
                point.first = i;
                point.second = j;
                points.push_back(point); // 빈칸의 좌표 저장
            }
        }
    sudoku(0);
}

평가

해당 문제는 30%라는 매우 낮은 정답률을 기록하고 있는데, 그 이유는 시간 초과 에러가 뜬다는점,

그리고 테스트 케이스가 너무 적어, 문제에서 제시된 테스트 케이스 외의 반례가 많이 발생한다는 점에 있다.

자신의 코드가 왜 오답인지 이해가 안되시는 분들을 위해 대표적인 반례 테스트케이스 2가지를 정리해보았다.

반례(테스트 케이스)

TEST CASE # 1

0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

SAMPLE ANSWER #1

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 1 4 3 6 5 8 9 7
3 6 5 8 9 7 2 1 4
8 9 7 2 1 4 3 6 5
5 3 1 6 4 2 9 7 8
6 4 2 9 7 8 5 3 1
9 7 8 5 3 1 6 4 2

TEST CASE # 2

0 2 0 9 0 5 0 0 0

5 9 0 0 3 0 2 0 0

7 0 0 6 0 2 0 0 5

0 0 9 3 5 0 4 6 0

0 5 4 0 0 0 7 8 0

0 8 3 0 2 7 5 0 0

8 0 0 2 0 9 0 0 4

0 0 5 0 4 0 0 2 6

0 0 0 5 0 3 0 7 0

SAMPLE ANSWER # 2

3 2 1 9 7 5 6 4 8
5 9 6 8 3 4 2 1 7
7 4 8 6 1 2 9 3 5
1 7 9 3 5 8 4 6 2
2 5 4 1 9 6 7 8 3
6 8 3 4 2 7 5 9 1
8 1 7 2 6 9 3 5 4
9 3 5 7 4 1 8 2 6
4 6 2 5 8 3 1 7 9