2020-11-02FrameWork / 스프링 / 1장 - IOC 컨테이너

Spring Ch 1. IoC 컨테이너(2) - Component와 Autowired

Component

Component-scan에 의해 Bean으로 등록되는 개발자가 직접 작성한 클래스.
@Controller, @Service, @Repository는 @Component를 확장한 annotation이며 이러한 Annotation이 등록된 컴포넌트들은 컨테이너에 의해 의존성이 주입된다.
ComponentScan에는 아래와 같이 다양한 설정들이 있다.

basePackages

기본적으로 컴포넌트 스캔은 basePackage로 등록된 클래스를 기준으로 하여 작동한다.
컴포넌트 스캔은 등록된 클래스가 존재하는 폴더부터 하위폴더로 진행되므로 상위 폴더에 대해서는 스캔 되지 않는다.
basePackage의 기본값은 component-scan을 사용하는 configuration 설정 파일의 폴더.

2020-10-29FrameWork / 스프링 / 1장 - IOC 컨테이너

Spring Ch 1. IoC 컨테이너(1) - 빈과 IoC

Dependency

하나의 객체가 다른 객체를 변수로 가지고 있거나 파라미터로 전달, 혹은 메소드를 호출하는 것을 ‘의존한다’라고 표현한다.
객체 A가 객체 B를 의존하고자 할 때 객체를 직접 선언하여 사용하나, 만약 객체 A가 객체 B 대신 객체 C를 사용하는 객체로 사용하기 위해서는 C에 의존하고 객체 A와 비슷한 객체 D를 선언해야 한다.

Dependency Inversion Principle

의존하는 객체는 재사용할 수 없다. 객체를 재사용하기 위해서는 의존성을 제거하여야 한다.
의존 대상이 되는 객체를 추상화하여 의존성을 제거할 수 있다. 이를 의존성 역전 원리(Dependency Inversion Principle)라고 한다.

2020-08-14코딩테스트

백준 1037번 문제 - 약수

문제 링크 : https://www.acmicpc.net/problem/1037

N의 약수들은 제곱으로 N이 되는 약수를 제외하고 대칭이 되는 숫자들끼리 곱하여 N을 구할 수 있다.

예를 들어, 16의 경우 약수들은 {1, 2, 4, 8, 16}으로 16을 구하기 위해 1과 16, 2와 8, 4(제곱)을 선택하여야 한다.

N의 약수들이 주어졌을 때, N은 최소값과 최대값을 저장하여 곱함으로서 구할 수 있고 이는 다른 최대, 최소 값을 제외하고 저장할 필요가 없다는 것을 의미한다.

그러나 주어지는 약수들은 1,000,000이하의 정수로 입력되는 점을 고려하였을 때, 두 정수의 곱으로 표현되는 정수 N은 16비트로 표현되는 int형 정수가 아닌 32비트 정수로 표현하여야 한다.

32비트 정수를 표현하기 위해 최소 약수와 최대 약수의 곱은 long long int형 정수로 형변환을 하여 출력되도록 하였다.

#include<stdio.h>
using namespace std;
int aliqot, N, alimin=1000000,alimax=1;

int main(){
    scanf("%d",&N);
    while(N--){
        scanf("%d",&aliqot);
        alimin = (aliqot<alimin)?aliqot:alimin;
        alimax = (aliqot>alimax)?aliqot:alimax;
    }
    printf("%lld",(long long int)alimin*alimax);
    return 0;
}

2020-08-11major / 알고리즘 / 정렬 알고리즘

알고리즘 (4): 트리

트리

정보를 갖는 노드들의 집합
수직 계층의 자료구조로, 하나의 루트 노드로부터 연결된 여러 노드들은 부모 자식의 관계를 가지며 자기 자신이 부모 노드가 되어 다른 노드를 자식으로서 연결할 수 있다.
루트(Root): 부모를 갖지 않는 최상단 노드
자식(Child): 부모 노드에 연결된 노드, 해당 노드에 접근하기 위해서는 부모 노드를 통해 접근해야 한다.
형제(Siblings): 같은 부모에 연결된 노드들은 형제 관계를 갖지만 트리 특성상 형제 노드만으로는 접근이 불가능하고 부모노드를 통해서만 접근 가능하다.
내부 노드(Internal node): 최소 하나의 자식을 갖는 노드
외부 노드(External node, Leaf node): 자식을 갖지 않는 노드
조상 노드(ancestor node): 노드의 부모 노드가 루트가 아니라면 해당 부모 노드도 부모 노드를 갖는다. 부모 노드 또한 조상 노드로서 표현됨.
깊이(Depth): 루트 노드로부터 자신까지 가는 경로의 길이.
레벨(Level): 루트 노드에서 자신까지 가는 경로+1.
높이(Height): 트리가 갖는 노드들의 최대 깊이를 의미.
차수(Degree): 자식노드가 최대로 가질 수 있는 형제 노드의 수

이진트리(Binary Tree)

자식노드가 최대 두개인 노드들로 구성된 트리
내부 노드의 자식들을 좌측 자식, 우측 자식으로 나누어 표현한다.
정 이진 트리(full binary tree): 모든 내부 노드들이 자식을 두 개 갖는 이진 트리
완전 이진 트리(complete binary tree): 마지막 레벨을 제외하고 모든 레벨에 노드들이 완전히 채워져 있고 외부 노드의 경우 왼쪽부터 채워진 트리
균형 이진 트리(balanced binary tree): 모든 외부노드들이 같은 깊이를 갖거나, 깊이의 차이가 최대 1인 트리

트리 순회

전위 순회(Preorder Traversal)

자식 노드에 접근하기 전에 노드를 방문하는 순회 방식
자식 노드의 접근은 자식간의 관계에 의해 형성된 순서를 지키며 먼저 방문함
1
2
3
4
5
void preOrder(node* v){
visit(v);
preOrder(v->left);
preOrder(v->right);
}

후위 순회(Postorder Traversal)

자식 노드에 먼저 접근한 후 자신의 노드를 방문하는 순회방식

루트 노드는 최상위 노드이므로 후위 순회에서 가장 마지막에 방문되어진다.

void postOrder(node* v){
    postOrder(v->left);
    postOrder(v->right);
    visit(v);
}

중위 순회

좌측 자식 -> 현재 노드 -> 우측 자식의 순으로 노드를 방문하는 순회방식
자식 사이에 현재 노드의 방문이 이루어지므로 이진트리가 아닌 경우 임의로 순서를 정하여 순회할 수 있다.
1
2
3
4
5
void inOrder(node* v){
inOrder(v->left);
visit(v);
inOrder(v->right);
}

오일러 투어 순회(Euler Tour Traversal)

현재 노드 -> 좌측 자식 -> 현재 노드 -> 우측 자식 -> 현재 노드의 순으로 노드를 방문하는 순회방식

현재 노드를 먼저 방문하는 전위 순회, 좌측 자식 방문 후 자기 노드를 방문하고 우측 노드를 방문하는 중위 순회, 자식 노드를 방문한 후 자기 노드를 방문하는 후위 순회가 모두 합쳐진 순회방식으로 볼 수 있다.

void eulerTour(node* v){
    visit(v);
    if(v->left != nullptr){
        eulerTour(v->left);
        visit(v);
    }
    if(v->right != nullptr){    
        eulerTour(v->right);
        visit(v);
    }
}

2020-08-05코딩테스트

백준 1032번 문제 - 명령 프롬프트

문제 링크 : https://www.acmicpc.net/problem/1032

명령 프롬프트 문제는 주어진 문자열들을 비교하여 불일치가 발생한 문자에 대해 ?로 표현하여 출력하는 문제이다.

하나의 문자열이라도 불일치가 발생한 경우 불일치가 발생한 위치의 문자는 ?로 출력되므로
비교할 기준이 되는 문자열 하나만을 저장하여 다른 문자열들과 비교하고 불일치가 발생한 위치의 문자를 ?로 변경한다면 공간적인 낭비를 줄일 수 있다.

또한 문자열의 길이 최대 값은 50이지만 그보다 작은 길이의 문자열 입력이 발생할 수 있다.

scanf 함수를 통해서 입력 받은 문자열의 마지막 문자는 NULL(‘\0’)이 입력되므로 (i<51 && arr[i] != NULL) 혹은 (i<51 && arr[i])의 조건문을 수행한다면 &&연산에 의하여 i<51을 만족하지 않는다면 뒤의 연산을 수행하지 않기 때문에 문자열 길이 내의 검사를 수행할 수 있다.

#include<iostream>
using namespace std;
#define MAXSIZE 51
int N;
char arr[MAXSIZE], temp[MAXSIZE];

int main(){
    scanf("%d",&N);
    scanf("%s",&arr);
    for(int i=1;i<N;i++){   
        scanf("%s",temp);
        int j=0;
        while(j<MAXSIZE && temp[j]){
            if(arr[j]!=temp[j]) arr[j] = '?';
            j++;
        }
    }
    printf("%s\n",arr);
}

2020-07-26코딩테스트

백준 1021번 문제 - 회전하는 큐

문제 링크 : https://www.acmicpc.net/problem/1021

회전하는 큐 문제는 다음과 같은 3가지 연산을 수행한다.

1. 첫 번째 원소를 뽑아낸다.
2. 원소들을 좌측으로 한 칸씩 이동시킨다.
3. 원소들을 우측으로 한 칸씩 이동시킨다.

2번 연산 이후 3번 연산을 사용하게 된다면 원소는 제자리로 돌아가게 될 것이다.

따라서 원소를 뽑아내는데 필요한 2, 3번 연산의 최소 값은 원하는 원소가 첫 번째 원소가 될 때 까지 2번 연산을 수행하거나 3번 연산을 수행하는 경우 중 수행한 연산의 최소 값이 된다.

(원소의 위치)와 (원소의 위치 - 큐의 크기)의 계산으로 이를 확인하였으며 구현한 내용은 아래와 같다.

#include<iostream>
#include<vector>
using namespace std;
int N,M,result=0;
vector<int> vec;

void myPop(int k){
    int current = 0;
    while(vec[current]!=k)        current++;    //뽑아내고자 하는 원소의 위치 확인
    if(current<vec.size()-current){//2번 연산
        while(vec.front()!=k){
            vec.push_back(vec.front());
            vec.erase(vec.begin());
            result++;
        }
    }else{//3번 연산
        while(vec.front()!=k){
            vec.insert(vec.begin(),vec.back());
            vec.pop_back();
            result++;
        }
    }
    vec.erase(vec.begin());//1번 연산
}

int main(){
    scanf("%d %d",&N,&M);
    for(int i=1;i<=N;i++){
        vec.push_back(i);
    }
    for(int i=0;i<M;i++){
        int k;
        scanf("%d",&k);
        myPop(k);
    }
    printf("%d\n",result);
    return 0;
}

2020-07-12코딩테스트

백준 1012번 문제 - 유기농 배추

문제 링크 : https://www.acmicpc.net/problem/1012

유기농 배추 문제는 DFS 또는 BFS를 통해 해결할 수 있다.

DFS란 깊이 우선 탐색(Depth-First Search), BFS란 너비 우선 탐색(Breadth-First Search)으로서 모든 정점을 한 번씩만 방문하여 모든 노드를 탐색하는 그래프 탐색 알고리즘이다.

명칭에서도 알 수 있듯이, DFS는 깊이 우선 탐색으로 더 이상 이동할 수 있는 노드가 없을 때까지 연결된 노드를 지속적으로 방문한 후 이전 노드로 돌아가 연결된 다른 노드를 방문하는 backtracking 방식을 사용하며 BFS는 너비 우선 탐색으로 노드에 가까운 노드들을 모두 방문한 후에 해당 노드들에 연결된 노드를 방문하는 방식으로 구현되어있다.

DFS의 경우 깊이를 우선시 하기 위해 LIFO인 stack을 사용하거나 재귀함수를 사용하여 탐색할 수 있으며, BFS의 경우 너비를 우선시 하기 위해 FIFO인 queue를 사용한다.

유기농 배추 문제는 배추가 심어져 있는 땅의 위치 X와 Y를 입력으로 받는다.
입력받은 배추들을 확인할 예정에 두고 인접한 위치에 배추가 존재하지 않을 때까지 방문하지 않은 인접 배추들을 확인하도록 하여 그룹을 체크할 수 있다.

#include<iostream>
#include<vector>
using namespace std;
#define MAXSIZE 51
int T,M,N,K;
int arr[MAXSIZE][MAXSIZE]={0};
bool bvisited[MAXSIZE][MAXSIZE]={false};
vector<pair<int,int>> vec;
int result=0;

void grouping(int x, int y){
    bvisited[x][y]=true;
    if(x>0&&arr[x-1][y]&&!bvisited[x-1][y]){
        grouping(x-1,y);
    }
    if(x+1<M&&arr[x+1][y]&&!bvisited[x+1][y]){
        grouping(x+1,y);
    }
    if(y>0&&arr[x][y-1]&&!bvisited[x][y-1]){
        grouping(x,y-1);
    }  
    if(y+1<N&&arr[x][y+1]&&!bvisited[x][y+1]){
        grouping(x,y+1);
    }
}

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d %d %d",&M,&N,&K);
        vec.clear();
        result=0;
        for(int i=0;i<N;i++){//y
            for(int j=0;j<M;j++){//x
                bvisited[i][j] = false;
                arr[i][j]=0;
            }
        }
        while(K--){
            int i,j;
            scanf("%d %d",&i,&j);
            arr[i][j] =1;
            vec.push_back(make_pair(i,j));
        }
        for(int i=0;i<vec.size();i++){
            int x = vec[i].first;
            int y = vec[i].second;
            if(!bvisited[x][y]){
                grouping(x,y);
                result++;
            }
        }
        printf("%d\n",result);

    }
    return 0;
}

2020-07-11코딩테스트

백준 1018번 문제 - 체스판 다시 칠하기

문제 링크: https://www.acmicpc.net/problem/1018

체스판 다시 칠하기 문제는 8x8 크기의 체스판으로 만들 때 체스판의 경우의 수가 좌상단 첫번째 칸이 흰색인 경우와 검은색인 경우 두가지 밖에 없다는 점을 읽었다면 쉽게 풀 수 있는 문제이다.

NxM의 보드판이 주어졌을 때 8x8의 체스판을 구하기 위해 정할 수 있는 시작점은 (0,0)부터 (N-8,M-8)까지 가능하다.

가능한 각 시작점을 기준으로 8x8의 가능한 체스판 2개에 대해 불일치한 수를 구해 최소값을 구함으로서 해답을 구할 수 있다.

#include<iostream>
using namespace std;
#define MAXSIZE 51
#define CHESSSIZE 8
int N,M,result=64;//8x8이므로 아무리 색을 다시칠해도 64의 결과가 나올 수 없음
char arr[MAXSIZE][MAXSIZE];

int check(int n,int m){ //8x8에서 인접한 위치와 충돌이 일어나는 수
    int result1=0, result2=0;
    for(int i=0;i<CHESSSIZE;i++){
        for(int j=0;j<CHESSSIZE;j++){
            if(i%2==j%2){//0,0 || 1,1
                if(arr[n+i][m+j]!='W') result1++;
                if(arr[n+i][m+j]!='B') result2++;
            }else{//0,1 || 1,0
                if(arr[n+i][m+j]!='B') result1++;
                if(arr[n+i][m+j]!='W') result2++;
            }
        }
    }
    return (result1<result2)?result1:result2;
}

int main(){
    scanf("%d %d",&N,&M);
    for(int i=0;i<N;i++) scanf("%s",&arr[i]);
    
    //풀이 1: 가장 간단한 방법, N-8, M-8의 경우의 수를 전부 조사하여 최소값 구하기
    for(int i=0;i<=N-8;i++){//시작점 세팅
        for(int j=0;j<=M-8;j++){
            int temp = check(i,j);
            result = (result>temp)?temp:result;
        }
    }
    printf("%d\n",result);
}

2020-07-09major / 알고리즘 / 정렬 알고리즘

알고리즘 (3): 쉘 정렬, 힙 정렬

쉘 정렬 (Shell Sort)

멀리 떨어진 원소끼리 교환하여 정렬 속도를 향상시키는 정렬 알고리즘
삽입 정렬을 변형하여 병렬 처리로서 정렬을 수행한다.
교환할 원소들의 Gap을 서서히 줄여가면서 최종적으로 i번째 인덱스와 i+1번째 인덱스의 교환들로 정렬이 마무리된다.

2020-07-07코딩테스트

백준 1009번 문제 - 분산처리

문제 링크 : https://www.acmicpc.net/problem/1009

분산처리 문제는 어려워보이는 제목과는 달리 컴퓨터가 10대라는 점만으로 해결방법을 알 수 있는 쉬운 문제이다.

1번째 컴퓨터는 1번째 데이터, 11번째 데이터, 21번째 데이터와 같이 일의 자리가 1인 번호의 데이터를 처리하며 $a^b$개의 데이터 중 마지막 데이터는 일의 자리에 따라 처리할 컴퓨터의 번호가 결정된다.

그러나 $1\leq a < 100 , 1\leq b < 1,000,000$의 조건으로 보아 단순히 $a^b$를 계산하여 일의 자리를 찾는 것은 무리가 있어보인다.

이때 생각해야 할 것이 “일의 자리의 규칙성”이다.

예를 들어, $3^7$의 데이터에 대하여 생각해보자. $3^1=3$, $3^2=9$, $3^3=27$, $3^4=81$, $3^5=243$, $3^6=729$, $3^7=2187$로 일의자리가 3 -> 9 -> 7 -> 1의 반복이 이루어짐을 확인할 수 있다.

10 이하의 자연수에 대하여 지수함수의 일의 자리는 최대 4가지 경우의 수가 존재하며, 11 이상의 자연수는 일의 자리에 대해서만 계산하므로 10 이하의 자연수와 동일한 결과를 얻는다.

따라서 $a^b$의 일의 자리는 ${(a \mod 10)}^{b} \mod 10$이며 일의 자리의 반복 중 $b \mod 4$번째 결과와 동일한 결과를 갖는다.

#include<iostream>
using namespace std;
int arr[4];

int main(){
    int T,a,b;
    scanf("%d",&T);
    while(T--){
        scanf("%d %d",&a,&b);
        arr[0]=a%10;
        arr[1]=(arr[0]*a)%10;
        arr[2]=(arr[1]*a)%10;
        arr[3]=(arr[2]*a)%10;
        printf("%d\n",(arr[(b-1)%4]==0)?10:arr[(b-1)%4]);
    }
    return 0;
}

Spring Ch 1. IoC 컨테이너(2) - Component와 Autowired

Component

basePackages

Spring Ch 1. IoC 컨테이너(1) - 빈과 IoC

Dependency

Dependency Inversion Principle

백준 1037번 문제 - 약수

문제 링크 : https://www.acmicpc.net/problem/1037

알고리즘 (4): 트리

트리

이진트리(Binary Tree)

트리 순회

전위 순회(Preorder Traversal)

후위 순회(Postorder Traversal)

중위 순회

오일러 투어 순회(Euler Tour Traversal)

백준 1032번 문제 - 명령 프롬프트

문제 링크 : https://www.acmicpc.net/problem/1032

백준 1021번 문제 - 회전하는 큐

문제 링크 : https://www.acmicpc.net/problem/1021

백준 1012번 문제 - 유기농 배추

문제 링크 : https://www.acmicpc.net/problem/1012

백준 1018번 문제 - 체스판 다시 칠하기

문제 링크: https://www.acmicpc.net/problem/1018

알고리즘 (3): 쉘 정렬, 힙 정렬

쉘 정렬 (Shell Sort)

백준 1009번 문제 - 분산처리

문제 링크 : https://www.acmicpc.net/problem/1009

카테고리

최근 글

아카이브

태그

Subscribe to Updates