Grace

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

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

접근방법 및 고려사항

- 기본적으로는 bfs문제이다.

- 나이트의 이동방향이 8가지 이므로 이를 고려한다.

- 만약 이동하려는 자리가 방문했던 자리라면 이때는 굳이 방문할 필요가 없다. 이미 해당좌표를 방문한 경우가 있다는 것이 지금의 루트가 최선의 루트가 아니라는 것을 말한다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstdlib>

using namespace std;



int bfs(pair<int, int> input[], int n){
  queue<pair<int, int>> q;
  int dp[300][300];
  for(int i=0; i<300; i++)
    for(int j=0; j<300; j++)
        dp[i][j]=-1;
        
  int count=0;
  int kx = input[0].first;
  int ky = input[0].second;
  q.push({kx, ky});
  dp[input[0].first][input[0].second]=0;
  //printf("start a,b = %d, %d\n", input[0].first, input[0].second);
  while(count==0 || q.size() > 1 ){
    int a = q.front().first;
    int b = q.front().second;
    //printf("a,b = %d, %d\n",a,b);
    q.pop();
    if(a==input[1].first && b==input[1].second){
        //printf("return !!! : %d=%d, %d=%d\n",a, input[1].first,b,input[1].second);
        if(count==0)
            return count;
        else return count-1;
    }
    if(a==kx && b == ky){
        count++;
        q.push({kx, ky});
    }        
    //printf("count : %d\n", count);
    // 말이동 가능 한 자리면 이동
    // 1.  경로에 대해 모두 고려하는 if문 8개 만들기 or for문으로 구조화 시키기 고민해보자
    // 2. 고려하면서 dp에 저장하기
    // 3. 현재위치가 도착위치면 count 를 리턴한다.
    for(int i=0; i<2; i++){ // i<2 를 i>2 라고 해서 함수가 끊기고리턴값이 쓰레기값으로 봔환되어 디버깅이 어려웠음
      for(int j=0; j<2; j++){
        for(int k=0; k<2; k++){
            //printf("i:%d, j:%d, k:%d\n", i, j ,k);
          int x=0,y=0,X=0,Y=0;
          if(i==0){
            x=1;
            y=2;
          }else{
            x=2;
            y=1;
          }
          if(j==0) x = abs(x);
          if(j==1 && x > 0) x = -x;
          if(k==0) y = abs(y);
          if(k==1 && y > 0) y = -y;
          X = x+a;
          Y = y+b;
          
          if(X >= 0 && X < n && Y >= 0 && Y < n){
              if(dp[X][Y]==-1){ // push하는 거를 if문 안에 넣지 않아서 해당범위에 있는 모든 좌표들이 푸쉬가 되었다. 디버깅 
                dp[X][Y]=count;
                //printf("dp[%d][%d] : %d\n", X,Y,dp[X][Y]);
                q.push({X,Y});
              }
          }
        }
      }
    }
  }
}

int main(){
  int t; cin >> t;
  for(int j=0; j<t; j++){
      int n; cin >> n;
      pair<int, int> input[2];
      for(int i=0; i<2; i++){
        int a,b; cin >> a >> b;
        input[i].first = a;
        input[i].second = b;
      }
      printf("%d\n", bfs(input, n));
  }
}

느낀점 및 개선사항

문제를 푼 후에 다른 사람의 코드와 나의 코드를 비교하면서 배울 점이 있는지 확인해 보았다. 대부분의 코드들이 나보다 훌륭하다고 느껴졌다. 앞으로도 문제 푸는것에 그치는 것이 아니라 타인의 코드와 비교하며 성장해야 겠다.

개선사항정리

1. q에서 카운트 셀때 더 좋은 방법
q에서 카운트를 셀때 해당 큐 인덱스에서 count+1해주는 방식으로 하면 더 간단한 코드구현이 가능함.
queue<pair<pair<int, int>, int>이렇게 해서
좌표와 카운트 값을 함꼐 저장하고 만약 방문하지 않은 좌표라서 넣게 될시에 카운트를 1증가한 값으로 하여서 큐에
집어넣으면 더욱 스마트하다!!! 굳굳

2. 8방향 고려시 효율적인 방법
그리고 8방향 고려할때도 배열을 지정해서 하면 좋다.
int dx[] = {-2,-2,-1,-1,1,1,2,2}
int dy[] = {1,-1,2,-2,2,-2,1,-1}

이 책을 효율적으로 읽는 방법

타이탄들의 매일의 작은 습관, 태도, 명상, 주문, 보충학습 계획, 즐겨하는 질문들, 독서법 등등에 더 각별히 주목하라 -15p-

1장 세상에서 가장 성공한 사람들의 비밀

01. 승리하는 아침을 만드는 5가지 의식

-> 이미 내가 거의 하고 있는 것들이었다. 잘하고 있다는 것을 확인할 수 있는 기회였다.

1) 일어나자 마자 잠자리 정리하라

2) 의자에 앉아, 10분 아침명상을 하라

3) 한동작을 5~10회 반복하라 ex) push up

4) 차를 마셔라

5) 아침일기 써라

- 감사기록 tips

1. 내게 정말 많은 도움을 주었거나 내가 높이 평가하는 오랜 지인들

2. 오늘 내게 주어진 기회

3. 어제있었던 근사한 일

4. 가까이 있거나 눈에 보이는 단순한 것들

- 밤에쓰는 일기

1. 오늘 있었던 굉장한 일 (3가지) -> 한달에 한번은 꼭 다시 보기를 권장한다.

2. 오늘은 어떻게 더 좋을 날로 만들었나? (3가지)

15. 천재와 싸워 이기는 법

- 2가지 분야에서 상위 25%가 되어라

- 두가지 이상의 괜찮은 능력을 결합해 자신을 보기 드문 존재로 만들어야 한다. 그때 우리는 1등을 이길 수 있다.

[적용]

1. 컴퓨터 공학 분야

2. 글쓰기 분야(독서) or 법률적인 분야

21. 한테암불로가 되어라

- 우리가 아는 훌륭한 스승보다 우리가 모르는 훌륭한 스승이 세상에는 더 많다.

- 중요한 것은 태도이다.

- 항상 타인을 섬기겠다는 자세를 가진 사람이 성공하지 못한 경우는 거의 보지 못했다.

24. 배거본더가 되어라

- 배거본딩 : 일상에서 최소 6주 이상 벗어나 여행을 하는 것을 의미한다. 충분한 시간을 갖고 떠나는 여행일 때, 비로소 우리는 일상과 삶을 새롭게 바꿔나갈 수 있다.

- 사람과 장소, 사물에 진심으로 흥미를 느끼는 모험가가 될때 다양한 기회를 얻을 수 있다.

- 배거본딩은 불확실함에 대처하는 능력을 길러준다. 세상을 정면으로 바라보고, 두려움과 마주하고, 습관을 바꾸고 새론운 사람과 새로운 공간에서 창의적인 관심과 흥미를 가꿔나가는 일이다.

제 2장 세상에서 가장 지혜로운 사람들의 비밀

01. 두려움을 극복하는 방법

두려움에서 벗어나지 못하는 이유는 당신의 삶을 너무 타인에게 맡기고 있기 때문이다. 당신이 진정 원하는 것과 향하는 것을 알면 타인의 중요성은 뚜렷하게 약해진다.

[생각]

- 주변환경이나 타인의 기대에 의해 살아가는 사람들은 불안해 한다.

- 항상 그들 스스로의 삶의 기준과 목표가 없기 때문이다. 그래서 걱정하고 불안해 한다.

- 오로지 나 자신으로 삶을 살아갈때 도전하고 세상과 맞써게 된다.

- "인생은 용기의 양에 따라 줄어들거나 늘어난다."

[적용]

나는 내 인생을 늘릴것이다. 어마어마하게 말이다. 항상 도전하고 새로움을 추구하며 타인의 틀에 갇히지 않는 사람이 될 것이다.

02. 오늘도 담대하게 뛰어들었는가(취약성에 관하여)

- 더 나은 사람이 되기 위해서는 나의 실수,한계,취약점을 드러내는 일에 두려워해서는 안된다.

- 많은 실수를 드러내는 사람일 수록 가장 열심히 노력하는 사람이다.

[적용]

영어공부에 있어서 내가 영어를 잘하지 못한다는 것 때문에 소극적으로 행동하지 말고 오히려 그 취약성을 드러내서 내영어 실력 향상을 위해 힘쓸것이다. 못하는 것을 들어내는 것이 더 나은 내가 되기 위한 출발점이다.

- 우리는 매일 2개의 질문을 던저야 한다.

- 나는 오늘 대담하게 뛰어들었는가?

- 나는 편안함 대신 용기를 선택하기 위해 어떤 취약성을 드러냈는가?

[적용]

Stay hungry, 항상 내 앞의 도전들을 향해 적극적으로 뛰어들고 용기를 내어 취약성을 드러내는 사람이 되자

- 기꺼이 먼저 자신에게 취약한 부분을 드러내는 사람을 세상은  더 높게 평가하고 도와준다.

- 상대방에게 도움의 기회를 제공하는 사람이 가장 용감하고 빠르게 성장한다.

- 두려울 때, 불안할 때 최악의 상황을 적어라. 그리고 생각하라.

- 최악을 조금 나은 상황으로 바꾸기 위해 지금 자신이 할 수 있는 것을 생각하고 실천하라.

03. 강력한 행동을 이끌어 내는 7가지 질문

- 우리는 부를 쫓는 것보다 가난을 연습함으로써 더 큰 자유를 얻을 수 있다. 타이탄들은 이렇게 말했다. "하루에 한번 한달에 한번 분기에 한번, 정기적으로 괴로워하면 괴로움이 사라질 것이다."

[적용]

나의 괴로움은 피곤이다. 한달에 한번 밤새는 날을 정해서 피곤과 싸우는 법을 연습하자. 잠을 자지 않고 2일을 버티는 것이다. 내가 극복할 수 있다는 것을 내 스스로에게 알려주자. 내 친김에 이 챕터를 읽은 당일날 피곤연습을 시작했다. 2021/06/27일이었다. 하루 밤새고 나니 어느정도 피곤에 대한 면역력이 올라간것 같은 느낌이 든다.

04. 답은 하나가 아니다

- 모르는 것은 알때까지 계속 질문하라. 그것이 질문의 정수로 가장 좋은 질문법이다. 정확하게 알때까지 질문하고 그것을 자신의 앎에 적용하기 위해 치열하게 연구하고 고민해라.

제 3장 세상에서 가장 건강한 사람들의 비밀

01. 건강한 삶을 살기 위해 구글 개척자의 3가지 습관(행복빌기)

- 무작위로 선택한 사람의 행복을 속으로 30초간 빌기 -> 당신의 마음이 편안해지고 행복해지는 것이 느껴질 것이다!

[적용]

자기전에 내가 행복을 빌 세 사람을 떠올린다. 3~5분 동안 그 사람들의 행복을 빌고 기도한다. 이 쳅터를 읽고 난 날부터 시작하여 9일째 진행중이다. 하루의 마무리로 매우 좋다!

06. 매일 자신감을 쌓는 가장 좋은 연습(솔선수범)

- 그들은 언제나 자신이 먼저 하겠다고 큰소리로 말한다. 상점에서 계산할때도 먼저 돈을 내고 먼저 인사를 건내고 낯선이와 스쳐 지나가면서 시선이 마주칠 때도 먼저 미소를 보낸다.

- 이들이 엄청난 운동력 뒤에는 매사에 솔선수범하는 습관이 숨겨져 있다.

- 적극적으로 먼저 나서서 타인을 돕고 세상에 기여하느 습관은 몸과 정신의 건강을 이끈다.

- 매사에 주도적인 사람은 다른 이 보다 더 빨리, 더 멀리, 더 높이 뛸 수 있는 가능성이 크다. 이미 일상에서 솔선수범 함으로써 다양한 성취감을 맛보았기 때문이다.

10. 단 하나의 결단

- 눈에 보이는 발전이 없을 때 나타나는 좌절감은 탁월함을 향해 나가는 과정에서 필수 불가결한 일이다.

- 좌절감을 느끼지 못하는 사람은 아무것도 배우지 못한다. 탁월함은 좌절감에 대처하는 방법을 찾아낸 사람들이 가는 길이다.

- 그러니 괴로워할 일이 아니다. 재대로 된 길을 가고 있는지 점검하는 좋은 기회이다.

끝으로

도전하라

인생의 모든 과정은 선택을 가장한 도전이라고 생각한다. 적극적으로 도전하지 않으면 무엇이든 재대로 이룰 수 없다. 아침 침대정리 부터 꽤 큰 도전인 이들도 있을 것이다. 또 더 나은 내가 되기 위해서, 세상에 대해 더 알아가기 위해서, 더 좋은 체력을 기르기 위해서 우리는 끊임없이 도전해야 한다. 도전하라 매순간에.

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

문제

자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다.

매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다. 하지만 자두는 체력이 그다지 좋지 못해서 많이 움직일 수는 없다.

자두는 T(1≤T≤1,000)초 동안 떨어지게 된다. 자두는 최대 W(1≤W≤30)번만 움직이고 싶어 한다. 매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 자두가 받을 수 있는 자두의 개수를 구해내는 프로그램을 작성하시오. 자두는 1번 자두나무 아래에 위치해 있다고 한다.

입력

첫째 줄에 두 정수 T, W가 주어진다. 다음 T개의 줄에는 각 순간에 자두가 떨어지는 나무의 번호가 1 또는 2로 주어진다.

출력

첫째 줄에 자두가 받을 수 있는 자두의 최대 개수를 출력한다.

접근방식

- 재귀방식으로 접근했다.

- 재귀만으로는 시간초과가 발생하므로 dp를 활용한다.

- dp[현재시각][움직일수있는횟수][현재위치]로 설정했다.

- 탐색을 진행하면서 가지치기를 하는 경우

1. 이미 들어 있는 dp 값이 현재 sum 값보다 큰 경우 -> 같은 조건에서의 값이 더 작은 것이므로 굳이 탐색을 이어갈 필요가 없다.

2. 현재시각부터 남은 시간 동안 모든 자두를 먹는다고 가정해도 maxnum보다 작은 경우

#include <iostream>
#include <algorithm>

using namespace std;

int t;
int input[1000][3]={0};
int dp[1000][30][2]={0};
int maxnum=0;
void jadoo(int move, int x, int depth, int sum){
  if(depth > t) return ;
  if(input[depth][x]==1)
    sum++;

  if(dp[depth][move][x]==0){
    dp[depth][move][x] = sum;
  }else if(dp[depth][move][x] < sum){
    dp[depth][move][x] = sum;
  }else{ // dp값이 이미 더 크다면 탐색할 필요가 없다. 같은 조건에서 값이 더 작은 것이기 때문이다.
    return ;
  }

  if(maxnum < sum) maxnum = sum;

  // 남은 시간동안 자두를 모두 먹는다고 해도 maxnum보다 작다면, 굳이 탐색할 필요가 없다.
  if(t-depth-1 + sum < maxnum) return ;
  
  if(move!=0 && x==1){
    jadoo(move-1, x+1, depth+1, sum);
    jadoo(move, x, depth+1, sum);
  }else if(move!=0 && x==2){
    jadoo(move-1, x-1, depth+1, sum);
    jadoo(move, x, depth+1, sum);
  }else
    jadoo(move, x, depth+1, sum);
}
int main(){
  int w;
  cin >> t >> w;
  for(int i=0; i<t; i++){
    int x;
    cin >> x;
    if(x==1) input[i][1]=1;
    if(x==2) input[i][2]=1;
  }
  // 옮기고 시작하는 경우도 함께 고려해 준다.
  jadoo(w, 1, 0, 0);
  jadoo(w-1, 2, 0, 0);
  printf("%d\n", maxnum);
}

느낀점

예전에 그리디 문제풀면서 배웠던 개념(남은 시간동안 자두를 모두 먹는 경우와 현재 max값을 비교)을 적용해서 시간을 단축할 수 있어서 뿌듯했다.

거의 2배로 시간을 단축했다!

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

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

접근방식

수빈이의 이동 가능 방식이 -1, *2, +1 3가지 이므로 BFS를 활용해서 탐색을 진행하여 해를 구할 수 있다.

고려해야할 사항

- -1 이동 시 좌표가 음수가 되서는 안된다.

- +1와 *2이동 시 좌표가 100000이 넘어서는 안된다.

- depth가 깊어질 수 록 3^n만큼 기하급수적으로 늘어난다. 방문체크 배열을 사용하여 이를 해결한다.

- 어디까지가 1번의 이동인지 판단해야 한다.

1) start값을 q에 넣은 후 -1의 값을 갖는 key을 queue에 넣는다.

2)꺼낸 q의 값이 -1일때가 한번 이동을 마친 경우이므로 이때 횟수를 카운팅 해준다.

#include <iostream>
#include <queue>
#include <cmath>

using namespace std;

int x,y;
queue<int> q;
int v[100001]={0};

int bfs(int start){
  if(start==y) return 0;
  int key=-1, result=0;
  q.push(start);
  q.push(key);
  v[start]=1;

  while(!q.empty()){
    int x = q.front();
    q.pop();

    if(x == y)
      return result;

    if(x!=key){
      if(x-1 >= 0 && v[x-1]==0){
        q.push(x-1);
        v[x-1]=1;
      }
      if(x*2 <= 100000 && v[x*2]==0){
        q.push(x*2);
        v[x*2]=1;
      }
      if(x+1 <= 100000 && v[x+1]==0){
        q.push(x+1);
        v[x+1]=1;
      }
    }
    else{
      q.push(key);
      result++;
    }
  }
  return result;
}

int main(){
  cin >> x >> y;
  cout << bfs(x) << "\n";
  return 0;
}

마지막 몰입은 자신의 한계를 제거하고 평범함을 넘어 비범함으로 나아가는 방법을 알려준다. 학습 방법의 학습을 위한 로드맵을 제시하는 것이 그 목적이다.

목차

1. 마인드셋 

- 당신의 한계는 어디인가?

2. 동기

- 목적

- 원하는 것을 할  수 있는 능력, 에너지

- 작은 성공, 작은 실행과 행동

3. 올바른 방법

- 집중, 학습, 기억력 향상, 속독, 비판적 사고

들어가며 

현재의 마인드셋, 동기, 방법이 꿈을 달성하는 능력을 제한한다고 느끼는 사람들에게 이 책을 추천한다. 당신이  당신의 뇌를 더 뛰어나고 명석하게 사용할 수 있는 방법을 알려준다. 나의 한계를 넘어서고자 난 이책을 읽기 시작했다. 항상 '이만하면 됐지' 혹은 '이 정도면 만족해, 충분해' 하고 나 자신을 합리화 시키는 내 모습을 보며 한계를 뛰어넘고 싶다는 생각을 했다.

내가 얻은 것은 마인드셋에 관한 깊은 영감이다. 가오가 육체를 지배한다는 말이 있듯이, 우리는 자기 자신을 어떻게 규정하고 한계를 어떻게 인식하느냐에 따라 할 수 있고 없음이 판가름 난다. 내 안에 있는 잠재력을 발휘하기 위해서는 자신의 한계를 제한하지 않아야 한다. 우리에게 한계가 있다는 인식을 떨치게 해준다. 마지막 몰입은 우리가 얼마나 특별해지고 비범해 질 수 있는 능력을 가졌는지 깨닫게 해준다.

디지털 시대의 악당들

디지털 홍수- 우리는 정보기술의 고도화로 인해 매일 넘처흐르는 정보들을 언제 어디서든 접할 수 있다. 그리고 매 순간 새로운 정보들이 나오고 기존의 정보가 업데이트 되기도 한다. 이런 정보 과부화로 인해 우리가 정보로 둘러쌓인 환경으로부터 휴식을 온전히 취하지 못한다.

디지털 주의 산만-스마트폰의 발전으로 SNS등의 알림이 우리 삶을 둘러싸고 있는 수준이다. 이는 습과넉으로 휴대폰을 처다보게 만든다. 우리의 주의를 빠았는다. 중요한 것에 집중하게 못하도록 한다.

디지털 치매-우리는 직접 기억하고 정보를 활용하기 보다 저장매체에 크게 의존하며 살아간다. 물론 이러한 의존성이 편리함을 가져다 준다. 하지만 동시에 장기기억력도 손상시킨다. 항상 대신 기억해주는 것에 익숙해져있기 때문이다.

디지철 추론-정보기술이 우리의 비판적 사고 능력을 앗아 간다. 검색을 통해 지식 습득하기가 편리해졌다. 하지만 그만큼 스스로 비판적으로 사고하는 과정도 빼앗아 간다. 특정 주제에 대해 다양한 입장을 검색을 통해 접할 수 있지만, 현실에서는  자신의 편협적인 사고를 더욱 굳히는 쪽으로 진행되는 경우가 대다수이다.

뇌가소성

- 우리 뇌는 변화할 수있다. 환경에 따라 변한다. 따라서 조형이 가능하다.

- 우리가 어떤 새로운 것을 배울때마다 뇌는 새로운 시냅스 연결이 생성된다. 즉 새로운 신경경로를 생성한다. 우리뇌는 유연하다. 바꿀 수 있다.

- 우리는 뇌를 한계 돌파를 위한 상태로 바꿀 수 있다. 저자는 그 방법을 제시한다.

마인드셋 :매일 생산적인 마인드셋으로 접근하는 방법

- 한계를 뛰어넘는 마인드셋을 가져라. 마인드셋은 어떤 상황이나 환경을 어떻게 바라보는 지에 대한 태도, 신념, 가정을 말한다. 자신의 잠재력을 충분히 받아드릴 때 그 힘은 커지게 된다.

- 대부분의 사람들은 초능력이 있다. 이 초능력은 당신이 할 수 없다고 생각되는 것을 할 수 있는 능력이다. 자신의 한계를 의식해 올바른 마인드셋을 가지지 못한다.

- 부정적인 자기 스스로와의 대화와 제한된 신념과 맞써야 한다. 당신의 내면의 부정적인 목소리에 한계를 두지 말라. 학습방법의 학습의 핵심은 limitless 한계초월이다.

제한적인 신념을 극복하는 방법

- 그 신념의 근원을 파악하려 시도해라. 근원을 인지하면 당신의 한계를 제한하는 그 신념이 사실이 아닌 의견일 뿐이라는 것을 깨닫게 될 것이다.

- 그리고 그 신념의 한계가 정말 존재하는지, 집증해줄 증거가 존재하는지 그 증거 조차 머릿속 소음에 오염된 것은 아닌지 확인해라. 대부분 사실이 아니다. 그 후 당신이 추구하는 성공을 위한 참인 신념을 만들어라

잠재력을 가두는 일곱 거짓말

저자는 잠재력을 발휘하지 못하도록 하는 7가지 잘못된 믿음에 대해 반박한다. 그 중 인상깊었던 몇가지만 간단하게 소개하겠다.

1. 지능은 타고 나는 것이다.

지능은 유동적이다. 변하기 쉬울 뿐 아니라 성장형 마인드셋을 기르는 능력에 따라 좌우된다.

2. 실수가 곧 실패다.

실수한적 없는 사람은 새로운 것을 시도하지 않는 사람이다. 실수는 뭔가 시도하고 있다는 증거며, 실수를 통해 우리는 발전한다. 실패같은 것은 없다. 배움의 실패가 있을 뿐이다.

3. 이는 것이 힘이다.

아는 것이 중요한게 아니다. 아는 것을 통해 어떻게 행동하느냐가 중요하다. 배운대로 행동하고 실천해라 힘은 지식과 행동의 곱이다.

4. 천재는 따로 있다.

주변을 둘러보면 가끔 가다 1명 씩 정말 천재적인 것 처럼 보이는 사람이 있다. 하지만 사람들은 그 사람이 얼마나 노력하고 연습했는지에는 거의 관심이 없다. 천재는 타고난 것이 아니라 심층적인 연습을 통해 만들어 진다. 

내가 얻은 영감

이 쳅터를 읽고 난 후에, 나의 한계를 풀어버리고 무엇이든지 도전해야 겠다는 뜨거운 열정이 생겼다. '대중들을 상대로 자신있게 발표하지 못하는 나', '영어에 자신감 없는 나', '낯선 사람에게 쉽게 다가가기 힘들어 하는 나'는 더 이상 진실이 아니라  '의견'일 뿐이라는 것을 깨달았다. 나의 무한한 잠재력을 바라볼 수 있게 되었다.

제한적 신념은 그릇된 통념일 뿐이다. 사실이 아니다.

동기 :몰입해야할 이유를 반드시 발견하라

최적의 동기수준으로 접근하는 방법

저자는 동기를 다음과 같이 정의한다.

동기 = 목적x에너지x작은행동^3

열정과 목적

당신의 열정과 목적과 정체성과 가치관을 생각해 보아라. 그것들이 당신이 행동할 이유의 토대가 될 것이다. 충분한 동기를 줄 수 있다.

열정은 당신이 무언가에 기쁨을 느끼는 것이다. 열정을 목적을 부른다. 열정을 찾으려면 스스로 새로운 것을 찾고 새로운 환경에 부딧쳐 당신의 마음을 뜨겁게 하는 것이 무엇인지 탐색해야 한다.

고통은 나를 앞으로 나아가게 만든다.

- 동기는 행동의 연료가 되는 고통스럽고 즐거운 감정이다. 동기는 어디서 오는가?

- 동기는 목적, 즉 행동을 하거나 행동을 하지 않을떄 생기를 결과를 충분히 느끼고 연관짓는 데서 나온다. 뭔가 조치를 취하지 않으면 느끼게 될 고통을 진정으로 느껴라. 그것이 변화를 지속시키고 끝까지 유지시키는 유일한 방법이다.

- 고통을 당신을 움직이게 하는 원동력으로 사용해라.

- 그리고 그 일을 했을때 얻는 긍정적이고 이상적인 결과를 적어보아라

적용

- 아무 어려움 없이 외국인과 영어로 대화하는 나. 쉽게 영어 전공 수업을 이해하고 학습하는 나. 영어로 된 논문을 찾아 읽는 데 별 어려움이 없는 나. 영어에 대한 장벽을 허물었다는 데에 아주 커다란 자부심을 만끽하는 나. 이런 모습들을 상상하는 것을 통해 큰 동기부여를 얻을 수 있었다.

- 동기는 결국 내 안에서 찾아야 한다는 것을 깨닫게 되었다.

- 환경이 중요하지만 환경을 변화시켜야 겠다는 동기 또한 내 안에서 나오는 것이다. 때문에 동기는 결국 내 안에 있다는 것이 큰 울림이었다.

- 군대에 오기전 나는 내가 하고 하고 있는 일이 힘들고 지칠 때마다 외부에서 더 많은 동기를 얻기를 바랐다.심리 교수님을 만나 상담 받기도 했다. 더 성장하고 나은 사람이 되고 싶고 열심히 하고 싶었다. 더 큰 동기부여를 얻으려면 어떻게 해야 하나 이런 고민들을 많이 했다. 이 책을 통해 동기는 나의 안에 있다는 것을 깨닫게 되었다.

열정 - 컴퓨터에 대해 알아가고 코딩하여 무엇가를 만드는데 열정이 있다.

목적 - 기술을 활용해 더 살기 좋은 세상을 만들고 사람들을 돕고 변화시키고 싶다.

가치관 - 사랑, 학습의 추구

정체성 - 남 주기위해 공부하는 자

이러한 동기의 결과물은 몰입 즉 행동이다. 궁극적으로 동기는 당신의 가치관과 정체성으로 인해 당신이 매일 수행하는 습관과 일상 그 자체이다.

방법

집중, 학습, 기억, 속독, 사고

5가지 영역에서 가속학습과 메타학습의 원리를 배운다.

1. 집중

- 집중은 훈련되는 것이다. 의식적으로 노력해서 길러야 한다.

- 멀티테스킹은 생리적적으로 불가능하다. 매우 비효율 적인 방법이다.

- 환경을 정리해라. 주의를 분산시키는 것들을 없애라.

- 주의 분산을 허용할 시간 마련해라. 예를 들어 이러이러한 걱정들은 4시 45분에 하자라고 마음 먹으면 편안한 마음을 가질 수 있다.

2.학습

학습의 한계를 벗어나기 위한 방법

1. 능동적으로 회상하라

2. 간격을 두고 반복하라.

3. 현재 상태를 확인하다 - 바른 자세는 호흡을 촉진하는 등 학습에 긍정적이다. 바른자세로 앉아라.

4. 뇌를 온전히 사용해서 들어라

HEAR기법

Halt(정지) : 화자 외 모든 방해요소를 정지시키고 온전히 화자에게 집중하라

Empathy(공감) : 화자의 입장에 공감할 때 더 많은 것들을 배운다.

Anticipate(기대) : 기대감을 가지고 들어라 감정과 연결된 학습만이 장기기억으로 연결된다.

Review(복습) : 되새겨 보고 자신의 말로 바꾸어 보아라

5. 유의해서 필기하라

- 필기는 자신의 어휘로 정리하며 내용을 소화하는 것이다.

- 자신의 말로 옮기는 것이 중요하다. 그대로 받아적는 것은 의미가 없다.

- 필기의 목적을 명확히 해라.

- 손으로 쓰며 필기하면 요약하게 되므로 정보를 받아드리는 양이 많아진다. 노트북 보다는 손글씨로 필기하라. 노트북을 사용하면 생각하고 요약하기 보다 그대로 받아 적게 된다.

3. 기억

기억력은 훈련할 수 있고 그 방법을 배울 수 있다.

더 많이 기억할수록 더 많이 배울 수 있다.

MOM기법

Motivation(동기부여) - 기억해야할 개인적인 동기를 부여하라. 기억력 강화훈련을 하려면 아주 강한 동기부여가 필요하다.

Observation(관찰) - 기억하고 싶은게 있는 상황에서 온전히 집중하라.

Method(방법) - 시각화하라. 연상하여 기억하라. 감정과 연관하여 기억하면 효과적이다.

그 외에는 연상기억법에 대한 소개를 많이 한다. 연상기억법은 한정적인 정보를 기억하는데 도움이 되지만 방대한 정보를 꾸준히 축적해 나가는 과정에서 비효율적이다. 연상기억법을 사용하는 경우 공부량이 늘면 떠올리거나 기억해야할 심상과 그림이 많아지고 이에 한계가 발생한다.

4. 속독

속독의 방해요소

1. 되읽기(안구회귀)

2. 뒤떨어진 읽기 능력 - 개선시켜야 한다.

3. 속발음 - 읽을 때 속으로 소리내는 것

손가락이나 펜으로 짚어가며 읽으면 집중력이 흐트러지는 것을 막아주고 주의를 지속적으로 집중할 수 있도록 도와준다.

실제 적용해서 책을 읽어보니 도움이 컸다. 집중력을 꽤 오랫동안 유지하도록 큰 도움을 받았다.

대부분의 소개한 방법들이 나는 알고 있었던 당연한 것들이었다. 아마 대부분의 사람들은 성공에 대한 어느정도의 답은 누구나 알고 있을 것이다. 실행하지 않아서 변하지 않는 것 뿐이다. 

마치며

내가 이 책을 통해 얻은 가장 큰 것은 마인드셋에 관한 깊은 영감이다. 우리 뇌는 생각보다 훨씬 강력한 도구로 사용될 수 있다는 것이다. 한계는 그 누가 결정하는 하는 것이 아니다. 당신의 부정적인 생각이 규정하는 당신의 한계는 사실이 아닌 의견일 뿐이라는 것을 기억하고 한계를 뚫기위해 노력하자. 할 수 있다. 당신은 충분히 해낼 수 있는 초능력을 지녔다. 단지 그 사실을 모르거나 받아들이지 않을 뿐이다. 학습된 무기력에 빠지지 말자.

무엇보다 자신을 사랑하고 믿고, 한계를 뛰어넘어라. 당신은 충분한 초능력을 가지고 있다.

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

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

접근방식

이 전글의 다룬 '유기농 배추'문제와 거의 유사하다. bfs 혹은 dfs의 개념을 이용해 간단히 풀 수 있다.

이 글에서는 bfs를 사용했다.

- input배열을 할당하고 이 배열 전체를 탐색하면서 bfs를 진행한다.

- 아파트(1)가 발견되면 bfs를 진행하면서 해당 bfs턴에 발견된 아파트 수를 벡터인 result에 넣는다.

- input배열 전체 탐색이 완료되면 result에는 bfs가 진행된 수 만큼의 정수값들이 할당되어 있을 것이다.

- 이를 오름차순으로 sort한 후 출력한다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>

using namespace std;

int input[25][25]={0,};
vector<int> result;
queue<pair<int, int>> q;
int v[25][25]={0,};
int n;

int bfs(int a, int b){
  int c=0;
  q.push(make_pair(a,b));
  v[a][b]=1;
  input[a][b]=1;
  while(!q.empty()){
    c++;
    int x = q.front().first;
    int y = q.front().second;
    q.pop();
    if(v[x-1][y]==0 && input[x-1][y]==1 && x!=0){ // 위
      v[x-1][y]=1;
      input[x-1][y]=1;
      q.push(make_pair(x-1,y));
    }
    if(v[x+1][y]==0 && input[x+1][y]==1 && x!=n-1){ // 아래
      v[x+1][y]=1;
      input[x+1][y]=1;
      q.push(make_pair(x+1,y));
    }
    if(v[x][y-1]==0 && input[x][y-1]==1 && y!=0){ // 왼쪽
      v[x][y-1]=1;
      input[x][y-1]=1;
      q.push(make_pair(x,y-1));
    }
    if(v[x][y+1]==0 && input[x][y+1]==1 && y!=n-1){ // 오른쪽
      v[x][y+1]=1;
      input[x][y+1]=1;
      q.push(make_pair(x,y+1));
    }
  }
  return c;
}

int main(){
  int count=0;
  string str;
  cin >> n;
  for(int i=0; i<n; i++){
      cin >> str;
    for(int j=0; j<n; j++){
      input[i][j] = str[j]-48;
    }
  }
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      if(input[i][j]==1 && v[i][j]==0){
        int x = bfs(i,j);
        result.push_back(x);
        count++;
      }
    }
  }
  sort(result.begin(), result.end());
  
  printf("%d\n", count);
  
  int k = result.size();
  //printf("result size : %d\n", k);
  for(int i=0; i<result.size(); i++)
    printf("%d\n", result[i]);
}

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

문제

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.

출력

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

접근방식

- bfs혹은 dfs을 사용해서 간단히 풀 수 있는 문제이다.

- 이 글에서는 bfs를 사용했다.

- input 배열들을 쭉 스캔하면서 배추가 발견되면 bfs를 진행하면서 배추가 있던 자리(1)를 0으로 바꿔준다.

- 배열을 모두 탐색했을때 bfs의 진행 횟수가 곧  필요한 최소 배추희지렁이의 수가 된다. 

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int input[50][50]={0};
queue<pair<int, int>> q;
int m,n,x; 

void bfs(int a, int b){
  int v[50][50]={0};
  v[a][b]=1;
  input[a][b]=0;
  q.push(make_pair(a,b));
  while(!q.empty()){
    int x,y;
    x = q.front().first;
    y = q.front().second;
    q.pop();
    if(v[x-1][y]==0 && input[x-1][y]==1 && x!=0){
      v[x-1][y]=1;
      input[x-1][y]=0;
      q.push(make_pair(x-1,y));
    }
    if(v[x+1][y]==0 && input[x+1][y]==1 && x!=n-1){
      v[x+1][y]=1;
      input[x+1][y]=0;
      q.push(make_pair(x+1,y));
    }
    if(v[x][y-1]==0 && input[x][y-1]==1 && y!=0){
      v[x][y-1]=1;
      input[x][y-1]=0;
      q.push(make_pair(x,y-1));
    }
    if(v[x][y+1]==0 && input[x][y+1]==1 && y!=m-1){
      v[x][y+1]=1;
      input[x][y+1]=0;
      q.push(make_pair(x,y+1));
    }
  }
}
int main(){
  int t; cin >> t;
  for(int w=0; w<t; w++){
    cin >> m >> n >> x;
    int result=0;
    fill(&input[0][0], &input[n-1][m-1], 0);
    for(int i=0; i<x; i++){
      int a,b; cin >> a >> b;
      input[b][a]=1;
    }
    
    for(int i=0; i<n; i++)
      for(int j=0; j<m; j++)
        if(input[i][j]==1){
          bfs(i,j);
          result++;
        }
      printf("%d\n", result);
  }
    return 0;
}

느낀점

BFS/DFS에 대해 점점 익숙해 지는 것 같아 기분이 좋다. 다음에는 좀 더 어려운 문제에 도전해봐야겠다.

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

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

출력

여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

접근방법

조금 응용된 BFS문제이다.

1. 주어지는 익은 토마토가 여러개라면 각각의 토마토가 하루씩 주변 토마토를 익힌다는 점을 고려해야 한다.

2. 또한 구조적으로 익을 수 없는 경우도 고려해야 한다.

1. 각 토마토별 1단계씩 BFS

- start라는 벡터를 하나 생성해서 여기서 초기값으로 주어진 익은 토마토들을 넣는다.

- bfs안에서 익은 토마토 별로 1단계씩 bfs를 진행한다.

- KeyX와 KeyY를 사용하는 방식으로 한단계씩 진행되는 bfs를 카운팅 할 수 있도록 했다.

- 만약 익은 토마토가 주어졌다면(익은 토마토가 없는 경우 upper bound error가 날 수 있다.)

- 첫번째 익은 토마토의 좌표값이 KeyX, KeyY값이 된다.

- bfs가 한차례씩 끝날때 마다 q에 KeyX와 KeyY값을 넣어 q에서 꺼넨 값이 key값일 경우 count를 한다.

2. 익지 못하는 토마토 판별

- bfs가 다 끝났음에도 익지 않은 토마토가 남아있다면  -1을 출력한다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

queue<pair<int, int>> q;
int input[1000][1000]={0};
int v[1000][1000]={0};
vector<pair<int, int>> start;
int m,n;

int bfs(vector<pair<int, int>> start){
    int k=0, count=0;
    int kx, ky;
    for(int i=0; i<start.size(); i++){
        int x,y;
        x = start[i].first;
        y = start[i].second;
        v[x][y]=1;
        q.push(make_pair(x,y));
    }
    if(start.size()>=1){
        kx = start[0].first; // Put key value 
        ky = start[0].second;
    }
    q.push(make_pair(kx, ky));
    while(q.size() > 1){ // 1이면 종료
        k++;
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        if(k!=1 && x==kx && y==ky){
            count++;
            q.push(make_pair(kx,ky));
        }else{
            //토마토가 안익었고 즉 0 이고 방문 안했으면 넣는다. 방문체크까지
            if(input[x-1][y]==0 && v[x-1][y]==0 && x!=0){ // 위쪽 
                v[x-1][y]=1;
                q.push(make_pair(x-1, y));
                input[x-1][y]=1;
            }
            if(input[x+1][y]==0 && v[x+1][y]==0&&x!=n-1 ){ // 아래쪽 
                v[x+1][y]=1;
                q.push(make_pair(x+1, y));
                input[x+1][y]=1;
            }
            if(input[x][y-1]==0 && v[x][y-1]==0 &&y!=0){ // 왼쪽
                v[x][y-1]=1;
                q.push(make_pair(x, y-1));
                input[x][y-1]=1;
            }
            if(input[x][y+1]==0 && v[x][y+1]==0 && y!=m-1){ // 오른쪽 
                v[x][y+1]=1;
                q.push(make_pair(x, y+1));
                input[x][y+1]=1;
            }
        }
    }
    return count;
}

int main(){
  cin >> m >> n;
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      cin >> input[i][j];
    }
  }
  // 익은 토마토는 방문할 필요 없으므로 방문체크한다.
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      if(input[i][j]==1)
        start.push_back(make_pair(i,j));
    }
  }
  int result = bfs(start);
  for(int i=0; i<n; i++)
    for(int j=0; j<m; j++)
      if(input[i][j]==0){
        printf("-1\n");
        return 0;
      }
  printf("%d\n", result);
  
  return 0;
}

느낀점

하루가 지나는 것을 인식하는 더 쉬운 방법이 있을 것 같다. 약간 비효율적인 방식을 채택한것 같지만 keyx,y값을 정해서 푸는 방법도 나름 창의적인 것 같기도 하다.