흔적

알고리즘에서 효율성은 경진 프로그래밍의 핵심이다.

• 빅오 표기법 (Big-O Notation) : 입력에 대한 최고차항의 상수항을 제거한 표기법 ( ex. 3n^2+2n = O(n^2) )
• 시간복잡도 : 시간복잡도는 입력에 대해 알고리즘이 얼마만큼의 시간을 사용할지를 근사적으로 알려준다.
  1. O(1) : 상수 시간 알고리즘으로 수행시간은 입력의 크기에 영향을 받지 않는다.

      cin>>n;
      int a = n;
      int b = 2;
      cout<<a+b<<endl;

     위와 같은 코드는 입력이 어떤 값이 들어와도 시간 복잡도에 영향이 없다.
  2. O(n) : 선형 시간 알고리즘으로 입력을 쭉 살펴보는 과정을 상수 번 수행한다.

      for(int i=0; i<n; i++) {
      //비지니스 로직
      }

     위와 같은 코드는 입력 n만큼 선회하며 확인하게 된다.
  3. O(n^2) : 제곱 시간 알고리즘으로 보통 2중으로 중첩된 반목문을 사용한다.
     

     for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
        //비지니스 로직
        }
     }

  4. O(log n) : 로그 시간 알고리즘으로 대체로 단계마다 입력의 크기를 절반씩 줄여나가는 것으로 입력의 크기가 증가해도 수행 시간에 크게 영향이 없다.
  5. O(2^n) : 이 시간 복잡도는 입력 원소로 만들 수 있는 모든 부분집합을 한 번씩 살펴보고는 알고리즘의 시간 복잡도를 기술할 때 자주 사용된다.

      {1,2,3}의 모든 부분집합 => {},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}

  6. O(n!) : 이 시간 복잡도는 입력 원소로 만들 수 있는 모든 순열을 한 번씩 살펴보는 알고리즘의 시간 복잡도를 기술할 때 자줏 사용된다.

      {1,2,3}의 모든 수열 => {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1}

• 이와 같이 알고리즘의 시간 복잡도를 알고 있으면 역으로 입력에 대한 적당한 알고리즘의 시간복잡도를 유추해 볼 수 있다.

문제

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

주안점

배열을 사용하지 않는다. 배열 사용의 단점 (공간 복잡도의 증가)

구조

재귀적 용법으로 문제에 나온 조건을 이용

코드

#include<bits/stdc++.h>
using namespace std;

int t,k,n;

int go(int floor, int door) {
    if(door == 1) return 1;
    if(floor == 0) return door;

    return go(floor-1, door)+go(floor, door-1);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>t;
    for(int i=0; i<t; i++){
        cin>>k>>n;
        cout<<go(k,n)<<"\n";
    }

}

문제

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

주안점

구조

단어를 BFS로 모두 지나며 확인해 본다.

코드

#include<bits/stdc++.h>
using namespace std;

int cnt, x;
int goal = -1;
queue<int> q;
bool flag = false;
int visited[54];

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    for(int i=0; i<words.size(); i++){
        if(words[i] == target) goal = i;
        cnt = 0;
        for(int j=0; j<begin.size(); j++){
            if(begin[j]!=words[i][j]) cnt++;
            if(cnt>1) break;
        }
        if(cnt==1) {
            if(words[i]==target) answer = 1;
            q.push(i);
            visited[i] = 1;
        }
    }
    if(answer) return answer;
    if(goal==-1) {
        answer = 0;
        return answer;
    }
    while(q.size()){
        x = q.front(); q.pop();
        for(int i=0; i<words.size(); i++){
            if(i==x) continue;
            if(visited[i]) continue;
            cnt = 0;
            for(int j=0; j<begin.size(); j++){
                if(words[x][j]!=words[i][j]) cnt++;
                if(cnt>1) break;
            }
            if(cnt==1) {
                visited[i] = visited[x]+1;
                if(i==goal) flag = true;
                q.push(i);
            }
        }
        if(flag) break;
    }
    answer = visited[goal];
    return answer;
}

문제

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

주안점

최대 이익 찾기 => 부르트 포스, 그리디, 동적 프로그래밍

부르트 포스로 찾을 수도 있으나 효율을 위해서 동적 프로그래밍이 적당하다.

구조

dp함수 : parameter로 넘어온 index에서 얻을 수 있는 최대 금액이 리턴된다.

코드

#include<bits/stdc++.h>
using namespace std;

int n,t,p;
vector<int> day,pay;
int a[19][19];

int dp(int idx){
	if(idx >= n) return 0;
	int &ret = *a[idx];
	if(ret != -1) return ret;

    ret = 0;
    if(idx+day[idx] > n) {
        ret = max(ret, dp(idx+1));
    } else {
        ret = max(dp(idx+1), dp(idx+day[idx])+pay[idx]);
    }

	return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

	cin>>n;
	for(int i=0; i<n; i++){
		cin>>t>>p;
		day.push_back(t);
		pay.push_back(p);
	}
	memset(a, -1, sizeof(a));
	cout<<dp(0)<<"\n";
}

알고리즘 1번문제에 단골로 문자열을 다루는 문제가 나온다.

문자열 다룰때 필요한 2가지 팁을 적어본다.

1. find 함수

c++에서 find 함수는 string.find(찾고싶은 문자열)으로 사용할 수 있다.

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s = "c++ 문자열 다루기";

    cout<<s.find("문자열")<<endl;
}

/*
	4
*/

해당 문자열이 존재하면 index값을 리턴한다.

그렇다면 이 코드를 보자

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s = "c++ 문자열 다루기";

    if(s.find("c+++")) {
        cout<<"yes"<<endl;
    } else {
        cout<<"no"<<endl;
    }

}

무심코 봣을 땐 해당 코드에서 if 분기문에 걸려 "no"를 리턴할것 같지만 실제로 find 함수를 통해서 찾으려는 문자열이 없는 경우 npos라는 더미 값을 리턴하게 된다. 따라서 c++에서 문자열을 다루게 된다면 아래 코드처럼 작성해야한다.

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s = "c++ 문자열 다루기";

    if(s.find("c+++") != string::npos) {
        cout<<"yes"<<endl;
    } else {
        cout<<"no"<<endl;
    }

}

/*
	no
*/

의식적으로 npos를 활용하는 습관을 가지자.

2. split 함수

c++에는 split 함수가 존재하지 않는다. 따라서 직접 구현하거나 다른 방법을 사용해야한다.

하지만 다른 방법을 사용하기엔 쉽지 않다. 작은 문자열이면 subString으로 해결할 수 있지만 split 함수 정도는 외워두는 것이 좋다.

#include <bits/stdc++.h>

using namespace std;

vector<string> split(string input, string delimiter) {
    vector<string> ret;
    long long pos = 0; //delimiter가 input에서 위치한 index
    string tmp = ""; //vector 값으로 split된 문자열
    while((pos = input.find(delimiter)) != string::npos) { //구분자가 사용된 index가 존재한다면
        tmp = input.substr(0,pos); //substr로 해당 문자열 파싱
        ret.push_back(tmp); //vector에 저장
        input.erase(0, pos + delimiter.length()); //저장된 문자열 삭제
    }
    ret.push_back(input); //구분자로 나누어져있지 않은 마지막 문자열 저장
    return ret;
}

int main() {
    string s = "c++ handle string";

    vector<string> answer = split(s, " ");

    for(string ss : answer) cout<<ss<<"\n";

}

/*
	c++
    handle
    string
*/

이와 같이 사용하면 쉽게 split 함수를 사용할 수 있다.

2021년 10월 9일 대장동 임장을 다녀왔다.

대장동에는 큰 개발 호재가 없다. 다만 요즘 언론에 많이 노출되다보니 알아보면 좋겠다 싶어 방문했다.

대부분이 대장동 이름만 들어봤지 위치는 자세히 모를 것이다. 성남시에 소속되어있고 판교에서 기흥쪽으로 내려가다보면 고기리 근처에 위치해 있다.

그렇다고 한다.... 사실 위치만 봤을땐 개발만 된다면 판교 집값에 치여 외곽으로 나가는 직장인들에게 더할나위 없이 좋은 위치인것 같다.

대장동의 임장 포인트는 1가지 밖에 없었다.

1. 대장동의 위치

2. 개발 진행 상황

1. 대장동은 판교 테크노벨리를 지나 '그' 서판교 터널을 지나면 바로 있다.

또한 대장동은 위 지도를 보면 나오듯이 산으로 둘러쌓여있는 곳이다. 이런곳을 어떻게 개발 할 것인가....하면 역시 다 깎아내는 방법 뿐이다.

이처럼 대장동 변두리에는 산을 깎아낸 흔적이 보인다.

그리고 곳곳에 이렇게 고압 송전탑이 보인다. 개발중에 문제가 많아 일부 철수한다고 한다.

멀리서 보면 이와 같은데 저 멀리 수지와 비교해서 대장동은 송전탑이 많아 주거단지처럼 보이진 않는다. 

2. 대장동은 원래 LH에서 주관해서 개발하던 곳이다.

대장동 초입에는 꽤 다 지어진 아파트가 있다. 하지만 펜스가 저렇게 쳐져있는것으로 보아 아직 개발중인 부지가 많은 것으로 보인다.

대부분의 아파트는 푸르지오였다.

이 처럼 개발 대기중인 공터도 많았고

개발중에 있는 건물도 많았다.

=> 분명 이재명 도지사님 말씀대로 판교와 가까이 있어 노른자 땅임에는 분명하다. 다만 건설 과정이 복잡할 뿐.....

2021년 9월 21일 송산 그린시티 임장을 다녀왔다. 아직 개발이 시작되지 않아 부지 외에 크게 볼 수 있는 것들이 많지는 않았다. 하지만 그린시티를 가는 도로는 완성이 되어있었는데 차선도 넓고 잘 되어있었다.

송산 그린시티 임장 포인트는 이렇게 볼 수 있다.

1. 동측지구

2. 남측지구

3. 서측지구

1. 동측지구는 3개의 지구중에 가장 먼저 개발이 된 곳으로 신세계에서 만드는 국제 테마 파크가 만들어질 예정이다. 이는 1400평 규모의 대규모 테마파크로 인천과 가까운 지리적 장점을 활용하여 관광 산업으로 활용할 수 있는 테마파크이다.

그리고 이러한 테마파크를 업고 자란 아파트가 있다.

동측지구엔 유일한 아파트 부지로 더 이상 동측 지구엔 아파트로 예정되어 있는 부지가 없다.

따라서 아래 새솔동 아파트가 분양가 3억에서 현재 6~7억을 호가하며 큰 호재를 얻었다.

2. 그 다음으로 개발 될 남측 지구이다. 남측 지구는 4차산업을 이끌 자율주행 + 산업단지가 형성 될 예정이다.

자동차 테마파크와 자율주행 시험장, 산업단지가 형성되고 복합 환승센터를 품은 송산역이 위치 할 예정이다.

3. 마지막으로 개발 되는곳은 서측 지구이다. 서측 지구는 개발 예정이 매우 늦다. 서측 지구에는 유럽형 도시가 생길 예정이다.

이 처럼 화성은 매우 발전할 가능성이 높은 도시이다. 또한 화성은 전세계 부자도시 4위에 랭크되어있는 도시로 추후 여러 고속도로와 지하철 노선이 추가 될 예정이다.

=> 아직 개발 예정 구역이라 현재는 황무지이나 이런 호재를 알아두어야 근처에 투자할 수 있을것 같다.

2021년 9월 21일 평택에 고덕신도시와 삼성 반도체 공장을 확인하면서 아래 주거단지를 확인하는 임장을 다녀왔다.

역시 지제역을 중심으로 동남쪽 주거단지를 확인했다.

이번 임장 포인트는 이렇게 볼 수 있다. 지제역을 중심으로 멀리 떨어지는 순으로 정리했다.

1. 동삭동

2. 죽백동

3. 비전동

4. 용이동

++세교동

1. 동삭동은 이미 유명한 주거단지로 지제로부터 가까웠다. 동삭동에 현대아파트가 있다. 주위를 보자 자이로 둘러 쌓였다. 92년에 지어진 건물로 자이가 들어서니 같이 오르는 모습 아주 좋다.

2,3. 임장을 돌면서 탐나는 아파트가 있었다. 주로 형광펜으로 칠해놓은 도로 쪽에 있었다. 아파트 단지 주변으로 나무들이 잘 조성되어있었고 단지 주변으로 도로와의 간격이 넓었다. 임장이 끝나고 확인 해보았더니 역시나 주변 아파트보다 몇억씩 더 비싸게 집값이 형성 되어있었다.

오늘 임장에서 LH가 차지한(?) 위치를 확인 해 본 것인데 역시 정부 소유라 그런지 위치선정이 뛰어나다. 특히 저 고덕LH17 탐난다.

4. 용이동은 지제역과 가장 멀지만 안성 바로 옆으로 안성 IC와 가깝고 스타필드가 있었다.

=> 모든 삼성 및 협력업체 직원들이 고덕 신도시에 살 수 없다. 이곳으로 몰릴 터이니 투자 가치가있다. 다만 현재는 매매가가 너무 급증하여 전세가가 따라가질 못한다. 때문에 갭이 2억~3억이 되는 집이 대부분이었다. 갭이 줄어들거나 살짝 외곽에 있는 구축을 노리는 것도 나쁘지 않아보인다.