가비지 컬렉션

쉽게 이야기해서 Java가 개발자 대신 사용하지 않는 객체를 자동으로 찾아 메모리에서 제거해줌으로써 메모리를 관리해주는 것이다.

GC 대상이 되는 객체

1. 모든 객체 참조가 null 인 경우
2. 객체가 블럭 안에서 생성되고 블럭이 종료된 경우
3. 부모 객체가 null이 된 경우, 자식 객체는 자동적으로 GC 대상이 된다.
4. 객체가 Weak 참조만 가지고 있을 경우
5. 객체가 Soft 참조이지만 메모리 부족이 발생한 경우

가비지 컬렉션 과정 - Generational Garbage Collection

Generational Garbage Collection에서는 힙을 Young, Old or Tenured, Permanent Generation으로 나눈다.

Young 영역

• 새롭게 생성한 객체의 대부분이 여기에 위치한다.
• 가득차게 되면 minor garbage collection이 일어난다.
• 대부분 객체가 금방 사라지기 때문에 많은 객체가 이 곳에서 사라진다.

Old 영역

• 접근 불가능 상태가 되지 않고 Young 영역에서 살아남은 객체들이 복사된다.
• Young 영역 보다 크기가 크게 할당하고 큰 만큼 GC는 적게 발생한다.
• 이 영역에서 객체가 사라질때 Major GC라고 한다.

Permanet 영역

• Method Area라고도 한다.
• JVM이 클래스들과 메소드들을 설명하기 위해 필요한 메타데이터들을 포함하고 있다.

1. 새로운 객체는 Eden space에 할당 된다.

2. Eden space가 채워지면 minor garbage collection이 시작 된다.

3. 참조되는 오브젝트들은 첫 번째 S0로 이동되어지고, 비 참조 객체는 Eden space가 clear 될 때 반환된다.

4. 다음 minor garbage collection이 시작될때 Eden space에서 비 참조 객체는 삭제되고 참조객체는 참조 객체는 두번째 S1로 이동한다.
   또한 S0의 minor minor garbage collection를 통해 S1공간으로 이동하게 되며 age가 증가 된다.
   모든 객체들이 S1으로 이동하게 되면 S0와 Eden space는 Clear 된다.
   

5. 다음 minor garbage collection에도 S0로 같은 작업이 반복된다. 그리고 Eden Space와 S1 공간은 Clear 된다.

6. minor garbage collection 후 일정한 age를 넘게 되면 young generation에서 old로 승격 된다.

7. minor garbage collection가 계속 발생하면 객체는 게속 old로 승격된다.

8. 결국 major garbage collection가 일어나며 old가 Clear 되고 정리된다.

JOIN

조인이란?

두개이상의 테이블이나 데이터베잇스를 연결하여 데이터를 검색하는 방법 이다.

보통 보통 Primary key혹은 Foreign key로 두 테이블을 연결한다.

INNER JOIN

결합된 테이블에 조건의 내용이 공통으로 들어가 있는 값을 결과 집합으로 만들어준다.

1
2
3
4

SELECT 열 목록
FROM 첫번째 테이블 [AS 별칭] 
INNER JOIN 두번째 테이블 [AS별칭]
ON(join_condition)

OUTER JOIN

INNER JOIN 문을 포함하고 한쪽에만 내용이 있더라도 지정한 기준 테이블에 있는 모든 데이터를 가져오는 조인

1
2
3
4
5

SELECT 열목록
FROM 첫번째 테이블
<LEFT | RIGHT | FULL> OUTER JOIN 두번째 테이블
ON(join_condition)
[WHERE 검색조건]

LEFT OUTER JOIN

왼쪽 테이블이 기준이 되어서 그 테이블에 있는 데이터를 모두 가져온다. 기준으로 지정되지 않은 오른쪽 테이블에서 가져올 수 없는 열은 NULL로 표현된다.

RIGHT OUTER JOIN

오른쪽 테이블이 기준이 되어서 그 테이블에 있는 데이터를 모두 가져온다. 기준으로 지정되지 않은 왼쪽 테이블에서 가져올 수 없는 열은 NULL로 표현된다.

FULL OUTER JOIN

왼쪽과 오른쪽에 관계없이 조건이 일치하지 않아도 양쪽의 모든 내용을 포함해서 나타낸다.

CROSS JOIN

결과값이 한쪽 테이블의 모든행들과 다른쪽 테이블의 모든 행을 조인시킨다.
결과 집합은 두 테이블의 개수를 곱한 값만큼 생성되며, 조인되는 테이블에 공통되는 행이 없어도 되며 조건절인 ON 키워드가 사용되지 않는다.

1
2
3

SELECT 열목록
FROM 첫번째 테이블 
CROSS JOIN 두번째 테이블

SELF JOIN

하나의 테이블에 같은 데이터가 존재하는데 그 의미가 다르게 존재하는 경우. 즉, 같은 데이터이지만 다른 열에 있는 경우에는 두 테이블을 서로 SELF JOIN 문으로 확인가능

index

index란

RDBMS에서 검색 속도를 높이는 기술중 하나이다.

대게 B-Tree, B+ Tree 구조를 갖는다.

index는 해당 TABLE의 컬럼을 색인화 한다.

index는 논리적/물리적으로 테이블과 독립적임

TABLE 에는 데이터의 레코드가 순서 없이 저장된다. 이때 데이터를 찾을 경우 데이터 페이지의 청므 레코드부터 끝 레코드까지 다 읽어 검색 조건과 비교하게 된다.
이러한 방식을 full scan이라고 하는데 full scan이 아닌 색인화 되어 있는 index파일을 검색하여 검색속도를 빠르게 한다.

index의 장단점

• 키 값을 기초로 하여 테이블에서 검색과 정렬 속도가 향상된다.
• 테이블의 기본 키는 자동으로 인덱스 된다.
• 인덱스를 만들면 .mdb 파일 크기가 늘어난다.
• 데이터를 업데이트 하거나 레코드를 추가 또는 삭제할 때 성능이 떨어진다.

index 생성시 고려할 점

• WHERE 절에서 사용되는 컬럼을 인덱스로 만든다.
• like ‘%~~~’는 조심(처음 %가 붙으면 table scan이 된다.)
• 데이터의 중복도가 높은 열은 인덱스로 만들지 않는다.(값이 true/false 이거나 성별 같은 경우)
• join, order by 에 자주 사용되는 열에는 인덱스를 생성해주는 것이 좋다.
• 외래키가 사용되는 열에는 인덱스를 생성해주는 것이 좋다.
• insert, delete, update 등 데이터의 변경이 많은 컬럼에는 인덱스를 걸지 않는 편이 좋음

Call by Value/Call by Reference

java에서 인수로 매개 변수를 전달하는 방식이 크게 두가지다.

기본 데이터형은 모두 Call by Value로 처리되고 클래스의 객체는 Call by Reference로 처리 된다.

Call by Value

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Class CallByValue{
    public static void swap(int x, int y) {
        int temp = x;
        x = y;
        y = temp;
    }

    public static void main(String[] args) {
        int a = 10;
        int b = 20;
        System.out.println("swap() 호출 전 : a = " + a + ", b = " + b);
        swap(a, b);
        System.out.println("swap() 호출 후 : a = " + a + ", b = " + b);
    }
}

1
2

swap() 호출 전 : a = 10, b = 20
swap() 호출 후 : a = 10, b = 20

인수로 기본 데이터형을 사용하면 모두 Call by Value가 된다.

값을 복사하여 처리하기 때문에 메소드 밖의 변수에는 영향을 미치지 않게 되어 값이 변경되지 않는다.

Call by Reference

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Class CallByReference{
    int value;
    CallByReference(int value) {
        this.value = value;
    }
    
    public static void swap(CallByReference x, CallByReference y) {\
        int temp = x.value;
        x.value = y.value;
        y.value = temp;
    }
    
    public static void main(String[] args) {
        CallByReference a = new CallByReference(10);
        CallByReference b = new CallByReference(20);
        System.out.println("swap() 호출 전 : a = " + a.value + ", b = " + b.value);
        swap(a, b);
        System.out.println("swap() 호출 전 : a = " + a.value + ", b = " + b.value);
    }
}

1
2

swap() 호출 전 : a = 10, b = 20
swap() 호출 후 : a = 20, b = 10

CallByReference 클래스의 객체를 생성하여 값을 전달하게 되면 객체가 저장한 값이 주소값이기 때문에 swap메서드에서 변경시킨 결과가 main메서드로 돌려지게 된다.

이렇게 다른 메소드에서 현재의 메소드 내의 변수 값을 바꾸는 현상을 사이드 이펙트(side effect) 라고 한다.

사이드 이펙트 는 메소드 간의 값 전달을 쉽게 하기 때문에 편리하지만, 실수로 프로그래머가 모르는 사이에 값이 바뀌면 심각한 문제를 일으킬 수 있기 때문에 위험하다고 알려져 있다. 그래서 Java는 모든 기본 데이터형은 Call by Value로 값을 주고받아 ‘사이드 이펙트’가 일어나지 않도록 했고, Call by Reference가 필요한 경우는 명시적으로 클래스 객체를 주고받도록 정해둔 것이다.

http/https

http

• http는 HyperText Tranfer Protocol의 약자로 www상에서 정보를 주고 받는 프로토콜이다.
• http는 텍스트 교환으로 네트워크상에서 정보를 누군가가 마음대로 열람, 수정이 가능하다.

위에 보이는 warning페이지가 http로 보내는 정보를 무단으로 열람하여 redirect 하는 경우

https

• 뒤에 붙는 S는 Secure Socket의 약어로 보안성을 강화한 프로토콜
• 일반 텍스트를 이용하는 대신에, SSL이나 TLS 프로토콜을 통해 세션 데이터를 암호화 한다.
• https의 원리의 핵심은 공개키 암호화 방식 이다.

공개키 암호화 방식

공개키 방식에서는 두 개의 키를 갖는다. 누구에게나 공개가 가능한 공개키, 자신만이 갖고 있는 개인키

A키로 암호화 하면 B키로 복호화 가능

B키로 암호화 하면 A키로 복호화 가능

클라이언트는 공개키를 얻은 사용자가 암호화 하여 정보를 보내고, 서버는 개인키로 해독하여 요청에 대해 처리한다.

서버가 정보를 제공할 때 개인키로 암호화하면 공개키로 복호화 할 수 있다는 점을 통해 서버에서 개인키로 암호화 했다는 것을 보장할 수 있다.

이렇게 믿을 수 있는경우 브라우저에서는 주소 창의 색을 다르게 하여 안전하다고 알려 준다.

TCP/UDP

TCP

• 신뢰성있는 데이터 전송을 지원하는 연결지향형 프로토콜
• Sequence Number, Ack Number를 통한 신뢰성 보장
• 연결의 설정(3-way handshaking)과 해제(4-way handshaking)
• 흐름제어와 혼잡제어를 지원하며 데이터의 순서를 보장

UDP

• 일방적으로 데이터를 전달하는 비연결형 프로토콜
• 데이터 전송에 대한 보장을 하지 않음 (비신뢰성)
• 헤더에 Checksum 필드를 통한 최소한의 오류검출
• 속도가 빠름

3-way handshaking

연결을 하여 데이터를 전송하기 위해 TCP에서 3-way handshaking 과정을 거친다.

1. 접속 요청 프로세스가 연결요청 메시지 전송(SYN)
2. 접속 요청을 받은 프로세스가 수락 (SYN + ACK)
3. 마지막으로 접속 요청 프로세스가 수락 확인을 보내 연결을 맺음(ACK)

• SYN(Synchronization) : 연결요청, 세션을 설정하는데 사용되며 초기에 시퀀스 번호를 보냄
• ACK(Acknowledgement) : 보낸 시퀀스 번호에 TCP 계층에서의 길이 또는 양을 더한 것과 같은 값을 ACK에 포함하여 전송

4-way handshaking

4-way handshaking는 세션을 종료하기 위해 수해되는 절차이다.

1. 클라이언트가 연결을 종료하겠다는 FIN 플래그를 전송한다.
2. 서버는 일단 확인메시지를 보내고 자신의 통신이 끝날때까지 기다리는데 이 상태가 TIME_WAT 상태
3. 서버가 통신이 끝났으면 연결이 종료되었다고 클라이언트에게 FIN 플래그를 전송
4. 클라이언트는 확인했다는 메시지를 보냄

• FIN(Finish) : 세션을 종료시키는데 사용되며 더 이상 보낸 데이터가 없음을 표시

톱니바퀴

출처

문제 설명

총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다.

이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다.

톱니바퀴를 회전시키려면, 회전시킬 톱니바퀴와 회전시킬 방향을 결정해야 한다. 톱니바퀴가 회전할 때, 서로 맞닿은 극에 따라서 옆에 있는 톱니바퀴를 회전시킬 수도 있고, 회전시키지 않을 수도 있다. 톱니바퀴 A를 회전할 때, 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니의 극이 다르다면, B는 A가 회전한 방향과 반대방향으로 회전하게 된다. 예를 들어, 아래와 같은 경우를 살펴보자.

두 톱니바퀴의 맞닿은 부분은 초록색 점선으로 묶여있는 부분이다. 여기서, 3번 톱니바퀴를 반시계 방향으로 회전했다면, 4번 톱니바퀴는 시계 방향으로 회전하게 된다. 2번 톱니바퀴는 맞닿은 부분이 S극으로 서로 같기 때문에, 회전하지 않게 되고, 1번 톱니바퀴는 2번이 회전하지 않았기 때문에, 회전하지 않게 된다. 따라서, 아래 그림과 같은 모양을 만들게 된다.

위와 같은 상태에서 1번 톱니바퀴를 시계 방향으로 회전시키면, 2번 톱니바퀴가 반시계 방향으로 회전하게 되고, 2번이 회전하기 때문에, 3번도 동시에 시계 방향으로 회전하게 된다. 4번은 3번이 회전하지만, 맞닿은 극이 같기 때문에 회전하지 않는다. 따라서, 아래와 같은 상태가 된다.

톱니바퀴의 초기 상태와 톱니바퀴를 회전시킨 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다.

다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴의 번호, 두 번째 정수는 방향이다. 방향이 1인 경우는 시계 방향이고, -1인 경우는 반시계 방향이다.

출력

총 K번 회전시킨 이후에 네 톱니바퀴의 점수의 합을 출력한다. 점수란 다음과 같이 계산한다.

• 1번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 1점
• 2번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 2점
• 3번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 4점
• 4번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 8점

입출력 예제

소스 코드

자바

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

package ag;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main { // Gear 클래스로 만들고 싶었지만 백준 체점을 위해 이름을  Main 클래스로 변경
    int[] state = null;
    public int top =0; // 톱니바퀴 처음 맨위의 인덱스
    public int right = 2; // 톱니바퀴 3시방향 처음 인덱스
    public int left = 6; // 톱니바퀴 9시방향 처음 인덱스
    public int direct = 0; // 톱니바퀴가 어떤 방향으로 돌지
    Main rightGear=null; // 톱니바퀴의 오른쪽 톱니바퀴
    Main leftGear=null; // 톱니바퀴의 왼쪽 톱니바퀴
    public Main(int[] state){ //톱니바퀴 클래스의 생성자로 톱니바퀴의 톱니에 적힌 극을 배열로 저장
        this.state=state;
    }
    public void setRightGear(Main rightGear){
        this.rightGear =rightGear;
    } // 오른쪽 톱니바퀴를 등록

    public void setLeftGear(Main leftGear){
        this.leftGear =leftGear;
    } // 왼쪽 톱니바퀴를 등록
    public void startTurn(int num){ // 맨처음 톱니바퀴를 돌릴때 실행시킬 메서드
        this.direct=num;
        if(rightGear!=null && leftGear!=null){ // 좌우 톱니바퀴가 모두 존재할 경우 양쪽으로 톱니바퀴 돌리는 메서드 실행
            rightTurn(direct*-1); //좌우 톱니바퀴는 자신과 반대로 돌기때문에 -1을 곱해 반대 값을 넘겨줌
            leftTurn(direct*-1);
        }
        else if(rightGear==null){ // 왼쪽 톱니바퀴만 존재할 경우
            leftTurn(direct*-1);
        }
        else if(leftGear==null){ // 오른쪽 톱니바퀴만 존재할 경우
            rightTurn(direct*-1);
        }
        turn(); //좌우 모든 톱니바퀴를 돌리고 나서 자신의 톱니바퀴를 돌림
    }
    public void turn(){ // 톱니바퀴를 돌리는 메서드 배열을 직접 바꾸지않고 top, left, right 값만 바꿔줌
        if(direct ==-1){
            if(top==7)top =0;
            else top++;
            if(right==7)right=0;
            else right++;
            if(left==7)left=0;
            else left++;
        }
        else if(direct==1){
            if(top==0)top =7;
            else top--;
            if(right==0)right=7;
            else right--;
            if(left==0)left=7;
            else left--;
        }

    }
    public void rightTurn(int num){
        rightGear.direct=num; // 오른쪽 톱니바퀴의 방향에 자신과 반대의 값을 넣어줌
        if(rightGear.rightGear==null&&this.state[this.right]!=rightGear.state[rightGear.left]){ //오른쪽 톱니바퀴의 오른쪽 톱니바퀴가 존재하지않고 자신의 오른쪽 값과 오른쪽 톱니바퀴의 왼쪽 값이 다를경우
            rightGear.turn(); //오른쪽 톱니바퀴만 돌림
            return;
        }
        else if(this.state[this.right]!=rightGear.state[rightGear.left]){ //오른쪽 톱니바퀴의 오른쪽 톱니바퀴가 존재하고 자신의 오른쪽 값과 오른쪽 톱니바퀴의 왼쪽 값이 다를경우
            rightGear.rightTurn(rightGear.direct*-1); //오른쪽 톱니바퀴의 rightTurn 메서드를 실행시켜 오른쪽 톱니바퀴의 오른쪽 톱니바퀴도 값비교후 돌림
            rightGear.turn();
            return;
        }
        else{ // 자신의 오른쪽 값과 오른쪽 톱니바퀴의 왼쪽값이 다를 경우는 아무 작업 하지 않고 리턴
            return;
        }
    }
    public void leftTurn(int num){
        leftGear.direct=num;
        if(leftGear.leftGear==null && this.state[this.left]!=leftGear.state[leftGear.right]){
            leftGear.turn();
            return;
        }
        else if(this.state[this.left]!=leftGear.state[leftGear.right]){
            leftGear.leftTurn(leftGear.direct*-1);
            leftGear.turn();
            return;
        }
        else{
            return;
        }
    }

    public int score(){ //맨위의 값이 1일 경우는 점수있음
        if(this.state[this.top]==1)return 1;
        else return 0;
    }
    static BufferedReader br =null;
    public static void main(String[] args) throws IOException {
        int answerScore =0; //정답을 만들기 위한 변수
        List<int[]> arrayList = new ArrayList<>();

        br = new BufferedReader(new InputStreamReader(System.in));
        for(int i=0; i<4;i++){
            int[] gearStateArray =new int[8];
            String arrayString = br.readLine();
            for(int j=0;j<arrayString.length();j++){
                gearStateArray[j]=arrayString.charAt(j) -'0';
            }
            arrayList.add(gearStateArray);
        }

        Main gear1 = new Main(arrayList.get(0)); // 톱니바퀴 1 생성
        Main gear2 = new Main(arrayList.get(1)); // 톱니바퀴 2 생성
        Main gear3 = new Main(arrayList.get(2)); // 톱니바퀴 3 생성
        Main gear4 = new Main(arrayList.get(3)); // 톱니바퀴 4 생성

        gear1.setRightGear(gear2); //톱니바퀴의 양옆 톱니바퀴들 등록
        gear2.setLeftGear(gear1); //톱니바퀴의 양옆 톱니바퀴들 등록
        gear2.setRightGear(gear3); //톱니바퀴의 양옆 톱니바퀴들 등록
        gear3.setLeftGear(gear2); //톱니바퀴의 양옆 톱니바퀴들 등록
        gear3.setRightGear(gear4); //톱니바퀴의 양옆 톱니바퀴들 등록
        gear4.setLeftGear(gear3); //톱니바퀴의 양옆 톱니바퀴들 등록

        int count = Integer.parseInt(br.readLine());
        int gear,direct;
        for(int i=0; i<count;i++){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            gear =Integer.parseInt(st.nextToken());
            direct = Integer.parseInt(st.nextToken());
            if(gear==1 && direct==1) gear1.startTurn(1);
            else if(gear==1 && direct==-1) gear1.startTurn(-1);
            else if(gear==2 && direct==1) gear2.startTurn(1);
            else if(gear==2 && direct==-1) gear2.startTurn(-1);
            else if(gear==3 && direct==1) gear3.startTurn(1);
            else if(gear==3 && direct==-1) gear3.startTurn(-1);
            else if(gear==4 && direct==1) gear4.startTurn(1);
            else if(gear==4 && direct==-1) gear4.startTurn(-1);
        }

        answerScore+=gear1.score() + (gear2.score()*2) + (gear3.score()*4) + (gear4.score()*8); //각 톱니바퀴에 점수에 맞게 계산


        System.out.println(answerScore);

    }
}

소스코드 설명

저는 우선 링크드 리스트를 이용하여 톱니바퀴가 바뀔때마다 리스트를 변경하려고 하였습니다.

그러나 그냥 좌, 우, 위의 인덱스 정보만 저장 해놓고 변경하는식으로 사용하면 될 거같아 배열을 사용하기로 하였습니다.

톱니바퀴 객체를 만들고 그안에 인덱스와 배열 정보들을 기초변수로 각 기어의 양 옆 기어들을 저장시키기위한 톱니바퀴 클래스 참조변수 두개를 변수로 두고 set 메서드로 연결 시키도록 하였습니다.

turn 메서드는 톱니바퀴가 돌았을때의 효과를 주기 위한 인덱스 변경 메서드입니다.

startTurn 메서드는 맨 처음 입력값에서 톱니바퀴를 돌릴 경우 양 옆의 톱니바퀴가 존재할 경우 양 옆으로 회전을 전이시키기 위해 따로 작성한 메서드 입니다.

leftTurn, rightTurn 메서드는 각각 옆의 톱니바퀴가 돌아야 한다면 돌리고, 옆의 톱니바퀴에서도 메서드를 실행시켜 옆옆의 톱니바퀴들도 게속 확인하며 돌리는 메서드입니다.

영어 끝말잇기

문제 설명

1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다.

1. 1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다.
2. 마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.
3. 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.
4. 이전에 등장했던 단어는 사용할 수 없습니다.
5. 한 글자인 단어는 인정되지 않습니다.

다음은 3명이 끝말잇기를 하는 상황을 나타냅니다.

tank → kick → know → wheel → land → dream → mother → robot → tank

위 끝말잇기는 다음과 같이 진행됩니다.

• 1번 사람이 자신의 첫 번째 차례에 tank를 말합니다.
• 2번 사람이 자신의 첫 번째 차례에 kick을 말합니다.
• 3번 사람이 자신의 첫 번째 차례에 know를 말합니다.
• 1번 사람이 자신의 두 번째 차례에 wheel을 말합니다.
• (계속 진행)

끝말잇기를 계속 진행해 나가다 보면, 3번 사람이 자신의 세 번째 차례에 말한 tank 라는 단어는 이전에 등장했던 단어이므로 탈락하게 됩니다.

제한 사항

• 끝말잇기에 참여하는 사람의 수 n은 2 이상 10 이하의 자연수입니다.
• words는 끝말잇기에 사용한 단어들이 순서대로 들어있는 배열이며, 길이는 n 이상 100 이하입니다.
• 단어의 길이는 2 이상 50 이하입니다.
• 모든 단어는 알파벳 소문자로만 이루어져 있습니다.
• 끝말잇기에 사용되는 단어의 뜻(의미)은 신경 쓰지 않으셔도 됩니다.
• 정답은 [ 번호, 차례 ] 형태로 return 해주세요.
• 만약 주어진 단어들로 탈락자가 생기지 않는다면, [0, 0]을 return 해주세요.

입출력 예

소스 코드

자바

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

import java.util.HashSet;
class Solution {
    public int[] solution(int n, String[] words) {
        int[] answer = {0,0};
        char wordStart; // 두번째 단어부터 첫번째 문자 저장을 위한 변수 선언
        char wordEnd = words[0].charAt(words[0].length()-1); //처음 단어의 마지막 문자를 저장
        HashSet<String> hashSet = new HashSet<String>(); 
        hashSet.add(words[0]); // 첫단어를 해쉬셋에 저장
        for(int i=1; i<words.length;i++){ 
            hashSet.add(words[i]);
            wordStart = words[i].charAt(0);
            if(wordEnd!=wordStart || hashSet.size() != i+1){
                answer[0] = (i%n)+1;
                answer[1] = (i/n)+1;
                break;
            }
            wordEnd= words[i].charAt(words[i].length()-1); //다음단어의 처음 알파벳 비교를 위해 이번 단어의 마지막 알파벳 저장
        }
        return answer;
    }
}

소스코드 설명

1. 단어의 끝 알파벳과 그 다음 첫 알파벳이 다른 단어를 찾아라.
2. 중복된 단어를 찾아라.

문자열이 저장된 배열에서 단어 한개씩 새로운 자료구조에 담으면서 문자열의 마지막 문자와 다음 문자의 처음 문자를 비교하면서 1번을 해결하려 하였습니다.

담으면서 중복됬는지를 확인하기 위하여 자료구조는 HashSet을 이용하였습니다.

HashSet에는 중복 문자가 한번밖에 저장되지 않는 점을 이용하여 size()메서드를 이용하여 담기는 문자열이 이미 사용된 문자열인지 판단하였습니다.

카펫

문제 설명

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 빨간색으로 칠해져 있고 모서리는 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 빨간색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 빨간색 격자의 수 red가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 빨간색 격자의 수 red는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

입출력 예

출처

소스 코드

자바

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int[] solution(int brown, int red) {
        int[] answer = new int[2];
        int garo;
        int sero;
        for(int i=1; i<= red;i++){
            if(red%i==0){
                garo = i >= red/i? i :red/i;
                sero = i >= red/i? red/i :i;
                System.out.println(garo);
                System.out.println(sero);
                if(brown == (sero*2)+((garo+2)*2)){
                    answer[0]=garo+2;
                    answer[1]=sero+2;
                    break;
                }
            }
        }
        return answer;
    }
}

소스코드 설명

저는 카펫에 갈색 부분이 빨간 부분의 세로2 개, (가로+2)2 개만큼 있다는걸 발견 하였습니다.

빨간 부분의 개수를 이용해서 가로 세로가 되는 경우를 전부 구하며 그경우에 위에 식을 대입하여 갈색 부분의 갯수와 일치 하는지 확인하였습니다.

일치하는 경우가 빨간 부분의 가로 세로가 되고 전체 카펫의 가로와 세로의 길이는 빨간 부분의 가로와 세로에 각각 2개만큼 더한게 됩니다.

몫과 나머지를 이용하여 빨간 부분의 가로세로를 구하는 부분에서 더 큰값을 가로로 잡기위해 삼항연산자를 사용하였습니다.

선택정렬

1. 주어진 리스트 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

시간 복잡도

Best : O(n^2)

Avg : O(n^2)

Worst : O(n^2)

소스 코드

1
2
3
4
5
6
7
8
9
10
11

int[] a = new int[]{2,4,1,3,6,7,5,8,10,9};
for(int i=0;i<a.length-1;i++){
            int min = i;
            for(int j=i+1;j<a.length;j++){
                if(a[j]<a[min]){
                    min=j;
                }
            }
            swap(a,min,i);
        }
 System.out.println(Arrays.toString(a));

버블정렬

버블 정렬(Bubble Sort)은 인접한 두개의 원소를 비교하여 자리를 교환하는 방식으로 정렬

첫번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막자리로 이동하는 모습이

물속에서 물 위로 올라오는 물방울 모양과 같다고 해서 버블 정렬이라고 한다

시간 복잡도

Best : O(n^2)

Avg : O(n^2)

Worst : O(n^2)

소스 코드

1
2
3
4
5
6
7
8
9

int[] b = new int[]{2,4,1,3,6,7,5,8,10,9};
ffor(int i=0; i<b.length-1;i++){
             for(int j=0;j<b.length-1;j++){
                 if(b[j]>b[j+1]){
                     swap(b,j,j+1);
                 }
             }
         }
 System.out.println(Arrays.toString(b));

삽입정렬

삽입 정렬(insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

시간 복잡도

Best : O(n)

Avg : O(n^2)

Worst : O(n^2)

소스 코드

1
2
3
4
5
6
7
8
9
10
11

int[] c = new int[]{2,4,1,3,6,7,5,8,10,9};
for(int i=1; i<c.length;i++){
             int j=i;
             int temp=c[i];
             while(j>0&&c[j-1]>temp){
                 c[j]=c[j-1];
                 j--;
             }
             c[j]=temp;
         }
System.out.println(Arrays.toString(c));

퀵정렬

분할 작업을 순환적으로 반복하면서 피봇의 왼쪽 왼쪽 부분 집합과 오른쪽 부분집합을 정렬 하는 방법

1. 전체원소 가운데 하나의 원소를 중심(Pivot)으로 2개의 부분 집합으로 분할 한다.

2. 기준값(Pivot) 보다 작은 원소는 왼쪽 부분집합으로, 기준값(Pivot) 보다 큰 원소들은 오른쪽 부분 집합으로 정렬한다.

3. 분할된 부분집합의 크기가 0이나 1이 될 때 까지 순환 호출을 이용하여 다시 분할 한다.

시간 복잡도

Best : O(nlogn)

Avg : O(nlogn)

Worst : O(n^2)

소스 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public int pivot(int[] array, int start, int end){
        int middle = array[(start+end)/2];
    while(start<end) {
        while (array[start] < middle && start < end) start++;
        while (array[end] > middle && start < end) end--;
        if (start < end) {
            int temp = array[start];
            array[start] = array[end];
            array[end] = temp;
        }
    }
        return start;
}

 public void quicksort(int[] array,int start,int end ){
        if(start<end){
            int middle = pivot(array,start,end);

            quicksort(array, start,middle-1);
            quicksort(array,middle+1,end);
        }

}
int[] d = new int[]{2,4,1,3,6,7,5,8,10,9};
@Test
public void sort(){
    quicksort(d,0,d.length-1);
    System.out.println(Arrays.toString(d));
}