IT회사원 신동갓

BOJ 2140 지뢰찾기

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

단순하게 구현하면 되는 문제입니다.

맵의 크기가 n이라고 가정했을 때,

테두리 옆의 # 즉 숫자 옆의 #들만 신경쓰면 됩니다.

그 외의 #들은 지뢰가 있을 수도 있고 없을 수도 있지만, 저희는 다 있다고 가정하고 풀어야합니다.

문제에서 요구하는 것이 최댓값이기 때문입니다.

테두리 옆의 #들은 8방향으로 검사를 해서 만약 주변의 숫자 중에 0인 것이 없다면 지뢰가 있어야하는 자리입니다.

이것만 유의한다면 어렵지 않게 해결할 수 있습니다.

BOJ 1918 후위표기식

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

구조체로 스택을 만들고 다시 해보았습니다.(.cpp에서 돌려야합니다.)

설명은 이전의 글을 참조해주세요.

  #include <stdio.h>
  #include <string.h>
  #include <stdlib.h>
  #define MAX_SIZE 10000
  ​
  typedef struct stack {
      char s[MAX_SIZE];
      int size;
  ​
      stack() {
          size = 0;
      }
  ​
      int empty() {
          if (size) return 0;
          else return 1;
      }
  ​
      void push(char c) {
          s[size] = c;
          size++;
      }
  ​
      void pop() {
          if (!empty()) {
              size--;
          }
      }
  ​
      char top() {
          return s[size - 1];
      }
  }stack;
  ​
  ​
  char* getPostOrder(char* str) {
      int len = strlen(str);
      char* ret = (char*)malloc(sizeof(char) * (len + 1));
      int retIdx = 0;
          
      stack s;
  ​
      for (int i = 0; i < len; i++) {
          if (str[i] == '+' || str[i] == '-') {
              while (!s.empty() && s.top() != '(') {
                  ret[retIdx++] = s.top();
                  s.pop();
              }
              s.push(str[i]);
          }
          else if (str[i] == '*' || str[i] == '/') {
              while (!s.empty() && (s.top() == '*' || s.top() == '/')) {
                  ret[retIdx++] = s.top();
                  s.pop();
              }
              s.push(str[i]);
          }
          else if (str[i] == '(') {
              s.push(str[i]);
          }
          else if (str[i] == ')') {
              while (s.top() != '(') {
                  ret[retIdx++] = s.top();
                  s.pop();
              }
              s.pop();
          }
          else if (str[i] >= 'A' && str[i] <= 'Z') {
              ret[retIdx++] = str[i];
          }
      }
  ​
      while (!s.empty()) {
          ret[retIdx++] = s.top();
          s.pop();
      }
  ​
      ret[retIdx] = '\0';
  ​
      return ret;
  }
  ​
  int main() {
      char str[MAX_SIZE];
      scanf("%s", str);
  ​
      char *ret = getPostOrder(str);
      printf("%s", ret);
  ​
      free(ret);
  ​
      return 0;
  }

진짜 가고 싶었던 게임사 1차 면접에서 복사 생성자가 무엇인가에 대해 나왔습니다.

이 용어 자체를 잘몰라서 잘모르겠다고 대답했고, 이어서 얕은 복사와 깊은 복사에 대해 물어보셨습니다.

두 용어가 헷갈리긴 했지만, 무엇을 뜻하는지는 기억이 나서 잘 대답했던 경험이 있네요.

어쨋든 면접에서 나온 내용을 복습하고자 합니다!! 복사생성자!!!!!!

얕은 복사와 깊은 복사는 복사 생성자의 사전 지식입니다. 모르시면 찾아서 공부하고 참고해주세요!

이 코드의 결과는

30

홍길동

30

홍길동

28e030

28e030

30

硼硼硼硼硼硼硼硼3쬋왹

30

硼硼硼硼硼硼硼硼3쬋왹

가 출력이 될것입니다.

홍길동 밑의 16진수와 아래의 깨지는 문자열은 다르게 출력될 수 있습니다.

이렇게 출력되는 이유에 대해서 알려드리겠습니다.

어떤 클래스의 객체에서 =을 이용하여 객체의 값을 복사하려고 할 때(대입할 때) 따로 오버라이딩을 하지 않는다면

해당 변수의 값만 복사됩니다.

이게 무슨말이냐하면..

위의 test클래스에는 name과 score가 있습니다.

근데 디폴트(오버라이딩을 하지 않았을 떄)

test b = a;

를 실행하면 발생되는 코드는

b.name = a.name;

b.score = a.score;

입니다.

이게 무슨 문제일까요?

네 문제입니다.

왜냐하면 name은 문자열이기 때문입니다. a.name과 b.name은 문자열 자체를 저장하는 것이 아닌 해당 문자열의 시작 주소를 저장하고 있습니다.

그러므로 포인터이겠죠. "홍길동"이라는 새로운 인스턴스가 생성되서 b에 대입되는 것이 아닌, a의 "홍길동"을 같이 가르키게 되는 것입니다.

이게 왜 문제인지 또 모르실 수 있습니다. 이 문제는 위에서 출력된 깨진 문자열을 보시면 됩니다.

문자열이 깨진 이유는 a.nameDelete();을 실행했기 때문입니다. 이것은 함수명 그대로 name에 할당한 메모리를 지워버립니다.

그렇다면.. a의 문자열 "홍길동"이 지워지면 b의 문자열 "홍길동"도 같이 지워지는 것입니다.

(엄연히 따지면 b의 문자열이 아니고 a와 b는 같은 메모리를 가르키고있음)

이를 해결하기 위해서는 복사생성자를 오버라이딩하면 됩니다.

위의 주석 부분 //복사생성자 오버라이딩 부분을 추가해주시면 해결할 수 있습니다.(이로써 깊은 복사가 되는 것이다!)

위 코드의 출력은

30

홍길동

30

홍길동

a.name이 가리키는 주소 : 10ddc8

b.name이 가리키는 주소 : 10da80

30

硼硼硼硼硼硼硼硼?k멓

30

홍길동

입니다.

위의 예제와는 다르죠??

a.name과 b.name이 가리키는 주소가 다릅니다.

이는 복사를 할 때 우리가 오버라이딩한대로 실행되기 때문입니다.

단순히 a.name이 가리키는 값을 복사하는 것이 아닌 새로 동적할당을 하여 문자열을 새로만들고 그 주소를 b.name에 대입을 하는 것입니다.

그리고 a.name만 삭제했기 떄문에 그대로 b는 살아있을 수 있는거죠!!!!!!!!!!!!!!!!

이만 포스팅을 마치겠습니다. 궁금한 점은 댓글달아주세요 ^^

ps....

근데 cpp의 string클래스를 사용하면 그냥 알아서 값을 복사해주더라구요..ㅎㅎㅎ..엄청 편리합니다..

데이터베이스 정규화

정규화를 하는 이유?

한 릴레이션에 여러 엔티티의 애트리뷰트들을 혼합하게 되면 정보가 중복 저장되고, 이는 저장 공간을 낭비시킨다. 또한, 중복된 정보로 인해 갱신 이상이 발생되며, 동일한 정보를 한 릴레이션에는 변경하고, 나머지 릴레이션에서는 변경하지 않은 경우 어느 것이 정확한지 알 수 없다. 이 때문에 정규화 과정을 거쳐 해결한다.

갱신 이상의 종류

<회원> 테이블

학번(PK)	이름	클래스	강사	과목명
1	홍길동	A	신다람쥐	넥슨 취직 대비
2	신첨지	B	이노드	웹 어플리케이션
3	김아무	B	이노드	웹 어플리케이션
4	최태수	C	최디비	데이터베이스
5	이길투	C	최디비	데이터베이스

• 삽입 이상

  • 원하지 않는 자료가 삽입되거나, 삽입하는데 자료가 부족하여 삽입이 되지 않아 발생하는 문제이다.

  • 위 테이블에서 네트워크 과목을 신설할 때 학생이 한명도 없으므로, 이름과 학번이 null값을 갖는다. 학번은 PK이므로 null을 가질 수 없으므로 오류가 발생한다.

• 삭제 이상

  • 하나의 자료만 삭제하고 싶지만, 그 자료가 포함된 튜플 전체가 삭제됨으로 원하지 않는 정보 손실이 발생하는 문제점을 말한다.

  • 위 테이블에서는 "홍길동" 튜플을 삭제하면, (클래스 A, 신다람쥐, 넥슨 취직대비)가 삭제된다. 위에서 클래스 A 정보를 가진 튜플은 "홍길동"이 유일하므로 없어지면 안되는 A 클래스의 정보가 사라지게된다.

• 수정(갱신) 이상

  • 정확하지 않거나 일부의 튜플만 갱신되어 정보가 모호해지거나 일관성이 없어져 정확한 정보 파악이 되지 않는다.

  • 위 테이블에서 B클래스의 강사 이름을 "웹마스터"로 바꾸게 되면, 모든 튜플에서 B클래스의 강사 이름을 전부 수정해야한다.

정규화 과정

실무에서는 주로 1~3정규형만을 사용한다고 한다. 그러므로 3정규형까지만 정리해보겠다.

• 제 1 정규형

  • 애트리뷰트의 도메인이 오직 원자값만을 포함하고, 튜플의 모든 애트리뷰트가 도메인에 속하는 하나의 값을 가져야 한다.

  • 복합 애트리뷰트, 다중값 애트리뷰트, 중첩 릴레이션 등 비 원자적인 애트리뷰트들을 허용하지 않는 릴레이션 형태이다.

• 제 2 정규형

  • 모든 비주요 애트리뷰트들이 주요 애트리뷰트에 대해서 완전 함수적 종속이면 제 2 정규형을 만족한다고 볼 수 있다. 완전 함수적 종속이란 X->Y 라고 가정했을 때, X의 어떠한 애트리뷰트라도 제거하면 더 이상 함수적 종속성이 성립하지 않는 경우를 말한다. 즉, 키가 아닌 열들이 각각 후보키에 대해 결정되는 릴레이션 형태를 말한다.

• 제 3 정규형

  • 어떠한 비주요 애트리뷰트도 기본키에 대해서 이행적으로 종속되지 않으면 제 3 정규형을 만족한다고 볼 수 있다. 이행 함수적 종속이란 X->Y, Y->Z의 경우에 의해서 추론될 수 있는 X->Y의 종속관계를 말한다. 즉, 비주요 애트리뷰트가 비주요 애트리뷰트에 의해 종속되는 경우가 없는 릴레이션 형태를 말한다.(한 테이블에서 X->Y->Z이면, X->Y, Y->Z 두 테이블로 나눈다.)

정규화의 단점?

무작정 정규화를 하는 것은 좋지 않다. 테이블 간의 조인을 자주해야한다면 오히려 한 테이블에 있는 것이 퍼포먼스가 좋을 수도 있다는 이야기이다.

데이터베이스 트랜잭션

트랜잭션이란?

데이터베이스 내에서 한번에 수행되어야할 일련의 연산.

한번에 완료되면 성공적이므로 COMMIT하고 데이터베이스에 반영됨.

도중에 취소가 되면 ROLLBACK하여 작업 시작의 초기의 상태로 되돌림.(일련의 연산 안의 모든 작업이 취소되어 데이터베이스에 영향을 미치지 않음)

트랙잭션의 특성

• 원자성(Atomicity)

  분리 할수 없는 하나의 단위로 작업은 모두 완료되거나 모두 취소 되어야 합니다.

• 일관성(Consistency)

  사용되는 모든 데이터는 일관되어야 합니다.

• 격리성(Isolation)

  접근하고 있는 데이터는 다른 트랜잭션으로 부터 격리 되어야 합니다.

  트랜잭션이 진행되기전과 완료된 후에 상태를 볼수 있지만 트랜잭션이 진행되는 중간 데이터는 볼수 없습니다.

• 영속성(Durability)

  트랙잭션이 정상 종료되면 그 결과는 시스템에 영구적으로 적용되어야 합니다.

• 순차성(Sequentiality)

  데이터를 다시 로드하고 트랜잭션을 재생하여 원래 트랜잭션이 수행된 후의 상태로 데이터를 되돌리는 것을 말합니다.

• 가상함수란?

  • C++ 클래스에서 virtual 키워드를 사용하는 함수

  • virtual 키워드를 이용하면!! 동적 바인딩이 됨.

  • 동적 바인딩이란 ? (출처: http://itguru.tistory.com/210)

    • 컴파일 시에 어떤 함수가 실행될 지 정해지지 않고, 런타임 시에 정해지는 일을 가리켜서 동적 바인딩(dynamic binding)이라고 부릅니다.

      
      #include <iostream>
      #include <string>
      using namespace std;
      ​
      class Parent
      {
          string s;
      public:
          Parent () : s("부모") 
          {
              cout << "부모 클래스" << endl;
          }
      ​
          virtual void what() { cout << s << endl;}
      };
      class Child : public Parent
      {
          string s;
      ​
      public:
          Child () : s("자식"), Parent() 
          {
              cout << "자식 클래스" << endl;
          }
      ​
          void what() { cout << s << endl;}
      ​
      };
      int main()
      {
          Parent p;
          Child c;
      ​
          Parent* p_c = &c;
          Parent* p_p = &p;
      ​
          cout << " == 실제 객체는 Parent == " << endl;
          p_p->what();
      ​
          cout << " == 실제 객체는 Child == " << endl;
          p_c->what();
      ​
          return 0;
      }

    41번째 코드 p_c->what()의 출력은 "자식"이다. 이유는 동적 바인딩이 되기 때문이다. virtual 키워드를 사용하지 않았을 때는 p_c->what()은 출력은 "부모"이다. 이유는 p_c가 부모의 포인터이기 때문에 컴파일러는 '부모의 포인터네? 부모의 함수를 실행해야지.'라고 생각을 하기 때문이다. 하지만 virtual키워드를 넣으므로써 컴파일러는 한번 더 생각하게 된다. '부모의 포인터네? 어 근데.. 이게 부모의 객체가 맞을까? 아니네 자식을 출력하자'라고 생각하게 되는 것이다.

  • 사실 클래스의 상속을 사용함으로써 중요하게 처리해야 되는 부분이 있습니다. 바로, 소멸자를 가상함수로 만들어야 된다는 점입니다.

      
      #include <iostream>
      using namespace std;
      ​
      class Parent
      {
      public :
          Parent()
          {
              cout << "Parent 생성자 호출" << endl;
          }
          ~Parent()
          {
              cout << "Parent 소멸자 호출" << endl;
          }
      };
      class Child : public Parent
      {
      public:
          Child() : Parent()
          {
              cout << "Child 생성자 호출" << endl;
          }
          ~Child()
          {
              cout << "Child 소멸자 호출" << endl;
          }
      };
      int main()
      {
          cout << "--- 평범한 Child 만들었을 때 ---" << endl;
          {
              Child c;
          }
          cout << "--- Parent 포인터로 Child 가리켰을 때 ---" << endl;
          {
              Parent *p = new Child();
              delete p;
          }
      }

    30번째 코드는 Child c;에서 부모 생성자 -> 자식 생성자 호출이 되고, }에서 지역이 끝나므로 소멸자가 호출이된다. 이때 자식 소멸자 -> 부모 소멸자 순으로 호출이된다. 근데 문제는 아래의 34번째 코드에서 발생한다. Parent *p = new Child();에서 delete p;를 호출한다면 자식의 소멸자가 아닌 부모의 소멸자가 호출(부모의 소멸자가 호출되기 때문에 자식의 메모리 누수가 발생한다)이 된다. 하지만 이 소멸자들을 virtual로 선언을 해주면 우리가 원하는 30번째 코드처럼의 호출이 가능해진다.

    이와 같은 연유로, 상속될 여지가 있는 Base 클래스들은 (위 경우 Parent), 반드시 소멸자를 virtual 로 만들어주어야 나중에 문제가 발생할 여지가 없게 됩니다.

    (출처: http://itguru.tistory.com/211 [Programming IT])

• 순수 가상함수함수와 추상 클래스

    
    class Animal
    {
    public:
        Animal() {}
        virtual ~Animal() {}
        virtual void speak() = 0;//순수 가상함수 (자바의 추상 메소드)
    };

  추상 클래스란? 순수 가상함수를 적어도 하나 이상 포함하고 있는 함수를 추상클래스라고 함.(자바랑 같음, 여기서 순수 가상함수란? 자바의 추상 메소드와 같음, 즉 구현이 안되어있어야함. cpp에서는 virtual void 함수명 = 0;으로 순수가상함수임을 알림)

http://bcho.tistory.com/953의 글을 참고했습니다!

Rest란?

Representational safe transfer이며, 웹의 장점을 최대한 활용할 수 있는 네트워크 기반의 아키텍쳐

Rest 기본 요소

크게 리소스, 메소드, 메세지 3가지 요소로 구성된다. 예를 들어 "Terry인 사용자를 생성한다."라는 호출이 있을 때 '사용자'는 생성되는 리소스, '생성한다'라는 행위는 메소드, '이름이 Terry인 사용자'는 메세지이다. 이를 REST 형태로 표현하면

  
  HTTP POST , http://myweb/users/
  {  
     "users":{  
        "name":"terry"
     }
  }

HTTP 메소드

HTTP에는 여러가지 메소드가 있지만 REST에서는 CRUD(Create, Read, Update, Delete) 4가지만 사용한다.

Create = Post(X)

Read = Get(O)

Update = Put(O)

Delete = Delete(O)

오른쪽의 O/X 는 Idempotent는 여러번 수행을 해도 결과가 같은 것을 의미한다.

REST 리소스

REST는 리소스 지향 아키텍쳐이므로 모든 것을 리소스(명사)로 표현한다. 예를 들어 사용자 리소스를 http://myweb/users라고 정의했다면, terry라는 id를 갖는 리소스는 http://myweb/users/terry라는 형태로 정의한다.

REST 특성

유니폼 인터페이스

rest는 http표준이라면 어떤 기술이던지 사용 가능한 인터페이스(모든 플랫폼에 사용가능한 느슨한 결합)이다. 흔히 REST라고 하면 HTTP + JSON를 떠올리는데, JSON은 하나의 옵션이다.

무상태성/스테이트리스(Stateless)

rest는 Stateless(상태를 유지하지 않음)이 특징이다. 상태가 있다/없다는 것은 클라이언트의 컨텍스트를 서버 쪽에서 유지하지 않는다는 의미이다. 쉽게 이야기하면 http 세션과 같은 컨텍스트 저장소에 상태 정보를 저장하지 않는 형태이다. rest의 각 API 서버는 들어오는 요청만을 메시지로 처리할 뿐이다. 세션과 같은 컨텍스트는 신경 쓸 필요가 없기 때문에 구현이 단순하다.

더 많은 특징 참조 주소 : http://bcho.tistory.com/953

​

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

LIS 문제입니다.

꼬이지 않으려면 내가 연결한 전봇대 보다 번호가 더 큰 전봇대만 선택해야하기 때문입니다.

N^2의 방법으로 해결하려고 했으나,  N이 너무 큽니다.

NlogN으로 해결하는 Lower Bound LIS로 해결해야합니다.

저도 처음해봤는데..

우선 로워바운드는 해당 숫자 이상의 수 중에서 가장 가까운 인덱스를 리턴하는 함수입니다.

(정렬이 되어있을 떄만 가능합니다. 이분 탐색을 응용한 것이기 떄문입니다.)

a배열은 입력들어오는 배열이고

b배열은 정렬된 수가 들어가 있는 배열입니다.

주의할 점은 b배열이 lis의 부분수열이 들어가있는 배열이 아니라는 점입니다.

로워 바운드는 자기보다 작거나 같은 경우 b배열에서 수행해서 자기의 위치를 찾아서 대입합니다.

예를 들어 10 20 30 1 2 3 4 5

라는 수열이 있으면

b배열에 10 20 30 이렇게 들어갈 것입니다.

허나 1을 만나면 10 20 30 이 들어있는 수열에서

로워바운드를 하여 자기 이상의 수 중 가장 인덱스를 찾겠죠.

네 value:10, idx:0 입니다.

그러면 b 배열은 1 20 30으로 바뀌게 됩니다.

또 2를 만나면 자기보다 큰 수를 찾겠죠. 네 20입니다.

1 2 30 으로 바뀌게 됩니다.

3을 만나면

1 2 3으로 바뀌겠죠.

4와 5는 b배열의 3보다 크므로 그냥 삽입하면 됩니다.

b배열은 1 2 3 4 5가 완성이 됩니다.

결국 lis값은 5가 되겠죠.