고마우미

5 3
10 20 30 20 10

70

문제접근

 제일 간단한 문제로는 loop를 돌며 일마다 일할 수 있는 연속 기간동안 추가 loop를 통해 합을 구해 비교하면 간단하게 구현 할 수있지만 O(n^2)의 시간 복잡도를 가지게 된다. 

 이를 해결하기 위해 제일 첫번째 날만 연속기간 일당을 구한 뒤 다음날 일자를 구할때는 해당 합에서 전날의 일당을 빼고 추가된 일당을 더해서 최대 이익을 구하는 방법으로 구현하였다.

1. 0일 부터 N - M 일까지 loop를 돈다.
2. 0일의 경우 0일 ~ M일 까지의 누적 합을 구한다.
3.  0일이 아닌 경우 전날짜의 임금을 빼고 다음날짜를 합한다.
4. 누적합이 이전 누적합의 최댓값보다 크면 최신화 한다. 

++ 합계를 구하는 변수가 int로 선언 된 경우 범위를 초과하여 오답처리 되었다. 해당 변수를 long 으로 변경한 이후 정상적으로 정답 처리 될 수 있었다.

문제풀이

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int day = Integer.parseInt(st.nextToken());
		
		int[] arr = new int[N];
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) 
			arr[i] = Integer.parseInt(st.nextToken());
		
		long maxProfit = 0;
		long tempSum = 0;


		
		for(int i = 0; i < N - day + 1; i++) {				// #1
			if(i == 0) {							// #2
				for(int j = 0; j < day; j++)
					tempSum += arr[j];
			}else {								// #3
				tempSum -= arr[i-1];
				tempSum += arr[i + day-1];
			}
			//System.out.println(i + " " + (i+day) + " " + arr[i+day-1] + " " + tempSum);
			
			if(tempSum > maxProfit)					// #4
				maxProfit = tempSum;
		}
		
		
		bw.write(maxProfit + "");
		bw.flush();
		br.close();
		bw.close();
		
		
	}

}

5
-2 4 -99 -1 98

-99 98

문제접근

2개 원소의 합을 구하여 일치하는 해를 구하면 되는 문제임으로 2개의 포인터를 주어 접근하면 되겠다는 생각이 들었다.

1. 입력 받은 자연수를 배열로 정렬한다.
2. loop를 돌면서 가장 작은 값의 인덱스 left , 가장 큰 값의 인덱스 right 를 두어 두 수를 합한다.
3. 두개의 값을 합하여 결과를 비교한다.
   • 합 한 값이 0에 가까운 경우 >> 최신화 밑 해당 인덱스 기억
   • 구하고자 하는 0 보다 작은 경우 -> left++
   • 구하고자 하는 0 보다 큰 경우 -> right--
4. loop는 i와 값이 j의 값보다 크거나 같은 경우 중단하며 저장된 인덱스를 반환한다

문제풀이

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());

		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		
		int[] arr = new int[N];
		
		for(int i = 0; i < N; i++) 
			arr[i] = Integer.parseInt(st.nextToken());

		Arrays.sort(arr);		// #1
		
		int answer = 0;
		
		int left = 0;
		int right = N-1;
		int temp;
		
		int saveLeft = 0;
		int saveRight = 0;
		
		int sum = Integer.MAX_VALUE;
		
		while(left < right) {		// #2
			temp = arr[left] + arr[right];

			//System.out.println(arr[left] + " " + arr[right] + " " + temp);
			
			if(Math.abs(temp) < sum) {
				sum = Math.abs(temp);
				saveLeft = left;
				saveRight = right;
			}
			
			
			
			if(temp > 0 ) {		// #3
				right--;
			}else {
				left++;
			}
		}
		
		bw.write(arr[saveLeft] + " " + arr[saveRight]);		// #4
		bw.flush();
		br.close();
		bw.close();
	}

}

문제

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)

출력

문제의 조건을 만족하는 쌍의 개수를 출력한다.

예제 입력 1

9
5 12 7 10 9 1 2 3 11
13

예제 출력 1

3

문제접근

2개 원소의 합을 구하여 일치하는 해를 구하면 되는 문제임으로 2개의 포인터를 주어 접근하면 되겠다는 생각이 들었다.

1. 입력 받은 자연수를 배열로 오름차순 정렬한다.
2. loop를 돌면서 가장 작은 값의 인덱스 i , 가장 큰 값의 인덱스 j를 두어 두 수를 합한다.
3. 두개의 값을 합하여 결과를 비교한다.
   • 구하자는 값인 경우 -> i++ j-- answer++
   • 구하고자 하는 값보다 작은 경우 -> i++
   • 구하고자 하는 값보다 큰 경우 -> j--
4. loop는 i와 값이 j의 값보다 크거나 같은 경우 중단하며 answer를 반환한다.

문제풀이

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

        StringTokenizer st;
        st = new StringTokenizer(br.readLine());

        int[] arr = new int[N];

        for(int i = 0; i < N; i++) 
            arr[i] = Integer.parseInt(st.nextToken());

        int sum = Integer.parseInt(br.readLine());

        Arrays.sort(arr);                //#1

        int answer = 0;

        int i = 0;
        int j = N-1;
        int temp;

        while(i < j) {                    //#2
            temp = arr[i] + arr[j];

            if(temp == sum) {            //#3
                answer++;
                i++;
                j--;
            }else if(temp < sum) {
                i++;
            }else {
                j--;
            }
        }

        bw.write(answer +"");            //#4
        bw.flush();
        br.close();
        bw.close();
    }

}

원티드 프리온보딩 인턴십 - 백엔드 6차 교육 내용 정리

Stack

Stack

• Stack은 Lifo 원칙 기반 선형 자료 구조
• 주요 연산
  • Push : 항목을 Stack의 맨위에 추가
  • Pop : Stack의 맨위에 항목을 제거하고, 그 항목을 반환
  • Top/Peek : Stack의 맨 위 항목을 반환 하지만, 제거 하지는 않음
  • IsEmpty : Stack이 비어 있는지 확인
• Stack의 사용 사례
  • Undo / Redo (Undo와 Redo 2개의 스택을 이용하여 구현)
  • 백 스페이스
  • 최근 작업 순서로되돌아가기
  • 프로그램 함수 호출 관리 (Call Stack)
  • 그 외 문자열 역순으로 바꾸기, 괄호의 짝 확인하기, 후위 표기법 변환하기
• 장점
  • 상수 시간의 기본연산
  • 메모리 효율성
  • 구현의 간결성
  • LIFO 특성

Stack의 시간 복잡도

Stack의 주요 연산에 따른 일반적인 시간 복잡도

• Push
  • Push 연산은 Stack의 맨 위(마지막)에 새로운 원소를 추가하는 연산
  • 배열로 구현한 Stack - O(1)
  • 연결리스트로 구현한 Stack - O(1)
• Pop
  • Pop 연산은 Stack의 맨 위에 있는 원소를 제거 하는 연산
  • 배열로 구현한 Stack - O(1)
  • 연결리스트로 구현한 Stack - O(1)
• Peek
  • Top 또는 Peek 연산은 맨 위에 있는 원소를 반환하지만 제거하지는 않는 연산
  • 배열로 구현한 Stack - O(1)
  • 연결리스트로 구현한 Stack - O(1)
• IsEmpty
  • IsEmpty 연산은 Stack이 비어있는지 확인하는 연산
• Size
  • Size 연산은 Stack에 현재 몇 개의 원소가 저장 되어 있는지 확인하는 연산
  • 배열로 구현한 Stack - O(1)
  • 연결리스트로 구현한 Stack - O(1)

Stack Overflow / Underflow

Stack Overflow / Underflow

• Stack Overflow : 스택이 할당된 메모리 용량을 초과하여 아이템을 추가하려고 할 때 발생하는 현상
• Stack Underflow : 스택이 비어 있을 때 아이템을 제거 하려고 할 때 발생하는 현상.

Stack Overflow / Underflow 시스템 영향

Spring Boot Application은 내부적으로 여러 스레드를 사용하여 작업을 처리함. (HTTP 요청을 처리하기 위한 워커 스레드, 데이터 베이스 연결을 관리하드는 스레드, 스케줄링 된 작업 등) Stack Overflow는 Thread 별로 할당된 스택 메모리 영역에서 발생하는데 주로 재귀 함수 호출의 depth가 깊어지는 경우, Stack 프레임의 크기가 너무 커져서 스택 메모리의 한계를 초과 할때 발생

• 스프링 부트 애플리 케이션에서 메인 스레드에서 Stack Overflow가 발생
  • 애플리케이션의 초기화나 빈 생성 과정에서 재귀적 호출이 발생할 경우, 메인 스레드에서 Stack Overflow가 발생. 메인 스레드에서 에러가 발생하면 애플리케이션 전체가 시작되지 않거나 중간에 중단 될수 있음.
  • 대부분의 Stack Overflow는 웹 요청 처리나 비즈니스 로직 수행 중에서 발생하는 경우가 많다. 웹 요청 처리나 비즈니스 로직 수행 중에 발생하는 경우, 해당 쓰레드만 종료되고, 다른 스레드는 영향을 받지 않는다.

Stack Overflow / Underflow 방지

• 재귀 함수 제한
• 예외 처리

중위 표현식을 후위 표현식으로 변환하는 알고리즘

• 중위 표현식
• a + b c - d
• 후위 표현식
• a b + c d -
• 초기상태
  • 연산자를 저장할 스택과 변환된 후위 표현식을 저장할 배열을 준비
  • operatorStack : x
  • postfixResult : x
• (a + b - c) * d
• ( 를 만남
  • 여는 괄호 ( 를 만나면, operatorStack에 추가합니다.
  • operatorStack : (
  • postfixResult : x
• a 를 만남
  • 숫자를 만나면 결과 리스트 postfixResult에 바로 추가합니다.
  • operatorStack : (
  • postfixResult : a
• + 연산자를 만남
  • 연산자를 만나면 opratorStack의 맨 위에 있는 연산자 (의 우선순위와 비교합니다. 현재 스택에는 ( 가 있으므로 +을 oprator Stack에 push합니다.
  • operatorStack : ( +
  • postfixResult : a
• b를 만남
  • 숫자를 만나면 postfixResult에 바로 추가합니다.
  • operatorStack : ( +
  • postfixResult : a b
• - 연산자를 만남
  • - 연산자를 만나면, operatorStack의 맨 위에 있는 연산자와의 우선 순위를 비교합니다. 현재 스택의 맨 위에 있는 연산자는 +이며 -와 +은 동일한 우선순위를 갖습니다.
  • operatorStack의 맨 위에 있는 연산자 +의 우선순위가 현재 연산자 -와 같거나 높으면, 해당 연산자를 pop하여 postfixResult에 추가한 다음 '-'를 operatorStack에 push합니다.
  • 이 작업은 operatorStack의 맨 위 연산자의 우선순위가 현재 연산자의 우선순위 보다 낮을 때 까지 계속합니다.
  • operatorStack : ( -
  • postfixResult : a b +
• c를 만남
  • operatorStack : ( -
  • postfixResult : a b + c
• )를 만남
  • 닫는 괄호 )를 만나면, operatorStack에서 여는 괄호 (가 나올 때까지 스택의 상단에 있는 연산자를 postResult에 추가하고, 스택에서 제거합니다. 여는괄호 (도 스택에서 제거합니다.
  • operatorStack : x
  • postfixResult : a b + c -
• *를 만남
  • * 연산자를 만나면, operatorStack의 맨 위에 있는 연산자의 우선순위와 비교합니다. 현재 operatorStack은 비어 있으므로, *를 operatorStack에 푸시합니다.
  • operatorStack : *
  • postfixResult : a b + c -
• d를 만남
  • 숫자를 만나면, postfixResult에 바로 추가합니다.
  • operatorStack : *
  • postfixResult : a b + c - d
• 중위 표현식의 모든 요소 순회 완료
  • 중위 표현식을 모두 순회했으므로, operatorStack에 남아있는 연산자들을 모두 pop하여 postfixResult에 추가합니다. 여기서 *를 팝하고 postfixResult 에 추가합니다.
  • operatorStack : x
  • postfixResult : a b + c - d *

Queue

Queue

• Queue는 FIFO 원칙을 따르는 선형 자료 구조입니다.
• 가장 먼저 들어온 요소가 가장 먼저 나가는 구조입니다
• 주요 연산
  • Enqueue : Queue의 맨 뒤에 원소를 추가하는 연산입니다. - O(1)
  • Dequeue : Queue의 맨 앞에 있는 원소를 제거하고 반환하는 연산입니다. - O(1)
  • Peek : Queue의 맨 앞에 있는 원소를 확인합니다. - O(1)
  • IsEmpty : Queue가 비어 있는지 확인합니다. - O(1)
• 사용 사례
  • OS CPU Scheduling
  • 프린터 대기열
  • Breadth-First Search (BFS)
  • 주문 처리 시스템
  • Data Streaming : 실시간 데이터 스트리밍 시스템에서는 데이터 패킷을 순서대로 처리해야합니다.
  • Packet Queue: [ Packet1 ] -> [ Packet2 ] -> [ Packet3 ] (First In) (Last In)
  • Load Balancing
  • Messaging
• Queue의 종류와 특징
  • 선형 큐
    • 가장 기본적인 Queue의 형태로 FIFO 원칙을 따릅니다.
    • 삽입 연산은 Queue의 뒤쪽에서, 삭제 연산은 Queue의 앞쪽에서 수행됩니다.
  • 순환 큐
    • 배열을 기반으로 하여, 배열의 마지막 요소 다음에는 배열의 첫번째 요소가 오는 형태
    • 원형 큐의 주요 이점은 공간을 재 사용 할 수 있으며, 앞부분이 비어 있고 뒷부분이 꽉 찼을 때, 새로운 요소를 배열의 앞부분에 넣을 수 있다.
  • 우선순위 큐
    • 각 항목이 우선순위와 함께 저장되는 Queue
    • Queue 에서 요소를 꺼낼 때 가장 높은 우선순위의 요소가 먼저 나옴
    • Heap 같은 특별한 자료 구조를 사용하여 구현 될 수 있다.
    • ex) 응급실 환자 대기열, 운영체제 프로세스 스케줄링
  • Deque
    • 양쪽 끝에서 추가 및 제거가 모두 가능한 큐
    • Deque는 스택 및 큐의 특징을 모두 가지고있음
    • 배열 또는 연결 리스트로 구현 될 수 있음
    • ex) 최근 방문한 사이트 주소 기록, 문서 작성 툴에서 undo/redo 기록