희연's 개발 일기장

• 입력 하나 받고 출력

n = input() # 입력 하나 받기
print(n) # 출력

• 값 교환

a, b = 10, 20
print(a, b) # 10 20
a, b = b, a
print(a, b) # 20 10

• 변수 타입 출력

a = 10
print(type(a)) # int
int, float, str

• 출력 방식

print("number")
print(a, b, c, sep=', ') # a, b, c 분리하는 방법 sep

• 줄바꿈 안하는 방법(end)

print(a, end=' ')

• 변수 입력과 연산자

a = input() # 입력 방법
print(a)

a = input("숫자를 입력하세요 : ") # 숫자를 입력하세요
a, b = input("숫자를 입력하세요 : ").split()

# 2개를 입력 받는 방식이 아니라, input으로 입력을 받은 후
# split을 통해 2개로 값을 분리 -> split
# split으로 분해되면 문자열로 들어간다.

print(a,b) # 3 5
print(a+b) # 35

# 다른 방법 - map
a, b = map(int, input("숫자를 입력하세요 : ").split())

• 사칙연산

input 3 2
a+b # 5
a-b # 1
a*b # 6
a/b 나누기 # 1.5
a//b 몫 # 1
a%b 나머지 # 2
a**b 거듭제곱 # 3^2

• 조건문

x=7
if x==7:
    print("Lucky")

if x>0 and x<10:
    print("10보다 작은 자연수")

if 0<x<10:
    print("10보다 작은 자연수")

if x>0:
    print("양수")
else:
    print("음수")

if x>=90:
    print('A')
elif x>=80:
    print('B')
else:
    print('F')

• 반복문

a = range(10) # 0~9까지 10개의 수
a = range(1, 11) # 1부터 10(1~10) 
print(list(a))

for i in range(10): # 0~9
    print(i)

for i in range(1,11): # 0~9
    print(i)

for i in range(10, 0, -2) # 10 8 6 4 2
    print(i)

i=1
while i<=10:
    print(i) # 1 ~ 10
    i=i+1 

i = 10
while i>=1:
    print(i)
    i = i-1

i=1
while True: # 1 ~ 10
    print(i)
    if i == 10:
        break
    i=i+1

for i in range(1, 11):
    if i%2==0:
        continue
    print(i) # 1 3 5 7 9

for i in range(1, 11):
    print(i)
    if i>15:
        break
else:
    print(11) # for문 정상 실행시 for else 구문 출력

# N = input() for문에서 N+1이 문자로 인식된다.
N = int(input()) # int 명시해주기
evenSum = 0
totalSum = 0
for i in range(1, N+1): 
    totalSum = totalSum + i
    if(i%2==1): # 짝수 출력
        print(i, end=' ')
    if(N%i==0): # 약수 출력
        print(i, end=' ')
print(totalSum) # 총합 출력

• 중첩 반복문(2중 for문)

for i in range(5): # 5번 반복
    print('i:', i, sep='', end=' ')
    for j in range(5):
        print('j:', j, sep='', end=' ')
    print()

for i in range(5):
    for j in range(i+1):
        print('*', end=' ')
    print()

for i in range(5):
    for j in range(5-i):
        print('*', end='')
    print()

• 문자열 접근 방법

# 문자열 접근 방법 1
for i in range(len(msg)): # 1~10
    print(msg[i], end='')

# 문자열 접근 방법 2
for x in msg: 
    print(x, end='')

• 대소문자, 문자열 쪼개기

msg = "It is Time"
print(msg.upper()) # 대문자 변환
print(msg.lower()) # 소문자 변환
print(msg)

tmp = msg.upper()
print(tmp)
print(tmp.find('T')) # 1 인덱스 번호를 찾아준다.
print(tmp[1]) # T
print(tmp.count('T')) # 2 특정 문자의 개수 출력
print(msg[:2]) # It : 제일 처음부터 1, 2번까지 
print(msg[3:5])
print(len(msg)) # 10


# 대소문자 출력
for x in msg:
    if x.isupper(): # 대문자만 출력
        print(x)

msg = "It is Time"
for x in msg:
    if x.isalpha(): # 알파벳만 출력
        print(x, end='')

• ASCII 표현

tmp = 'AZ'
for x in tmp:
    print(ord(x)) # ord는 아스키 넘버 출력 -> 65 90

tmp = 65
print(chr(tmp)) # 아스키 코드 출력 -> A

• 리스트와 내장함수

import random as r
a=[]
b=list()
print(a) # 같은 표현 1
print(b) # 같은 표현 2

a = [1,2,3,4,5]
b=list(range(1, 11)) # 1부터 10까지의 리스트
print(a+b) # 두개의 리스트를 합친다.
a.append(6) # 배열의 뒤에 원소를 추가하는 함수
a.insert(3, 7) # 3번 인덱스에 7 입력
a.insert(3, 7) # 3번 인덱스에 7 입력
a.pop() # 리스트 맨 뒤의 원소를 없애준다
a.insert(3, 7) # 3번 인덱스에 7 입력
a.pop(3) # 3번 인덱스 값을 제거해준다.
a.remove(4) # 4라는 값 찾아서 제거
print(a.index(5)) # 5라는 값의 인덱스 출력

a = list(range(1,11)) # 1부터 10까지의 리스트 생성
print(a) 
print(sum(a)) # 리스트 원소들의 총합
print(max(a)) # 최대값 출력
print(min(a)) # 최소값 출력
print(min(7,5)) # 인자 값들 중에서 최소값을 찾아주는 min

import random as r 
r.shuffle(a) # 랜덤으로 값을 섞어주는 라이브러리 
a.sort() # 오름차순 정렬
a.sort(reverse=True) # 내림차순 정렬
a.clear() # 리스트의 모든 값들이 삭제된다.

a = [23, 12, 36, 53, 19]
print(a[:3]) # 0~2번 index value output
print(a[1:4]) # 1~3번 index
print(len(a)) # 5

• 반복문으로 리스트 원소 접근

for i in range(len(a)): # 같은 결과 1
    print(a[i], end=' ')
print()

for x in a: # 같은 결과 2
    print(x, end=' ')
    
    
a = [23, 12, 36, 53, 19]
# 방식1
for x in enumerate(a): # 튜플 자료구조
    print(x)

# 방식2
for x in enumerate(a):
    print(x[0], x[1])
    
# 방식3 을 제일 많이 사용한다.
for index, value in enumerate(a):
    print(index, value)
    
# 출력 결과
# (0, 23)
# (1, 12)
# (2, 36)
# (3, 53)
# (4, 19)

리스트, 튜플, 셋, 딕셔너리

• list : [], 값 변경 가능
• tuple : (), 값 변경 불가능
• set : {}
• dictionary : {key:value, key:value}

b = (1,2,3,4,5)
print(b[0]) # 접근 방법 -> 1 출력
b[0] = 7 # 튜플의 값은 변경이 불가능하다

# if all, if any 사용방법
if all(50>x for x in a):
    print("YES")
else:
    print("NO")
# for문으로 a 리스트를 변수 x로 접근
# 60보다 큰 값들이 없어요 
# if all은 모든 값들이 해당되어야 한다. 1개라도 거짓이면 X

if any(15>x for x in a):
    print("YES")
else: 
    print("NO")
# any는 하나라도 참이면 참을 반환한다.

문제 

- 임의의 N개의 숫자가 주어진다.

- 오름차순으로 정렬하고, M의 값이 주어진 상태에서 M이 몇 번째에 있는지 프로그램 작성

- 이분 탐색 사용

- lt와 rt를 생성 후, 왼쪽과 오른쪽의 위치가 바뀔 때까지 왼쪽와 오른쪽의 중간값을 M과 비교한다.

import java.util.Arrays;
import java.util.Scanner;
public class Solution {
    public static int solution(int n, int m, int[] arr){
        int answer = 0;
        Arrays.sort(arr);
        int lt = 0;
        int rt = n-1;

        while(lt<=rt){ // 왼쪽이 오른쪽으로 가면 해제
            int mid = (lt+rt)/2;
            if(arr[mid]==m){
                answer = mid+1;
                break;
            } else if(arr[mid]<m){ // 왼쪽
                lt = mid +1;
            } else if(arr[mid]>m){ // 오른쪽
                rt = mid -1;
            }
        }

        return answer;
    }
    public static void main(String[] args) {
        Solution T = new Solution();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 수 개수
        int m = sc.nextInt(); // 구하는 수
        int[] arr = new int[n];
        for(int i=0; i<n; i++){
            int num = sc.nextInt();
            arr[i] = num;
        }
        System.out.println(T.solution(n,m,arr));
    }
}

투포인터 문제 - 두 배열의 공통 원소 출력

- 공통 원소를 추출해서 오름차순 출력하기

- 배열들을 미리 오름차순 정렬한다.

- 같은 값일 경우 둘 중에 아무거나 값을 넣고 둘 다 포인터 index를 증가시킨다.

- 더 작은 배열의 포인터 index를 증가시킨다.

- 첫 번째 배열이 더 큰 경우에 두 번째 배열 포인터 index++

- 두 번째 배열이 더 큰 경우에 첫 번째 배열 포인터 index++

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    public static ArrayList<Integer> solution(int[] arr1, int[] arr2){
        ArrayList<Integer> answer = new ArrayList<>();

        Arrays.sort(arr1);
        Arrays.sort(arr2);

        int p1=0;
        int p2=0;
        int n = arr1.length;
        int m = arr2.length;

        while(p1<n && p2<m){
            if(arr1[p1]==arr2[p2]){ // 둘중에 값 아무거나 넣고, 둘다 idx증가
                answer.add(arr1[p1++]);
                p2++;
            } else if(arr1[p1]>arr2[p2]){ // 1번째 배열이 더 큰 경우 -> 작은 쪽을 증가 시키기
                p2++;
            } else {
                p1++;
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        Solution T = new Solution();
        int[] arr1 = {1,3,9,5,2};
        int[] arr2 = {3,2,5,7,8};
        System.out.println(T.solution(arr1,arr2));
    }
}

슬라이딩윈도우 문제 - 연속된 K일의 최대 매출 구하기문제

- 수열에서 연속된 K개를 합했을 때, 합의 최대 값 구하기

- 일단 첫 번째부터 K번째 까지 값들을 다 더해줘서 max 값으로 지정한다.

- 그 이후로 k번째부터 배열의 마지막까지 반복문을 실행한다.

- sum = sum + 현재값 - 첫번째값

- 현재의 총합과 이전의 총합 중에서 최대 값으로 저장해준다.

- 배열을 종료 했을 때 나오는 최대 값이 수열에서 연속된 K개의 값들 중 최대 값이된다. 

public class Solution {
    public static int solution(int[] arr, int k){
        int answer = 0;
        int sum = 0;

        // 일단 맨 첫번째부터 k번째 값들을 다 더해준다.
        for(int i=0; i<k; i++){
            sum += arr[i];
        }
        answer = sum;

        // k부터 배열의 마지막까지 계산해본다.
        for(int i=k; i<arr.length; i++){
            sum+=(arr[i]-arr[i-k]); // 현재 값을 더해주고 맨 앞의 값을 지워준다.
            answer = Math.max(answer, sum); // 이전의 총합과 현재의 총합을 비교해줘서 최대값을 저장
        }

        return answer;
    }
    public static void main(String[] args) {
        Solution T = new Solution();
        int[] arr = {12,15,11,20,25,10,20,19,13,15};
        System.out.println(T.solution(arr, 3));
    }
}

복합적 문제 - 특정 숫자가 되는 경우의 수 구하기

- 투포인터는 O(N^2)에서 O(N)으로 개선 가능하다.

- N개의 수열에서 특정 숫자 M이 되는 경우의 수를 구해라

- N=8, M=6

- 수열 : 1 2 1 3 1 1 1 2

// sum이 M보다 크면 lt를 빼주고 lt++
// sum이 M보다 작으면 rt++

for(int rt=0; rt<N; rt++){ // 1. 증가
    sum+= arr[rt]; // 2. 더하기
    if(sum==M) answer++; // 3. 확인

    // sum이 M보다 커지면 삭제
    while(sum>=M){
        sum -= arr[lt++];
        if(sum==M){
            answer++;
        }
    }
}

복합적 문제 - 연속으로 1인 수열의 최대 길이 출력

public class Solution {
    public static int solution(int[] arr, int k){
        int N = arr.length; // 길이는 : rt - lt + 1
        int count = 0, lt=0;
        int answer = 0;

        for(int rt=0; rt<arr.length; rt++){
            if(arr[rt]==0) count++;
            while(count>k){
                if(arr[lt]==0) count--;
                lt++;
            }
            answer = Math.max(answer, rt-lt+1);
        }

        return answer;
    }
    public static void main(String[] args) {
        Solution T = new Solution();
        int[] arr = {1,1,0,0,1,1,0,1,1,0,1,1,0,1};
        System.out.println(T.solution(arr, 2));
    }
}

Hash + 슬라이딩 윈도우 - N일 중에서 K일 동안 벌어들일 수 있는 매출액의 종류를 각 구간별로 구하기

public class Solution {
    public static ArrayList<Integer> solution(int[] arr){
        int n = 7;
        int k = 4;
        ArrayList<Integer> answer = new ArrayList<>();
        HashMap<Integer, Integer> HM = new HashMap<>();

        for(int i=0; i<k-1; i++){
            HM.put(arr[i], HM.getOrDefault(arr[i],0)+1);
        }
        int lt = 0;
        for(int rt=k-1; rt<n; rt++){
            HM.put(arr[rt], HM.getOrDefault(arr[rt],0)+1);
            answer.add(HM.size());
            HM.put(arr[lt], HM.get(arr[lt])-1);
            if(HM.get(arr[lt])==0) {
                HM.remove(arr[lt]);
            }
            lt++;
        }
        return answer;
    }
    public static void main(String[] args) {
        Solution T = new Solution();
        int[] arr = {20,12,20,10,23,17,10};
        System.out.println(T.solution(arr));
    }
}

Hash + 슬라이딩 윈도우 - 모든 아나그램 찾기

import java.util.HashMap;

public class Solution {
    public static int solution(String s, String t){
        int answer = 0;
        HashMap<Character, Integer> am = new HashMap<>();
        HashMap<Character, Integer> bm = new HashMap<>();

        for(char x : t.toCharArray()) bm.put(x, bm.getOrDefault(x,0)+1);
        int L = t.length()-1;
        for(int i=0; i<L; i++) am.put(s.charAt(i), am.getOrDefault(s.charAt(i), 0)+1);
        int lt = 0;
        for(int rt=L; rt<s.length(); rt++){
            am.put(s.charAt(rt), am.getOrDefault(s.charAt(rt), 0)+1);
            if(am.equals(bm)) answer++;
            am.put(s.charAt(lt), am.get(s.charAt(lt))-1);
            if(am.get(s.charAt(lt))==0) am.remove(s.charAt(lt));
            lt++;
        }

        return answer;
    }
    public static void main(String[] args) {
        Solution T = new Solution();
        String s = "bacaAacbaa";
        String t = "abca";
        System.out.println(T.solution(s,t));
    }
}

문제

- 2차원 배열에서 자기 자신보다 상하좌우에서 높은 크기를 가지고 있는 값들이 있는 경우의 개수를 구하기

public class Main{
    static int[] dx = {-1,0,1,0};
    static int[] dy = {0,1,0,-1};
    public static int solution(int[][] arr){
        int answer = 0;
        int n = arr.length;

        for(int i=0; i<arr.length; i++){
            for(int j=0; j<arr.length; j++){
                boolean flag = true;
                //int current = arr[i][j];
                for(int d=0; d<4; d++){
                    //int nx = arr[i][j]+dx[d];
                    //int ny = arr[i][j]+dy[d];

                    int nx = i+dx[d];
                    int ny = j+dy[d];

                    // 경계선 넘지 않게 체크 0~n-1
                    if(nx>=0 && nx<n && ny>=0 &&ny<n && arr[nx][ny]>=arr[i][j]) { // 현재위치보다 상하좌우가 큼
                       flag = false;
                       break;
                    }
                }
                if(flag){
                    answer++;
                }
            }
        }

        return answer;
    }

문제

- 방향 그래프에서 1번에서 N번 정점으로 가는 모든 경로의 가지 수 출력하기

- 이동할 수 있는 정점을 체크할 graph, 방문 했었던 위치를 체크하기 위한 배열 ch를 선언한다.

- 정점에서 이동할 수 있는 정점을 graph에 1을 저장해서 체크해준다.

- DFS를 1번부터 실행

- v(현재 정점)과 n(목적지 정점)이 같으면 경로의 수 + 1

- 아닐 경우, 1번~n번 정점으로 갈 수 있는지 체크(graph[x][y]=1 간선으로 이어져 있고 && ch[i] ==0 방문하지 않았던 곳)

- 방문할 수 있는 정점일 경우 방문 체크를 해주고 다음 정점으로 넘어가기 전에 스택 프레임에 D(v)를 넣고 DFS(다음 정점) 실행

- 앞의 과정을 반복해서 n번 정점에 도착하게 되면 다시 돌아와서 ch[i] = 0 방문 체크를 해제 해준다. 

public class Solution {
    static int n, m, answer = 0;
    static int[][] graph; // 정점 체크
    static int[] ch; // 방문 체크
    public void DFS(int v){
        if(v==n){
            answer++;
        } else {
            for(int i=1; i<=n; i++){
                if(graph[v][i]==1 && ch[i]==0){ // v번 행에서 1~n까지 찾을 수 있는 정점 찾기
                    ch[i] = 1; // 방문 체크
                    DFS(i);
                    ch[i] = 0; // DFS 실행 후에 스택 프레임을 통해 다시 되돌아 올때 방문 풀어주기
                }
            }
        }
    }
    public static void main(String[] args) {
        Solution T = new Solution();
        Scanner sc = new Scanner(System.in);
        n = 5; // 정점의 수
        m = 9; // 간선의 수
        graph = new int[n+1][n+1];
        ch = new int[n+1];
        for(int i=0; i<m; i++){
            int x = sc.nextInt();
            int y = sc.nextInt();
            graph[x][y] = 1;
        }
        ch[1] = 1;
        T.DFS(1);
        System.out.println(answer);
    }
}

DFS

- 자식이 2개가 아닌 경우에는 DFS에서 오류가 난다. 

- 연습용 코드

class Node {
    int data;
    Node rt;
    Node lt;

    public Node(int val) {
        data = val;
        rt = lt = null;
    }
}
public class Solution {
    Node root;
    public int DFS(int L, Node root){
        if(root.lt==null && root.rt==null){
            return L;
        } else {
            return Math.min(DFS(L+1,root.lt), DFS(L+1,root.rt));
            // 자식이 2개가 아니면 DFS 에서는 말단 노드가 아닌 것이 출력되는 오류가 난다.
        }
    }

BFS

class Node{
    int data;
    Node rt;
    Node lt;

    public Node(int val){
        data = val;
        rt = lt = null;
    }
}

public class Solution {
    Node root;
    public int BFS(Node root){
        Queue<Node> Q = new LinkedList<>();
        Q.offer(root); // 큐에 루트 넣어준다.
        int L = 0; // 레벨은 0 부터
        while(!Q.isEmpty()){
            int len = Q.size(); // 레벨에 있는 원소 개수 = 큐의 사이즈
            for(int i=0; i<len; i++){
                Node current = Q.poll(); // 현재 (레벨) 큐에 있는 원소들
                if(current.lt==null && current.rt == null){
                    return L; // 말단노드의 경우 출력
                }
                // 자식 노드가 있는 경우 현재 노드의 자식 노드를 큐에 넣어준다.
                if(current.lt!=null){
                    Q.offer(current.lt);
                }
                if(current.rt!=null){
                    Q.offer(current.rt);
                }
            }
            // for문이 끝남 = 레벨 증가
            L++;
        }
        return 0;
    }

문제

- 현수와 송아지의 위치가 주어질 때, 현수가 송아지의 위치로 갈 수 있는 최소의 점프 횟수를 구해라

- 현수는 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5 이동 가능하다.

레벨 0에서 루트 노드를 큐에 넣어주고, 방문 체크를 해준다.

while문에서 큐의 사이즈를 구해준다. // 큐의 사이즈 = 레벨에 있는 원소의 개수

큐의 사이즈 만큼 for문을 돌려준다. 

큐에서 원소들을 꺼내준다. // 레벨에 있는 원소들

원소들이 다음에 갈 수 있는 위치들을 계산해준다. 

다음 위치의 원소들이 범위에서 벗어나지 않고, 방문하지 않았던 곳만 큐에 넣어준다.

이때, 다음 레벨의 원소가 송아지의 위치일 경우 현재레벨+1을 return 해준다.

없을 경우, for문이 종료되고 해당 레벨의 순회는 종료되어 레벨을 +1 증가 시켜준다.

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    int answer = 0;
    int[] dis = {1, -1, 5};
    int[] ch; // 체크 배열
    Queue<Integer> Q = new LinkedList<>();

    public int BFS(int s, int e){
        ch = new int[10001]; // 좌표는 1부터 10000까지
        ch[s] = 1; // 방문 체크
        Q.offer(s); // root 노드
        int L = 0; // 레벨 0에서 시작
        while(!Q.isEmpty()){
            int len = Q.size(); // 큐의 크기 = 레벨에 있는 원소
            for(int i=0; i<len; i++){
                int x = Q.poll(); // 레벨에 있는 노드 꺼내주기
                //if(x==e) return L; // 송아지 찾는 방법 1 : 레벨에 송아지의 위치가 존재하면 return
                for(int j=0; j<3; j++){ // 이동할 수 있는 3가지 경우의 수
                    int nx = x + dis[j]; // 현재노드 + 이동거리 = 이동한 노드의 위치
                    if(nx==e) return L+1; // 송아지 찾는 방법 2 : 다음 레벨에 송아지가 있다는 뜻
                    if(nx>=1 && nx<=10000 && ch[nx]==0){
                        // 범위에서 벗어나지 않고, 방문 체크 안한곳만
                        Q.offer(nx);
                    }
                }
            }
            // for문 종료되면 레벨 증가
            L++;
        }
        return 0;
    }

    public static void main(String[] args) {
        Solution T = new Solution();
        int s = 5;
        int e = 14;
        System.out.println(T.BFS(s, e));
    }
}

문제

- 이진트리 레벨 탐색하기

- 큐 사용

0레벨부터 N레벨까지 레벨 별로 탐색하기

- 일단 root노드를 0레벨에 만들고, 큐에 루트 노드를 넣는다.

- while문에서 큐에 원소가 없어질때까지 큐에 있는 원소 개수(레벨에 있는 원소 개수)만큼 출력해준다.

- queue에서 queue의 크기만큼 노드를 꺼내서 출력한다.

- 왼쪽과 오른쪽 자식이 있는 경우 현재 노드에서 왼쪽 자식과 오른쪽 자식 노드를 큐에 넣어준다.

if(current.lt!=null) if(current.rt!=null)

for이 종료되면 해당 레벨 탐색이 끝났다는 뜻으로, 레벨을 증가시킨다.

큐에 원소가 모두 제거되면 탐색을 종료한다.

class Node{
    int data;
    Node lt, rt;
    public Node(int val){
        data=val;
        lt=rt=null;
    }
}
public class Solution {
    Node root;
    public void BFS(Node root){
        Queue<Node> Q = new LinkedList<>();
        Q.offer(root);
        int L = 0; // root 노드 레벨은 0
        while(!Q.isEmpty()){
            int len = Q.size(); // Q의 원소의 개수
            System.out.print(L+" : "); // 해당 레벨의 원소들은 무엇이 있는지 출력
            for(int i=0; i<len; i++){ // 해당 레벨의 원소들이 모두 여기에서 나와야 함
                Node current = Q.poll(); // 노드 꺼내기
                System.out.print(current.data+" ");

                // 왼쪽, 오른쪽 자식을 queue에 넣어줘야 함
                if(current.lt!=null){
                    Q.offer(current.lt);
                }
                if(current.rt!=null){
                    Q.offer(current.rt);
                }
            }
            // for문이 끝나면 레벨 끝
            L++;
            System.out.println();
        }

    }
    public static void main(String[] args) {
        Solution tree = new Solution();
        tree.root = new Node(1);
        tree.root.lt = new Node(2);
        tree.root.rt = new Node(3);
        tree.root.lt.lt = new Node(4);
        tree.root.lt.rt = new Node(5);
        tree.root.rt.lt = new Node(6);
        tree.root.rt.rt = new Node(7);
        tree.BFS(tree.root);
    }
}