BEEZI life

https://www.slideshare.net/SuhyunPark23/kucc-2022-4

Bring

물건이나 사람을 움직이는것을 뜻한다.

움직임의 방향은 다음과 같다.

• 화자 -> 청자
• 청자 -> 화자

In both of the following examples, the speakers are seeing things from A’s viewpoint – things will move to the place where A is:

A: Are you going to the bedroom?

B: Yes.

A: Can you bring me my grey sweater? It’s on the bed.

B: Yeah. (B will return with the sweater to the place where A is.)

Not: Can you take me my grey sweater?

A: Are you coming to our place on Friday night?

B: Yes. Do you want me to bring my guitar? (B will carry the guitar to the place where A will be.)

움직임의 방향이 한 가지 더 있다.

• 어딘가 다른 곳 -> 청자 / 화자

[on the telephone]

A: Did Laura bring you anything for your birthday?

B: Yes. She brought me some flowers and a CD. (Laura is C, another person, in a different place from A or B. She moved with something to where B, the listener, was.)

Take

역시 물건이나 사람을 움직이는 것을 뜻한다.

움직임의 방향은 다음과 같다.

• 화자 / 청자 -> 어딘가 다른 곳

[university assistant at a central faculty office, speaking to a student]

You have to fill in this form and then take it to the English Department to get it stamped. (the assistant and the student are at the central faculty office – the English Department is a different place)

Not: … and then bring it to the English Department

A: I can take you to the station tomorrow. What time’s your train? (Neither A nor B is at the station; it is a different place.)

B: Thanks. It’s eight-thirty.

Fetch

역시나 물건이나 사람을 움직이는 것을 뜻하지만, 조금 더 구체적이다.

현재 위치에 있어야 하는데 없을 때 사용한다.

움직임의 방향은 한 종류이다.

• 현재 위치 -> 목표의 위치 -> 현재 위치

If you’re going to the garage, can you fetch that green bag with the paintbrushes in it? Or Can you get that green bag …

Right. It’s five o’clock. I’d better go and fetch my mother from the station.

Bring, take and fetch: typical error

• 청자의 시점에 물건이 보일 때는 take를 사용하지 않는다.

A: Are you and Josh coming to our party?

B: Yeah. Sheila invited us.

A: Good. Can you bring some CDs? We’re a bit short of music.

Not: Can you take some CDs?

출처 : https://dictionary.cambridge.org/ko/문법/영국식-문법/bring-take-and-fetch

vim

http://vimgenius.com

https://openvim.com

https://vim-adventures.com/

git

https://learngitbranching.js.org/?locale=ko

css select(CSS 선택자)

https://flukeout.github.io

Regular Expression(정규표현식

• Regex 를 시각화 해서 볼 수 있다.
• https://regexper.com/

• 단계에 따라서 배우고, 문제를 풀 수 있다.
• RegexOne - Learn Regular Expressions - Lesson 1: An Introduction, and the ABCs

• Regex 를 디버깅 해볼 수 있다.
• regex101: build, test, and debug regex

문제

이렇게 numbers배열이 주어지면 각 원소들을 조합해서 가장 큰 수를 만드는 문제이다.

접근

처음 시도했던 접근 방법은 이렇다.
일단, 두 수를 비교했을 때 어떤 수가 앞에 와야 하는지 생각해봤다.

1. 맨 앞자리수가 커야 한다.
예를 들어서, 18과 2를 비교했을 때 만들 수 있는 조합은 182와 218인데
218이 더 큰 것을 보면 앞 자릿수가 커야 조합했을 때 큰 수 를 만들 수 있다.

2. 앞자리수가 같다면 마찬가지 논리로 뒷자리 수가 커야 한다.
예를 들어서, 28과 27을 비교했을 때 만들 수 있는 조합은 2827과 2728인데
2827이 더 큰 것을 보면 알 수 있다.

3. 모든 자리의 숫자가 같지만 자릿수가 다르다면, 자릿수가 같을 때까지 맨 앞의 수를 넣은 후 비교한다.
예를 들어서 382와 38을 비교했을 때,
382와 (38에 맨 앞 자릿수인 3을 붙인 383을 비교한다.
그렇게 하면 38382가 만들어지는데 이것은 다른 조합인 38238보다 더 큰 것을 알 수 있다.

4. 이렇게 해서도 모두 같으면 더 작은 수가 더 큰 조합을 만들 수 있다.
예를 들어서, 383과 38을 비교했을 때 만들 수 있는 조합은 38383과 38338인데
38383이 더 큰 것을 보면 수가 더 적은 38이 앞에 있는 상황인 것을 알 수 있다.

이렇게 해서 코드를 짜면 아래와 같다.

bool compare(const int& a, const int& b){
    string sa=to_string(a), sb=to_string(b);
    string tmp1=sa+sb, tmp2=sb+sa;
    return stoi(tmp1)>stoi(tmp2);
}

시행착오

하지만 이 코드에는 예외상황이 발생한다.

예를 들어서 [10,101,1]이 주어졌을 때 위의 논리대로 하면

1. 번으로는 모두 같고, 2. 번으로도 모두 같다.

이제 3. 번으로 비교하면 1 > (10 , 101) 순서가 된다.

이것을 4. 번으로 비교하면 1 > 10 > 101 이고, 이것으로 만든 수는 110101이 된다.

하지만, 실제로 가장 큰 수는 110110, 즉 1 > 101 > 10 순서가 된다.

깨달음

문제를 너무 복잡하게 생각했다.

이 문제는 여러 가지 수의 조합을 따져봤을 때, 가장 큰 조합을 만드는 것이다.

그렇다면 두 가지 수를 비교했을 때도 조합을 따져본 뒤, 가장 큰 조합을 만들 수 있는 배열을 만들어 주면 되는 것이다.

다시 위의 예를 들어서 101과 10을 비교한다고 했을 때

두 수로 만들 수 있는 조합 10110과 10101을 비교했을 때 10110이 더 크므로

101 > 10 순서를 만들어 주면 되는 것이다.

이것을 코드로 구현해보면 아래와 같다.

bool compare(const int& a, const int b){
    string sa=to_string(a), sb=to_string(b);
    if(sa.length()==sb.length()) return a>b;
    while(sa.length()!=sb.length()){
        if(sa.length()>sb.length()) sb.push_back(sb.front());
        if(sa.length()<sb.length()) sa.push_back(sa.front());
    }
    if(stoi(sa)==stoi(sb)) return a<b;
    return stoi(sa)>stoi(sb);
}

이렇게 하면 모든 배열을 가장 큰 수의 조합으로 만들어 줄 수 있다.

단 한 가지 예외 사항이 있는데 [0,0]이 주어졌을 경우에는 00이 출력되지만 답은 0이다.

이것을 예외 처리해주면 정답 코드는 아래와 같다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(const int& a, const int& b){ /* 위와 같음 */ }

string solution(vector<int> numbers) {
    string answer = "";
    sort(numbers.begin(), numbers.end(), compare);
    if(numbers[0]==0) return "0";
    for(int i=0; i<numbers.size(); i++){
        answer+=to_string(numbers[i]);
    }
    return answer;
}

앞으로

문제가 주어졌을 때, 문제를 곧이곧대로 보는 방법도 시도해보는 연습을 해야겠다.

반열림구간 [start, end)에서의 quick sort template

// reference를 불러와서 실제 배열에도 swap의 결과를 반영한다.
void swap(int& a, int& b){
  int tmp=a;
  a=b;
  b=tmp;
}

void qsort(vector<int>& arr, int start, int end){
  // 분할된 원소가 0개이거나 1개일때까지 함수 호출
  // start+1==end일 때, 원소의 개수는 1개
  if(start+1>=end) return;

  int pivot=start; 
  // 값 설정 기준 : 첫번째 원소

  int bigger=start+1; 
  // bigger : pivot보다 큰 원소를 찾는 index
  // 값 설정 기준 : pivot + 1

  int smaller=end-1; 
  // smaller : pivot보다 작은 원소를 찾는 index
  // 값 설정 기준 : 마지막원소

  // `bigger`와 `smaller`이 교차할때 까지 pivot보다 크거나 작은 원소들을 서로 교환한다.
  while(bigger<=smaller){
    // end는 아무 원소도 가리키지 않으므로 end보다 작아야한다.
    // bigger이 가리키는 원소가 pivot이 가리키는 원소보다 작으면 계속 bigger을 키운다.
    while(bigger<end && arr[bigger]<=arr[pivot]) ++bigger;

    // smaller은 나중에 pivot과 swap해야하기 때문에 pivot의 index인 start와 같으면 안된다.
    // 역시, smaller이 가리키는 원소가 pivot이 가리키는 원소보다 크면 계속 smaller을 줄인다.
    while(start<smaller && arr[pivot]<=arr[smaller]) --smaller;

    // bigger과 smaller이 교차하면 종료한다.
    if(bigger>=smaller) break;

    // 교차하지 않았다면 서로가 가리키는 원소를 swap하고 다시 반복한다.
    swap(arr[bigger], arr[smaller]);
  }
  // 교차했다면 pivot과 smaller가 가리키는 원소를 서로 교환한다.
  // 이렇게 하면 pivot 왼쪽에는 pivot보다 작은것, 오른쪽에는 pivot보다 큰것이 위치한다.
  swap(arr[smaller], arr[pivot]);

  // pivot을 기준으로 오른쪽과 왼쪽으로 나눠서 다시 정렬을 수행한다.
  qsort(arr, smaller+1, end);
  qsort(arr, start, smaller);
}

Class 3의 문제를 모두 풀었다.

여기에서 기초적인 지식들을 많이 얻고 부족한 점들을 많이 보완할 수 있었다.

배운것 : map, set, 기초적인 문자열 다루기, Floyd-Warshall
보완한 점 : 재귀, 분할정복, 그래프문제

추가로 최근에 풀어본 프로그래머스 실력체크 Level 2도 첨부한다.

다음목표 : Class 4, Level 3

한글로 써도 영어가 너무 많이들어가길래 영어로 썼다.

c++11부터는 erase의 매개변수로 const_iterator이 들어간다.
정확히 뭔지는 모르겠으나.
set.erase(set.begin());을 하면 잘 되는데
set.erase(set.rbegin());을 하면 오류가 난다.

똑같은 iterator인데 왜 안되는지는 잘 모르겠으나 해결방법을 발견했다.

int main()
{
    std::set<int> set;

    set.insert(15);

    std::cout << set.size() << " ";

    auto ri = set.rbegin();

    auto i1 = --ri.base();

    auto i2 = --set.end();

    assert(i1 == i2);

    set.erase(i1);

    std::cout << set.size() << std::endl;
}

이런식으로 하면 된다고 하는데
나는 그냥 가볍게 아래와 같이 작성했다.

auto it=set.rbegin();
set.erase((--it.base()));

1. 배열을 반복해서 뒤집어야 하는 경우에는 포인터의 개념을 사용하면 시간복잡도를 상당히 줄일 수 있다.

vector<int> arr={1,2,3,4,5};
reverse(arr.begin(), arr.end());

for(auto it=arr.begin(); it!=arr.end(); ++it) { printf("%d ", *it); }

위 코드에서 뒤집기를 m번 할때, 시간복잡도가 \\( O(m\*N^2) \\)이지만

vector<int> arr={1,2,3,4,5};
bool rev=true;
if(rev){
    for(auto it=arr.rbegin(); it!=arr.rend(); ++it) { printf("%d ", *it); }
}else{
    for(auto it=arr.begin(); it!=arr.end(); ++it) { printf("%d", *it); }
}

위 코드는 뒤집기를 m번 할 때, 시간복잡도가 \\( O(N^2) \\)이다.

2. 문자열에 숫자를 추가할 때, 10을 넘어간다면 다른 방법을 사용해야한다.

vector<int> arr={1,2,3,4,5};
string answer="";
for(auto it=arr.begin(); it!=arr.end(); =+it){
    answer+=(*it+'0");
    answer+=",";
}

위 코드대로 한다면 answer="1,2,3,4,5"가 제대로 저장된다고 생각할 수 있다. 하지만 10을 넘어가게 된다면 전혀 예상치 못한 답이 출력될 수 있다.

vector<int> arr={1,2,3,10,15} 라고 한다면

answer="1,2,3,:,?" 가 저장될 것이다.

그 이유는 0의 ASCII코드가 48, :은 58, ?은 63이기 때문이다.