21W19-Stack1 - Githubissues

happy-oh commented 3 years ago

SW 1217. [S/W 문제해결 기본] 4일차 - 거듭 제곱

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<stdio.h>
#include<string.h>

using namespace std;

int pow_int(int m, int n)
{
    if (n == 0)
        return 1;
    else if (n == 1)
        return m;
    else
        return m * pow_int(m, n - 1);
}

int main(int argc, char** argv)
{
    int test_case;
    int T;

    freopen("input.txt", "r", stdin);
    T = 10;
    // cin >> T;

    int i, j, k;
    int test_size;
    int temp;
    int find_bit;
    int find_size;
    int o_int;
    int m, n;

    for (test_case = 1; test_case <= T; ++test_case)
    {

        scanf("%d", &temp);

        scanf("%d %d", &m, &n);

        //printf("\n%d %d %d", temp, m, n);
        o_int = pow_int(m, n);

        printf("#%d %d\n", test_case, o_int);

    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

happy-oh commented 3 years ago

SW 1218. [S/W 문제해결 기본] 4일차 - 괄호 짝짓기

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<stdio.h>
#include<string.h>
#define MAX_N 300

int top;
int stack[MAX_N];

using namespace std;
void stackInit(void)
{
    top = 0;
}

int stackIsEmpty(void)
{
    return (top == 0);
}

int stackIsFull(void)
{
    return (top == MAX_N);
}

int stackPush(int value)
{
    if (stackIsFull())
    {
        //printf("stack overflow!");
        return 0;
    }
    stack[top] = value;
    top++;

    return 1;
}

int stackPop(int* value)
{
    if (stackIsEmpty())
    {
        //printf("stack is empty!");
        *value = 0; // my code
        return 0;
    }
    top--;
    *value = stack[top];

    return 1;
}

int main(int argc, char** argv)
{
    int test_case;
    int T;

    freopen("input.txt", "r", stdin);
    T = 10;
    // cin >> T;

    int i, j, k;
    int arr_size;
    int m, n;
    char cha_arr[300];
    int problem_bit;
    int sol_bit;
    int stack_pop_val;

    for (test_case = 1; test_case <= T; ++test_case)
    {
        problem_bit = 0;
        sol_bit = 2;
        stack_pop_val = 0;
        stackInit();
        scanf("%d", &arr_size);
        scanf("%s", cha_arr);
        for (i = 0; i < arr_size; ++i)
        {
            switch (cha_arr[i])
            {
            case '(':
                stackPush(1);
                break;
            case '[':
                stackPush(2);
                break;
            case '{':
                stackPush(3);
                break;
            case '<':
                stackPush(4);
                break;
            case ')':
                stackPop(&stack_pop_val);
                if (stack_pop_val != 1)
                    problem_bit = 1;
                break;
            case ']':
                stackPop(&stack_pop_val);
                if (stack_pop_val != 2)
                    problem_bit = 1;
                break;
            case '}':
                stackPop(&stack_pop_val);
                if (stack_pop_val != 3)
                    problem_bit = 1;
                break;
            case '>':
                stackPop(&stack_pop_val);
                if (stack_pop_val != 4)
                    problem_bit = 1;
                break;
            }
        }
        int emp_bit;
        emp_bit = (!stackIsEmpty());
        if (problem_bit || emp_bit )
            sol_bit = 0;
        else
            sol_bit = 1;

        printf("#%d %d\n", test_case, sol_bit);

    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

moodmine commented 3 years ago

SW 1217. [S/W 문제해결 기본] 4일차 - 거듭 제곱

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>

using namespace std;

int power(int M, int N)
{
    if (N == 0)
        return 1;

    return M * power(M, N - 1);
}

int main(int argc, char** argv)
{
    int test_case;
    int T;

    //freopen("input.txt", "r", stdin);
    //cin >> T;
    /*
       여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
    */
    T = 10;
    for (test_case = 1; test_case <= T; ++test_case)
    {
        int num;
        scanf("%d", &num);
        int result = 0;
        int M, N;
        scanf("%d %d", &M, &N);
        result = power(M, N);
        printf("#%d %d\n", num, result);
    }

    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

SW 1218. [S/W 문제해결 기본] 4일차 - 괄호 짝짓기

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include <stdio.h>

using namespace std;

#define MAX_N 10000

int top;
char stack[MAX_N];
char arr[10001];

void stackInit(void)
{
    top = -1;
}

int stackIsEmpty(void)
{
    if (top == -1)
        return 1;
    else
        return 0;
}

int stackIsFull(void)
{
    return (top == MAX_N - 1);
}

int stackPush(char value)
{
    if (stackIsFull())
    {
        printf("stack overflow!");
        return 0;
    }
    top++;
    stack[top] = value;

    return 1;
}

int stackPop(char* value)
{
    if (stackIsEmpty())
    {
        printf("stack is empty!");
        return 0;
    }
    *value = stack[top];
    top--;

    return 1;
}

int main(int argc, char** argv)
{
    int test_case;
    int T;

    //freopen("input.txt", "r", stdin);
    //cin >> T;

    T = 10;
    for (test_case = 1; test_case <= T; ++test_case)
    {
        int len;
        scanf("%d", &len);
        char data = 0;
        scanf("%s", arr);
        stackInit();
        int stop = 0;
        int i = 0;
        while (arr[i] != 0)
        {
            switch (arr[i])
            {
            case '(':
                stackPush(arr[i]);
                break;
            case '[':
                stackPush(arr[i]);
                break;
            case '{':
                stackPush(arr[i]);
                break;
            case '<':
                stackPush(arr[i]);
                break;
            case ')':
                if (stack[top] == '(')
                    stackPop(&data);
                else
                    stop = 1;
                break;
            case ']':
                if (stack[top] == '[')
                    stackPop(&data);
                else
                    stop = 1;
                break;
            case '}':
                if (stack[top] == '{')
                    stackPop(&data);
                else
                    stop = 1;
                break;
            case '>':
                if (stack[top] == '<')
                    stackPop(&data);
                else
                    stop = 1;
                break;
            }
            if (stop)
                break;
            i++;
        }

        printf("#%d %d\n", test_case, stackIsEmpty());
    }

    return 0;
}

1219. [S/W 문제해결 기본] 4일차 - 길찾기

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include <stdio.h>

using namespace std;

#define MAX_N 200

int top;
int stack[MAX_N] = { 0, };

void stackInit(void)
{
    top = -1;
}

int stackIsEmpty(void)
{
    if (top == -1)
        return 1;
    else
        return 0;
}

int stackIsFull(void)
{
    return (top == MAX_N - 1);
}

int stackPush(int value)
{
    if (stackIsFull())
    {
        printf("stack overflow!");
        return 0;
    }
    top++;
    stack[top] = value;

    return 1;
}

int stackPop(int* value)
{
    if (stackIsEmpty())
    {
        printf("stack is empty!");
        return 0;
    }
    *value = stack[top];
    top--;

    return 1;
}

int main(int argc, char** argv)
{
    int test_case;
    int T;

    //freopen("input.txt", "r", stdin);
    //cin >> T;
    T = 10;
    for (test_case = 1; test_case <= T; ++test_case)
    {
        int num;
        int len;
        int i, j;
        int result = 1;
        int data = -1;
        scanf("%d %d", &num, &len);
        int arr[2][100][2];
        for (i = 0; i < 2; i++)
            for (j = 0; j < 100; j++)
            {
                arr[i][j][0] = -1;
                arr[i][j][1] = 0;
            }

        int from, to;
        for (i = 0; i < len; i++)
        {
            scanf("%d %d", &from, &to);
            if (arr[0][from][0] == -1)
                arr[0][from][0] = to;
            else
                arr[1][from][0] = to;
        }

        stackInit();
        stackPush(0);

        if (arr[0][0][0] == -1 && arr[1][0][0] == -1) // 0 지점에서 하나의 길이라도 있어야 함.
            result = 0;

        while (stack[top] != 99)
        {
            if (stack[top] == 0 && arr[0][0][1] == 1)
            {
                if (arr[1][0][1] == 1 || arr[1][0][0] == -1)
                {
                    result = 0;
                    break;
                }
            }

            if (arr[0][stack[top]][0] != -1 && arr[0][stack[top]][1] == 0) // 첫번째 길이 뚫렸을 때
            {
                arr[0][stack[top]][1] = 1; // 거쳐갔던 길이라고 체크
                stackPush(arr[0][stack[top]][0]); // 스택에 현재 지점 저장
            }
            else // 첫번째 길이 막혔을 때
            {
                if (arr[1][stack[top]][0] != -1 && arr[1][stack[top]][1] == 0) // 두번째 길이 뚫렸는가?
                {
                    arr[1][stack[top]][1] = 1; // 거쳐갔던 길이라고 체크
                    stackPush(arr[1][stack[top]][0]); // 스택에 현재 지점 저장
                }
                else // 두번째 길이 막혔을 때
                {
                    stackPop(&data); // 왔던 길 되돌아가기
                }
            }
        }

        printf("#%d %d\n", test_case, result);
    }

    return 0;
}

happy-oh commented 3 years ago

[S/W 문제해결 기본] 4일차 - 길찾기


#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<stdio.h>
#include<string.h>
#define MAX_N 200

using namespace std; int top; int stack[MAX_N];

void stackInit(void) { top = 0; }

int stackIsEmpty(void) { return (top == 0); }

int stackIsFull(void) { return (top == MAX_N); }

int stackPush(int value) { if (stackIsFull()) { //printf("stack overflow!"); return 0; } stack[top] = value; top++;

return 1;

}

int stackPop(int value) { if (stackIsEmpty()) { //printf("stack is empty!"); //value = 0; // my code return 0; } top--; *value = stack[top];

return 1;

}

int main(int argc, char** argv) { int test_case; int T;

freopen("input.txt", "r", stdin);
T = 10;
// cin >> T;

int i, j, k;
int test_size;
int load_size;
int temp;
int find_bit;
int find_size;
int o_int;
int m, n;
int start_arr[200];
int end_arr[200];
int map_1[3][100];
int map_2[3][100]; //3번째에는 간 여부 0 -> 안감, 1, 감 표시  2번째에는 100이면 선언이 안된거임

for (test_case = 1; test_case <= T; ++test_case)
{

    scanf("%d %d", &temp, &load_size);
    stackInit();
    for (i = 0; i < load_size; ++i)
    {
        scanf("%d %d ", &start_arr[i], &end_arr[i]);
    }
    for (i = 0; i < 100; i++)
    {
        map_1[0][i] = i;
        map_1[1][i] = 100;
        map_1[2][i] = 0;
        map_2[0][i] = i;
        map_2[1][i] = 100;
        map_2[2][i] = 0;
    }
    for (i = 0; i < load_size; ++i)
    {
        if (map_1[1][start_arr[i]] == 100)
        {
            map_1[1][start_arr[i]] = end_arr[i];
        }
        else
            map_2[1][start_arr[i]] = end_arr[i];
    }

    // 결과값을 저장할 변수 생성 길있으면 true 없으면 false 시작은 false로 시작
    bool ans = false;
    // 스택이 맨 윗 부분이 현재 내가 위치해있는 부분
    stackPush(0);
    // 계속 돌다가 길 하나라도 찾으면 바로 break
    j = 1;

    while (1) {
        // 만약에 내 위치가 끝이면 break
        j++;
        //printf("top = %d\n", top);
        //printf("stack = %d\n", stack[top-1]);
        if (stack[top-1] == 99)
        {
            ans = true;
            break;
        }
        // 그것도 해줘
        if (stackIsEmpty())
        {
            ans = false;
            break;
        }
        // 만약에 내가 있는 위치가, 한번 방문한 적이 있었으면 글로 갈 필요 없자나?
        if ((map_1[2][stack[top - 1]] == 0) && (map_1[1][stack[top - 1]] != 100)) {
            // 내가 map 1에 간 적 없으면, 그 방향으로 가보기
            map_1[2][stack[top - 1]] = 1;
            stackPush(map_1[1][stack[top - 1]]);

        }
        else if ((map_2[2][stack[top - 1]] == 0) && (map_2[1][stack[top - 1]] != 100)) {
            // 내가 map 2에 간 적 없으면, 그 방향으로 가보기
            map_2[2][stack[top - 1]] = 1;
            stackPush(map_2[1][stack[top - 1]]);

        }
        else
        {
            int val;
            stackPop(&val);
        }
    }

    printf("#%d %d\n", test_case, (ans ? 1 : 0));

}
return 0;//정상종료시 반드시 0을 리턴해야합니다.

}

murry2018 commented 3 years ago

SWEA 1217. 거듭 제곱

#include <cstdio>

using namespace std;

inline bool iseven(int x) {
  return (x&1) == 0;
}

// 로그 차수로 자라나는 거듭제곱 알고리즘 (idea from SICP)
// r*a^b
// = r               if b is 0
// = (a*r)*a^(b-1)   if b is odd
// =  r*(a*a)^(b/2)  if b is even
int power(int a, int b, int r=1) {
  if (b == 0)
    return r;
  if (iseven(b))
    return power(a*a, b/2, r);
  else
    return power(a, b-1, a*r);
}

int main() {
  for (int i = 0; i < 10; i++) {
    scanf("%*d");
    int a, b, res;
    scanf("%d %d", &a, &b);
    res = power(a, b);
    printf("#%d %d\n", i+1, res);
  }
}

murry2018 commented 3 years ago

SWEA 1218. 괄호 짝짓기

#include <cstdio>
#include <stack>

using namespace std;

int index(char* items, char item) {
  for (int i = 0; items[i] != 0; i++) {
    if (items[i] == item)
      return i+1;
  }
  return 0;
}

int paren_id(char paren) {
  char open_paren[5] = "([{<";
  char close_paren[5] = ")]}>";
  int id = index(open_paren, paren);
  if (id == 0)
    id = -index(close_paren, paren);
  return id;
}

int main() {
  for (int i = 0; i < 10; i++) {
    stack<char> s;
    char c;
    scanf("%*d\n");
    while ((c = getchar()) != '\n' && c != EOF) {
      int id = paren_id(c);
      if (id == 0)
        continue;
      if (s.size() > 0) {
        int prev = s.top();
        if (prev + id == 0) {
          s.pop();
          continue;
        }
      }
      s.push(id);
    }
    printf("#%d %d\n", i+1, s.size() == 0);
  }
}

murry2018 commented 3 years ago

SWEA 1219. 길찾기

#include <cstdio>
#include <stack>
#include <cstring>

using namespace std;

bool exists_route(int route[2][100]) {
  bool visit[100] = {false};
  stack<int> history;
  history.push(0);
  visit[0] = true;
  while (!history.empty()) {
    int cur = history.top();
    history.pop();
    if (cur == 99)
      return true;
    int route1 = route[0][cur], route2 = route[1][cur];
    if (route1 != -1 && !visit[route1]) {
      visit[route1] = true;
      history.push(route1);
    }
    if (route2 != -1 && !visit[route2]) {
      visit[route2] = true;
      history.push(route2);
    }
  }
  return false;
}

int main() {
  int route[2][100];
  char c;
  while ((c = getchar()) != EOF) {
    ungetc(c, stdin);
    memset(route, 0xff, sizeof route);
    int t, nroute;
    scanf("%d %d", &t, &nroute);
    for (int i = 0; i < nroute; i++) {
      int n, r;
      scanf("%d %d", &n, &r);
      if (route[0][n] == -1)
        route[0][n] = r;
      else
        route[1][n] = r;
    }
    printf("#%d %d\n", t, exists_route(route));
    while ((c = getchar()) != '\n' && c != EOF);
  }
}

murry2018 / BelarusianCutlet

21W19-Stack1 #6

SW 1217. [S/W 문제해결 기본] 4일차 - 거듭 제곱

SW 1218. [S/W 문제해결 기본] 4일차 - 괄호 짝짓기

1219. [S/W 문제해결 기본] 4일차 - 길찾기

SWEA 1217. 거듭 제곱

SWEA 1218. 괄호 짝짓기

SWEA 1219. 길찾기