깊이 우선 탐색(dfs) 그래프의 시작 노드에서 출발하여, 한쪽 분기를 정해, 최대 깊이까지 탐색하는 알고리즘. 한번 방문한 노드는 다시 방문해서는 안된다.

구현 방법

• 재귀 함수
• 스택 이용

시간복잡도

• O(V+E) (노드 수 + 선분 수)

구현 구체화 방법

1. 그래프를 인접 리스트로 표현하기. ex) 1번 노드와 인접한 노드가 2,3 번이라면 list[1]={2,3}
2. 방문 리스트 추가하기. ex) 만약 1번 노드를 방문(stack에 input)했다면 visit[1]=true
3. stack에 pop 하며 인접 리스트 내용을 stack에 input (vist[2]=true, visit[3]=true), 이때 방문한 노드는 추가 안함.
4. stack이 빌 때까지 반복.

연결 요소의 개수 구하기

문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력 첫째 줄에 연결 요소의 개수를 출력한다.

입력 예시 6 5 1 2 2 5 5 1 3 4 4 6

출력 예시 2

코드 예시

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
stack = []
visit = [False] * (n + 1)
lst = [[] for _ in range(n + 1)]
count = 0
for _ in range(m):
    a, b = map(int, input().split())
    lst[a].append(b)
    lst[b].append(a)
while False in visit[1:]:
    count += 1
    stack.append(next(i for i in range(1, n + 1) if not visit[i]))
    while stack:
        a = stack.pop()
        if visit[a]:
            continue
        visit[a] = True
        stack.extend(i for i in lst[a] if not visit[i])
print(count)

가장 첫번째로, visit[i]=False 인 i를 stack에 넣고 순차적으로 시작한다. stack에 숫자가 존재하면, pop을 해서 visit[a] 이면 lst[a] 의 인접한 노드들을 stack에 넣는다.(visit 이 false 인 얘들만)

기수 정렬(radix sort) : 두 값을 비교하지 않고, 각 자리수에 따라 비교하여 정렬하는 알고리즘 시간복잡도 - O(kn) , k=데이터의 자릿수

ex) 16 80 18 77 03 24 88 23

• 1의 자리 숫자 기준으로 데이터 저장 list[0]={80} list[3]={03,23} list[4]={24} ...
• 순서대로(index=0 부터 pop) 10의 자리 숫자 기준으로 데이터 저장
• 다시 순서대로 pop 하면 정렬됨.
• 최대 데이터의 자릿수 만큼 진행해야 함. => 최대 수가 10000 이면, 5번 반복

수 정렬하기3(백준 10989번, 시간 제한: 3초)

문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

입력 예시 10 5 2 3 1 4 2 3 5 1 7

출력 예시 1 1 2 2 3 3 4 5 5 7

코드 예시

import sys
input = sys.stdin.readline
n=int(input())
arr=[0]*10001
for _ in range(n):
    arr[int(input())]+=1
for i in range(10001):
    k=arr[i]
    for j in range(k):
        print(i)

n의 최대 개수 10,000,000 이기 때문에 O(nlogn) 으로 문제를 접근 시, 시간 초과가 난다. 자릿수는 최대 5자리기이기 때문에 Radix sort나 Count Sort로 문제를 푸는 것이 좋다.

더 간단한 코드인 Count Sort 로 풀어보자. list를 010000 까지 가지고 있고, input이 들어올때마다, list[input]++ 을 한다. 그 다음, list 010000 까지 돌면서, list[i] 개수만큼 i를 출력하면 된다.

문제 N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오.

버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2 1 3 이 된다. 다음에는 2, 1이 바뀌어야 하므로 1 2 3 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다.

입력 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다.

출력 첫째 줄에 Swap 횟수를 출력한다.

입력 예시 3 3 2 1

출력 예시 3

코드 예시

import sys
input = sys.stdin.readline

def merge_sort(start,end):
    if(start<end):
        middle=(start+end)//2
        merge_sort(start,middle)
        merge_sort(middle+1,end)
        merge(start,middle,end)

def merge(start,middle,end):
    global result
    i=start
    k=start
    j=middle+1
    while i<=middle and j<=end :
        if list[i]<=list[j]:
            sorted[k]=list[i]
            k+=1
            i+=1
        else:
            sorted[k]=list[j]
            result=result+middle-i+1
            j+=1
            k+=1
    while i<=middle:
        sorted[k]=list[i]
        k+=1
        i+=1
    while j<=end:
        sorted[k]=list[j]
        k+=1
        j+=1
    for s in range(start,end+1):
        list[s]=sorted[s]

N=int(input())
list=list(map(int,input().split()))
sorted=[0]*int(N)
result = 0
merge_sort(0,N-1)
print(result)

이 문제는 이름과는 달리, 버블 소트를 하게되면 시간초과가 뜬다. N=500,000 이기 때문이다.

머지 소트는 정렬 시에, 투 포인터를 비교하며 정렬이 되는데, 이때 왼쪽으로 몇 칸이 이동하는지 세는 것과 같다. 이때, 배열 2개를 L(i 포인터), R(j 포인터) 이라고 할때, L 쪽의 현재 포인터가 더 크다면 (middle+1-i) 를 더해주면 된다.

=> 이정도 swap 이 되어야 함.

Divide and Conquer 방식을 이용하여, 데이터 분할 및 정렬하여 합치는 알고리즘. 시간 복잡도 => O(nlogn)

• 가장 작은 데이터 집합 부터 하나씩 정렬해가면서 => 전체 정렬

ex)

1. 42 32 24 60
2. 42 32 | 24 60
3. 32 42 | 24 60
4. 24 32 42 60

투 포인터를 이용하면 쉽게 정렬이 가능하다.

수 정렬하기(백준 2751번, 시간 제한: 2초)

문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

입력 예시 5 5 4 3 2 1

출력 예시 1 2 3 4 5

코드 예시

import sys
input = sys.stdin.readline
def merge_sort(start,end):
    if(start<end): # 나눌 수 있을 때까지 분할
        middle=(start+end)//2
        merge_sort(start,middle)
        merge_sort(middle+1,end)
        merge(start,middle,end)

 # 투 포인터를 이용하여 정렬.(두 배열 씩 짝짓기)
def merge(start,middle,end):
    i=start
    k=start
    j=middle+1
    while i<=middle and j<=end :
        if list[i]<list[j]:
            sorted[k]=list[i]
            k+=1
            i+=1
        else:
            sorted[k]=list[j]
            j+=1
            k+=1
    while i<=middle:
        sorted[k]=list[i]
        k+=1
        i+=1
    while j<=end:
        sorted[k]=list[j]
        k+=1
        j+=1
    for s in range(start,end+1):
        list[s]=sorted[s]

N=int(input())
list=[0]*int(N+1)
sorted=[0]*int(N+1)
for i in range(0,N):
    list[i]=int(input())
merge_sort(0,N-1)
for i in range(0,N):
    print(list[i],end="\n")

N의 범위가 1,000,000 이다. 때문에 O(nlogn) 시간 복잡도로 풀면 된다. => Merge Sort 를 사용하자.

CodeLab 소개

• 여기서 소개하고자 하는 widget 은 flutter widget 에 대한 내용이 아니라 실제 device 홈화면에서의 widget 에 대한 내용이다.

• 위젯은 홈화면에서 구현되는 부분이다 보니 복잡한 기능을 구현 할 수 없다.
  • IOS : 기본 텍스트, 간단한 그래픽
  • ANDROID : 기본 텍스트, 간단한 그래픽, 기본 컨트롤

• flutter 프레임워크에서는 홈 화면 위젯 UI 를 자체적으로 그리는 것이 불가능!

  ⇒ Jetpack Compose 나 SwiftUI 등의 플랫폼 프레임워크로 생성된 위젯을 flutter 앱에 추가하자.

CodeLab 목표

1. 홈위젯에 Flutter 앱의 데이터 표시.
2. 홈위젯에 Flutter 앱에서 공유하는 글꼴을 사용하여 텍스트 표시.
3. 홈위젯에 Flutter 위젯의 이미지를 표시.

파일 종류 및 패키지

• home_screen.dart : 헤드라인 및 간단한 설명이 있는 뉴스 리스트 화면
• article_screen.dart : 차트 및 전체 기사를 볼 수 있는 화면
• news_data.dart : NewsArticle class 및 mock data를 정의해 놓은 파일.
• shared_preferences : local device 에 저장하기 위한 패키지
• home_widget : 홈화면의 위젯과 flutter 간에 데이터를 공유시키는 패키지

In IOS

1. Make Basic IOS Home Widget

1. Xcode 실행
2. 설정 창에서 file→new→target 클릭 후
3. template 에서 widget extension 선택
4. flutter 앱 구성 업데이트 필요 ( flutter 앱에 새 패키지 추가 + Xcode에서 프로젝트 target 을 run 시킬 때) ⇒ 프로젝트 터미널에 flutter build ios --config-only 입력
5. Xcode 에서 Runner 대상 목록 새로 생성한 위젯을 선택하여 Run

(해당 과정까지 오류가 발생하지 않는다면?! 홈 화면 위젯 에서 새로 생성한 위젯을 찾을 수 있음.)

2. Connect HomeWidget and Flutter App Data

• codelab 에서는 flutter 와 homewidget 간의 data를 공유하는 방법은 local device storage 를 이용해서 key/value 값을 통해 접근.
• 해당 기능들은 SharedPreferences, home_widget 패키지를 통해서 구현이 가능.

1. Xcode의 singing & capabilities 에서 Runner, NewsWidgetExtension 모두 Bundle Identifier 설정.
2. Xcode의 singing & capabilities 에서 Runner, NewsWidgetExtension 모두 Capability 에서 App Groups 를 추가. (같은 그룹으로 설정해야 한다.)
3. dart 코드를 이용해서 홈 화면 위젯에 업데이트 하고자 하는 내용 추가. (코드 참고)
4. Xcode 에서 ios/NewsWidgets/NewsWidgets.swift 수정

struct NewsArticleEntry: TimelineEntry {
    let date: Date
    let title: String
    let description:String
}

기존의 SimpleEntry(원래 기본 홈위젯은 시간만 띄워줌) 를 우리가 원하는 정보(기사 제목, 기사 내용 등)를 띄워줄 NewsArticleEntry 로 바꾼다.

struct NewsWidgetsEntryView : View {
    var entry: Provider.Entry

    var body: some View {
      VStack {
        Text(entry.title)
        Text(entry.description)
      }
    }
}

여기서는 뉴스 기사 제목, 내용 들을 띄우기 위해 VStack 수정

struct Provider: TimelineProvider {

// 위젯을 처음 생성할 때 예시로 보이는 부분.
    func placeholder(in context: Context) -> NewsArticleEntry {
//      Add some placeholder title and description, and get the current date
      NewsArticleEntry(date: Date(), title: "Placeholder Title", description: "Placeholder description")
    }

// 현재 시간과 상태(ex.사용자의 기본값 데이터)에 대한 부분.
    func getSnapshot(in context: Context, completion: @escaping (NewsArticleEntry) -> ()) {
      let entry: NewsArticleEntry
      if context.isPreview{
        entry = placeholder(in: context)
      }
      else{
        //      Get the data from the user defaults to display
        let userDefaults = UserDefaults(suiteName: <YOUR APP GROUP>)
        let title = userDefaults?.string(forKey: "headline_title") ?? "No Title Set"
        let description = userDefaults?.string(forKey: "headline_description") ?? "No Description Set"
        entry = NewsArticleEntry(date: Date(), title: title, description: description)
      }
        completion(entry)
    }

//    getTimeline is called for the current and optionally future times to update the widget
//콘텐츠를 업데이트 할 시점 고려할 시 도움을 주는 함수 (타임라인 항목 관련)
    func getTimeline(in context: Context, completion: @escaping (Timeline<Entry>) -> ()) {
//      This just uses the snapshot function you defined earlier
// getSnapshot 함수를 통해서 현재 상태를 가져옴
      getSnapshot(in: context) { (entry) in
// atEnd method 는 현재 시간이 지날 시 데이터를 새로고침 하도록 홈화면 위젯에 명령
        let timeline = Timeline(entries: [entry], policy: .atEnd)
                  completion(timeline)
              }
    }
}

에러가 나지 않는다면? 정상적으로 작동한다.

1. 추가적으로 flutter 앱에서 뉴스 기사 세부 화면에서 floating button 클릭 시 홈화면 위젯이 정상적으로 바뀌는지도 체크하자!

3. Change Home Screen Widget Font by Flutter app custom fonts

• Xcode 에서 ios/NewsWidgets/NewsWidgets.swift 수정

struct NewsWidgetsEntryView : View {
   ...

   // font url 을 쉽게 가져올 수 있도록 도움을 주는 함수
   var bundle: URL {
           let bundle = Bundle.main
           if bundle.bundleURL.pathExtension == "appex" {
               // Peel off two directory levels - MY_APP.app/PlugIns/MY_APP_EXTENSION.appex
               var url = bundle.bundleURL.deletingLastPathComponent().deletingLastPathComponent()
               url.append(component: "Frameworks/App.framework/flutter_assets")
               return url
           }
           return bundle.bundleURL
       }
// path를 통해서 폰트를 등록
       init(entry: Provider.Entry){
         self.entry = entry
         CTFontManagerRegisterFontsForURL(bundle.appending(path: "/fonts/Chewy-Regular.ttf") as CFURL, CTFontManagerScope.process, nil)
       }
   ...
}

var body: some View {
    VStack {
      // Update the following line.
      Text(entry.title).font(Font.custom("Chewy", size: 13))
            Text(entry.description).font(.system(size: 12)).padding(10)
    }
   }

• 기존의 VStack은 뉴스 기사 제목, 내용만 간단하게 보여줬다면 해당 font 추가를 통해서 사이즈 및 폰트가 적용됨.

3. Rendering Flutter widgets as an image

• 간단하게 플러터 위젯을 홈화면 위젯에 보여지게 하고 싶다면? 이미지로 표시하면 된다!

 //global key 생성 (해당 위젯의 크기를 가져오는데 필요한 context를 가져올때)
final _globalKey = GlobalKey();
String? imagePath;
...
floatingActionButton: FloatingActionButton.extended( 
        onPressed: () async {
          if (_globalKey.currentContext != null) {
            var path = await HomeWidget.renderFlutterWidget(
//home_widget package 에 있는 renderFlutterWidget 메소드를 통해서 LineChart()를 image화 한다.
              const LineChart(),
             /// fileName: 'screenshot', 이 부분은 실제로 사용을 안함. 변수 존재 x
              key: 'filename',
              logicalSize: _globalKey.currentContext!.size,//global key 사용
              pixelRatio:
                  MediaQuery.of(_globalKey.currentContext!).devicePixelRatio,
            );
            setState(() {
              imagePath = path as String?; //flutter위젯이 렌더링되는 image 위치 저장
            });
          }
          updateHeadline(widget.article);
        },

...
            Center(
            // New: Add this key 해당 currentContext 사용하기 위해서
            key: _globalKey,
            child: const LineChart(),
          ),

• renderFlutterWidget 메소드가 호출 시

  • Flutter Widget 을 PNG 파일로 변환
  • Local DB 에 저장. (이때 key는 filename으로 저장되어 있다.)

• Xcode 에서 ios/NewsWidgets/NewsWidgets.swift 수정

struct NewsArticleEntry: TimelineEntry {
   ...
        let date: Date
    let title: String
    let description:String

   // New: add the filename and displaySize.
   let filename: String
   let displaySize: CGSize
}

새롭게 들어올 NewsArticleEntry 구조를 적어준다.

func placeholder(in context: Context) -> NewsArticleEntry {
      NewsArticleEntry(date: Date(), title: "Placholder Title", description: "Placholder description", filename: "No screenshot available",  displaySize: context.displaySize)
    }

처음 홈화면위젯을 선택시에 보여지는 부분인 placeholder 를 수정한다.

struct NewsWidgetsEntryView : View {
   ...

   // New: create the ChartImage view
   var ChartImage: some View {
        if let uiImage = UIImage(contentsOfFile: entry.filename) {
            let image = Image(uiImage: uiImage)
                .resizable()
                .frame(width: entry.displaySize.height*0.5, height: entry.displaySize.height*0.5, alignment: .center)
            return AnyView(image)
        }
        print("The image file could not be loaded")
        return AnyView(EmptyView())
    }
   ...
}

chartImage 가 보일 수 있도록 다음과 같이 코드를 추가해준다. 이때 크기는 frame의 50% 로 설정했다.

VStack {
   Text(entry.title).font(Font.custom("Chewy", size: 13))
   Text(entry.description).font(.system(size: 12)).padding(10)
   // New: add the ChartImage to the NewsWidgetEntryView
   ChartImage
}

Vstack 에 CharImage 를 추가해서 실제로 잘 동작 하는지 체크해보자.

최종적으로 IOS device 에서

flutter 내부의 data 를 홈화면 위젯에서 공유 할 수 있다.

pivot 을 정해 해당 값보다 작은 데이터와 큰 데이터로 분류하여 recursive 하게 정렬하는 알고리즘 =Divide and conquer 시간복잡도가 일반적으로 O(nlogn)이지만 최악의 경우 O(n^2)

start, end 2개의 포인터가 있어 pivot 기준 start 쪽 데이터가 더 작으면 오른쪽으로 한 칸씩 이동하고 end 쪽 데이터가 더 크면 왼쪽으로 한 칸씩 이동한다. 만약 만약 둘 중 하나라도 차이가 난다면 swap을 한다. start=end가 되면 start+1에 해당하는 데이터와 pivot을 서로 바꾼다. 이 후 recursive 하게 진행하면 된다.

코드를 통해 이해하는 것이 가장 좋을 것이다.

K번째 수 구하기(백준 11004번, 시간 제한: 2초)

문제 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오.

입력 첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다. 둘째에는 A1, A2, ..., AN이 주어진다. (-10^9 ≤ Ai ≤ 10^9)

출력 A를 정렬했을 때, 앞에서부터 K번째 있는 수를 출력한다.

입력 예시 5 2 4 1 2 3 5

출력 예시 2

코드 예시

import sys
input=sys.stdin.readline
n,k=map(int,input().split())
A=list(map(int,input().split()))
def quickSort(start,end,k): #k 번째 수가 pivot 이면 더이상 구할 필요가 없다. 불필요한 sorting 안함.
    global A
    if start<end:
        pivot=partition(start,end) #pivot은 index이다. 
        if pivot==k:
            return
        elif k<pivot: #k가 pivot보다 작으면 왼쪽 그룹만 정렬하면 된다. 
            quickSort(start,pivot-1,k)
        else :
            quickSort(pivot+1,end,k)
def swap(i,j):
    global A
    temp=A[i]
    A[i]=A[j]
    A[j]=temp
def partition(start,end):
    global A
    if start+1==end: #data 가 2개일 경우
        if A[start]>A[end]:
            swap(start,end)
        return end
    M=(start+end)//2 #중간 index를 pivot으로 고른다
    swap(start,M) # pivot에 해당하는 값을 가장 앞으로 옮긴다
    pivot=A[start]
    i=start+1 # pivot이 start 자리를 이미 차지했음
    j=end 
    while i<=j:
        while pivot<A[j] and j>0: # j를 먼저 끝까지 찾아가본다  j를 기준으로 문제를 풀었음.
            j=j-1
        while pivot>A[i] and i<len(A)-1:
            i=i+1
        if i<=j:
            swap(i,j)
            i=i+1
            j=j-1
    A[start]=A[j]
    A[j]=pivot #pivot과 자리 바꾸기
    return j
quickSort(0,n-1,k-1) #k-1 이 원하는 index 위치
print(A[k-1]) 

int partition(int A[], int start, int end)
{
    int pivot = A[end];
    int index = start - 1;
    for (int i = start; i < end; i++)
    {
        if (A[i] <= pivot)
        {
            index++;
            int temp = A[i];
            A[i] = A[index];
            A[index] = temp;
        }
    }
    index++;
    int temp = A[end];
    A[end] = A[index];
    A[index] = temp;
    return index;
}

void quick_sort(int A[], int start, int end)
{
    if (start < end)
    {
        int q = partition(A, start, end);
        quick_sort(A, start, q - 1);
        quick_sort(A, q + 1, end);
    }
}

c 언어를 이용해서 풀었던 것과 비교도 한번 해보자. partition 구하는 방법은 여러가지가 있기 때문에 정답은 없는 듯 하다!!

정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입하여 정렬하는 방식. 시간 복잡도는 O(n^2)

ATM인출 시간 계산하기(백준 11399번, 시간 제한: 1초)

문제 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다. 줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다. 줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

입력 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

출력 첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

입력 예시 5 3 1 4 3 2

출력 예시 32

코드 예시

import sys
input=sys.stdin.readline
n=int(input())
A=list(map(int,input().split()))
for i in range(1,n):
    index=i #index에 A[i]를 넣어야한다
    for j in range(i):
        if A[i]<A[j]:
            index=j 
            break
    temp=A[i] 
    for k in range(i,index,-1):
        A[k]=A[k-1] #하나씩 뒤로 당긴다
    A[index]=temp
S=[0]*n
S[0]=A[0]
for i in range(1,n):
    S[i]=S[i-1]+A[i]
print(sum(S))

해당 문제는 greedy 문제이다. 가장 적게 걸리는 사람부터 정렬하면 모든 사람 atm 이용의 최소의 시간이 걸리게 된다.

시간 제한이 적기 때문에 insertion sort 를 사용하였다.

S 배열은 Sum 배열이므로 누적 합을 이야기 한다. 해당 S 배열을 다시 Sum 하면 전체 걸린 총 시간이 된다.

=>range 함수 사용 시 3번째 인자에 값을 주면 원하는 만큼 건너 띄도록 한다. (뒤로 이동 시 -1)

데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법. 왼쪽부터 정렬되므로 inner for문 시 시작 지점을 잘 정하는 것이 그나마 효율성 측면에서 좋음.

코팅테스트에서는 거의 사용하지 않는 알고리즘이다.

내림차순으로 자릿수 결정하기(백준 1427번, 시간 제한 2초)

문제 배열을 정렬하는 것은 쉽다. 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자.

입력 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.

출력 첫 줄에 자리수를 내림차순으로 정렬한 수를 출력한다.

입력 예시 2143

출력 예시 4321

코드 예시

import sys
input=sys.stdin.readline
A=list(input())
for i in range(len(A)):
    for j in range(i+1,len(A)):
        if(A[i]<A[j]):
            temp=A[j]
            A[j]=A[i]
            A[i]=temp
for i in range(len(A)):
    print(A[i],end='')

selection sort로 간단하게 풀어보았다.

여기서 특이점은 list(input()) 즉, list 함수를 사용해서 input() 에 대해 각 원소들을 list로 저장한다. data type이 int 가 아닌 str 형태로 sorting 을 진행했다.

사실 ascii code 역시 특정 값을 가지고 있기 때문에 sorting에 전혀 문제가 되지 않는다.

문제 버블 소트 알고리즘을 다음과 같이 C++로 작성했다.

bool changed = false;
for (int i=1; i<=N+1; i++) {
    changed = false;
    for (int j=1; j<=N-i; j++) {
        if (A[j] > A[j+1]) {
            changed = true;
            swap(A[j], A[j+1]);
        }
    }
    if (changed == false) {
        cout << i << '\n';
        break;
    }
}

위 소스에서 N은 배열의 크기이고, A는 정렬해야 하는 배열이다. 배열은 A[1]부터 사용한다. 위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구해보자.

입력 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다.

출력 정답을 출력한다.

입력 예시 5 10 1 5 2 3

출력 예시 3

코드 예시

import sys
input=sys.stdin.readline
n=int(input())
a=[]
for i in range(n):
    a.append((int(input(),i)))
Max=0
sort_a=sorted(a)
for i in range(n):
    if Max<sort_a[i][1]-i:#정렬 전 index-정렬 후 index
        Max=sort_a[i][1]-i
print(Max+1)

해당 문제는 시간 제한이 2초인 반면 n이 50만 이기 때문에 O(n^2) 으로 문제를 해결하지 못한다.

그래서 기본 내장 함수인 sorted 함수를 써서 O(nlogn) 시간복잡도가 필요하다.

idea는 sorting을 했을 때 이전 index 와 sorting 후 index 를 비교하는 것이다. 둘을 빼게 된다면 이동한 index 가 나오는데 양수일 경우 오른쪽에서 왼쪽으로 이동한 경우이다.

bubble sort 특성상 항상 오른쪽 끝부터 채워지기 때문에, 최대 오른쪽에서 왼쪽 이동한 것을 찾는다면 그 다음 for문 이후로는 sorting 과정이 필요 없이, 이미 sorting 되어 있다는 것을 알 수 있다. 즉 break를 걸어도 상관 없다는 뜻이다.

=> Bubble sort 의 개념을 완벽히 이해해야만 풀 수 있는 생각보다 어려운 문제였다..

Bubble Sort: 데이터의 인접 요소끼리 비교, swap방식을 통해 정렬하는 방식 Selection Sort: 대상에서 가장 크거나 작은 데이터를 찾아 선택하면서 정렬하는 방식 Selection Sort: 대상을 선택해 정렬된 영역에서 적절한 위치를 찾아가며 삽입하여 정렬하는 방식 Quick Sort: pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식 Merge Sort: 이미 정렬된 부분 집합들을 효율적으로 병합하여 전체를 정렬하는 방식 Radix Sort: 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식

Bubble Sort

결국 최종적으로 배열의 가장 끝부분부터 정렬된다고 생각하면 된다.

수 정렬하기 (백준 2750번, 시간 제한: 2초)

문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

입력 예시 5 5 2 3 4 1

출력 예시 1 2 3 4 5

코드 예시

import sys
input=sys.stdin.readline
n=int(input())
a=[]
for i in range(n):
    a.append(int(input()))
print(a)
for i in range(n):
    for j in range(n-i-1):
        if a[j+1]<a[j]:
            temp=a[j]
            a[j]=a[j+1]
            a[j+1]=temp
for i in range(n):
    print(a[i])

N이 최대 1000이기 때문에 시간복잡도는 O(n^2) 으로도 충분하다. 즉 이번에는 bubble sort 로 짜보았다. 우리가 알고 있는 것처럼 서로 인접한 두 원소를 비교하여 sorting 한다.

이 과정을 하게 되면 가장 끝 원소는 가장 큰 원소가 들어가게 되므로 굳이 해당 구간까지 계속해서 반복문을 돌릴 이유는 없다.

문제 절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다. 배열에 정수 x (x ≠ 0)를 넣는다. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -2^31보다 크고, 2^31보다 작다.

출력 입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

입력 예시 18 1 -1 0 0 0 1 1 -1 -1 2 -2 0 0 0 0 0 0 0

출력 예시 -1 1 0 -1 -1 1 1 -2 2 0

코드 예시

import sys
from queue import PriorityQueue
input=sys.stdin.readline
n=int(input())
queue=PriorityQueue()
for i in range(n):
   temp=int(input())
   if temp==0:
        if queue.empty():
            print("0")
        else:
            temp2=queue.get()
            print(temp2[1])
   else :
       queue.put((abs(temp),temp))

해당 문제는 Priorty Queue 를 사용해서 우선순위 대로 queue에 넣으면 된다.

여기서 알아야 할 점은 prityqueue 같은 경우 pop() 명령어가 아닌 get() 명령어를 통해 pop과 같은 역할을 수행한다.

그리고 이전에 사용했던 len(queue) 같은 Len 함수 사용이 안되었다.

마지막으로 queue에 element를 넣을 때 절대값 temp, temp를 둘 다 넣어 우선 절대값 Temp로 sorting 된 상태로 넣고 만약 절대값이 같다면 temp (즉, 음수인것 부터) 로 sorting 하여 queue를 가지고 있으면 된다.

문제 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다. N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

입력 첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.

출력 첫째 줄에 남게 되는 카드의 번호를 출력한다.

입력 예시 6

출력 예시 4

코드 예시

import sys
from collections import deque
input=sys.stdin.readline
n=int(input())
queue=deque()
count=1
for i in range(n):
    queue.append(i+1)
while len(queue)!=1:
    if count%2==0:
        queue.append(queue[0])
    queue.popleft()
    count+=1
print(queue[0])

이번 문제는 어렵지 않게 풀 수 있다. queue에 대한 것으로 주어진 문제대로 반목문 횟수가 홀수 일때는 front를 버리고 반복문 횟수가 짝수 일때는 front를 append 하고 해당 Front를 버리면 해결된다.

이렇게 queue의 개수가 1개가 남을때 까지 진행하면 된다.

문제 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다. 예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력 총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

예시 입력 4 3 5 2 7

예시 출력 5 7 7 -1

예시 코드

import sys
input=sys.stdin.readline
n=int(input())
arr=list(map(int,input().split()))
ans=[-1]*n
stack=[]
for i in range(n):
    while stack and arr[stack[-1]]<arr[i] :
        ans[stack.pop()]=arr[i]
    stack.append(i) #index를 stack에 넣어야 한다.
print(*ans)

이 문제에서 n은 최대 백 만이다. 2중 반복문을 돌며 문제를 풀 수 없다는 뜻이다.

stack을 활용하여 문제를 풀어야 한다. 특징은 stack에 index를 저장하는 것이다. stack의 top이 arr[i] 보다 작은지 확인하고 작다면 ans 배열에 해당 top index 부분에 arr[i]를 집어 넣는다. 그리고 stack에 index i 를 append 한다.

만약 arr[stack[-1]]<arr[i] 이게 없다면 ans[stack[-1]] 은 -1 이 나와야 하니 처음부터 -1로 ans 배열을 초기화 시키는 것이 시간복잡도를 줄이는 데 도움이 될 것이다.

추가적으로 print(*ans) 를 하면 list 같은 iterable 객체를 개별 요소로 분리하여 출력한다. space bar를 두고 출력된다. 굳이 반복문을 돌릴 필요가 없다!!

print(ans[i],end=" ")를 사용하면 마지막에 % 기호가 붙는다..? => 왜지?

stack 은 후입선출 (Last in First Out) LIFO 형식으로 이루어진 자료구조.

stack.append(data) 를 하면 가장 뒤쪽에 들어오고 stack.pop() 을 하면 가장 뒤쪽이 삭제된다. top pointer로 stack에서 가장 새롭게 들어온 부분을 가르키게 된다.

값1, 값2, 값3, 값4 에서 값5를 넣으면 값1, 값2, 값3, 값4, 값5 이렇게 된다.----->top은 값5

연산 top: 삽입, 삭제가 일어날 위치 append(data): 데이터 삽입 pop(): 데이터 삭제 s[-1]: top에 데이터가 있는지 없는지 확인하는 연산

DFS, Back tracking 등에 쓰임.

Queue

queue 은 선입선출 (First in First Out) FIFO 형식으로 이루어진 자료구조.

queue.append(data) 를 하면 rear 쪽에 데이터가 들어오고 queue.popleft() 를 하면 front 쪽의 데이터가 삭제된다.

연산 rear: 큐의 가장 끝 데이터가 가리키는 영역 front: 큐의 가장 앞 데이터가 가리키는 영역 append(data): rear 쪽 데이터 삽입 popleft(): front쪽 데이터 삭제 q[0]: front에 데이터가 있는지 없는지 확인하는 연산

BFS 등에 주로 쓰임.

Priority Queue

우선 순위 큐는 값이 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조. heap을 이용하여 구현하는게 일반적이다.

해당 내용은 추후 heap을 다룰 때 자세히 공부하도록 하겠다.

스택으로 수열 만들기(백준 1874번, 시간 제한: 2초)

문제 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다. 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

입력 첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

출력 입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

입력 예시 8 4 3 6 8 7 5 2 1

출력 예시

코드 예시 (python)

from collections import deque
import sys
input=sys.stdin.readline
n=input()
A=[0]*n
for i in range(n):
    A[i]=int(input())
stack=[]
num=1
ans=""
result=True
for i in range(n):
    if A[i]>=num:
        while A[i]>=num:
            stack.append(num)
            num+=1
            ans+="+\n"
        stack.pop()
        ans+="-\n"
    else:
        if stack.pop()>A[i]:
            print("NO")
            result=False
            break;
        else:
            ans+="-\n"
if result:
    print(ans)



stack을 사용해야 한다.
A[i]가 num보다 크다면 stack에 num을 하나씩 넣는다.
A[i]<num 이 되면 해당 stack에 pop 한다.
만약 pop 한 결과가 A[i]이 아니면 NO 를 출력하면 된다.

>
```py
else:
        if stack.pop()==A[i]:
            ans+="-\n"
        else:
            print("NO")
            result=False
            break;

즉, 이렇게 수정해도 된다.

코드 예시(c)

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main(){
    int n;
    int top=-1;
    int index=0;
    int result_index=0;
    int A[100001];
    int stack[100001];
    char result[200002];
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&A[i]);
    }
    int num=1;
    while(1){
        if(top==-1||stack[top]<A[index]){
            top++;
            stack[top]=num++;
            result[result_index]='+';
            result_index++;
        }
        else if(stack[top]==A[index]){
            top--;
            result[result_index]='-';
            result_index++;
            index++;
        }
        else {
            printf("NO\n");
            return 0;
        }
        if(index==n)break;
    }
    for(int i=0;i<result_index;i++)
        printf("%c\n",result[i]);
    return 0;
}

문제 예시 N개의 수 A1, A2, ..., AN과 L이 주어진다. $D_i$= $A_{i-L+1}$ ~ $A_i$ 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 $A_i$는 무시하고 D를 구해야 한다.

입력 첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000) 둘째 줄에는 N개의 수 $A_i$가 주어진다. ($-10^9 ≤ A_i ≤ 10^9$)

출력 첫째 줄에 $D_i$를 공백으로 구분하여 순서대로 출력한다.

입력 예시 12 3 1 5 2 3 6 2 3 7 3 5 2 6

출력 예시 1 1 1 2 2 2 2 2 3 3 2 2

코드 예시

from collections import deque
import sys
input=sys.stdin.readline
n,l=map(int,input().split())
mydeqeue=deque()
arr=list(map(int,input().split()))
for i in range(n):
    while mydeqeue and mydeqeue[-1][0]>arr[i]:
        mydeqeue.pop()
    mydeqeue.append((arr[i],i))
    if mydeqeue[0][1]<=i-l:
        mydeqeue.popleft()
    print(mydeqeue[0][0],end=" ")

해당 문제는 input N,L이 각 5백만이기 때문에 sorting 시에 필요한 O(nlogn)이 아닌 O(n) 시간복잡도로 문제를 풀어야 하기 때문에 매우 어렵다. 이때 python 은 deque(덱) 자료구조를 지원하기 때문에 상대적으로 쉽게 풀 수 있다. sorting을 O(n)으로 할 수 있다는 장점이 있다.

덱의 구조는 appendleft()<--------------> append() popleft()<-----------------> pop()

이렇게 stack, queue 를 합쳐놓은 구조이다. 양방향으로 넣고 뺄 수 있는 장점이 있다.

그래서 해당 문제는 우선 첫번째 arr[i],i 두 노드를 덱에 넣는다. 이후 두번째 노드를 넣는데 그 전에, 가장 마지막 노드인 deque[-1][0] 과 arr[i]를 비교하여 arr[i]가 더 작으면 deqeue[-1]을 pop 한다. 우리는 가장 작은 값들만 원하기 때문에 필요 없는 노드이기 때문이다. 그 다음 해당 노드를 넣는다. 만약 deque[0][1] 즉 deque 의 가장 첫번째 노드의 Index가 i-l 보다 작거나 같다면 window를 벗어난 것 이기 때문에 해당 노드도 pop 해야 한다.

이 과정을 통해 deque[0][0]이 해당 window 에서 가장 작은 값인 것을 알 수 있다.

추가 설명

일반적으로 python 의 Print 가장 마지막은 개행문자로 끝이 난다. 이를 바꾸기 위해서는 end= 원하는 문자를 적으면 된다. int, char 같은 서로 데이터타입이 다른 경우는 + 연산이 되지 않아 , 를 사용한다.

그리고 c언어와 달리 arr[-1] 처럼 음수 index인 경우 뒤에서부터 접근이 가능하다!! 2018년에 배웠더니 이런 사소한 것들이 기억나지 않는다..

슬라이딩 윈도우는 기존의 투 포인터 문제와 다르게 일정 window를 유지한 채로 sliding 하며 푸는 문제를 의미.

DNA 비밀번호(백준 12891번, 시간 제한: 2초)

문제 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA”는 DNA 문자열이 아니지만 “ACCA”는 DNA 문자열이다. 이런 신비한 문자열에 완전히 매료된 민호는 임의의 DNA 문자열을 만들고 만들어진 DNA 문자열의 부분문자열을 비밀번호로 사용하기로 마음먹었다. 하지만 민호는 이러한 방법에는 큰 문제가 있다는 것을 발견했다. 임의의 DNA 문자열의 부분문자열을 뽑았을 때 “AAAA”와 같이 보안에 취약한 비밀번호가 만들어 질 수 있기 때문이다. 그래서 민호는 부분문자열에서 등장하는 문자의 개수가 특정 개수 이상이여야 비밀번호로 사용할 수 있다는 규칙을 만들었다. 임의의 DNA문자열이 “AAACCTGCCAA” 이고 민호가 뽑을 부분문자열의 길이를 4라고 하자. 그리고 부분문자열에 ‘A’ 는 1개 이상, ‘C’는 1개 이상, ‘G’는 1개 이상, ‘T’는 0개 이상이 등장해야 비밀번호로 사용할 수 있다고 하자. 이때 “ACCT” 는 ‘G’ 가 1 개 이상 등장해야 한다는 조건을 만족하지 못해 비밀번호로 사용하지 못한다. 하지만 “GCCA” 은 모든 조건을 만족하기 때문에 비밀번호로 사용할 수 있다. 민호가 만든 임의의 DNA 문자열과 비밀번호로 사용할 부분분자열의 길이, 그리고 {‘A’, ‘C’, ‘G’, ‘T’} 가 각각 몇번 이상 등장해야 비밀번호로 사용할 수 있는지 순서대로 주어졌을 때 민호가 만들 수 있는 비밀번호의 종류의 수를 구하는 프로그램을 작성하자. 단 부분문자열이 등장하는 위치가 다르다면 부분문자열이 같다고 하더라도 다른 문자열로 취급한다.

입력 첫 번째 줄에 민호가 임의로 만든 DNA 문자열 길이 |S|와 비밀번호로 사용할 부분문자열의 길이 |P| 가 주어진다. (1 ≤ |P| ≤ |S| ≤ 1,000,000) 두번 째 줄에는 민호가 임의로 만든 DNA 문자열이 주어진다. 세번 째 줄에는 부분문자열에 포함되어야 할 {‘A’, ‘C’, ‘G’, ‘T’} 의 최소 개수가 공백을 구분으로 주어진다. 각각의 수는 |S| 보다 작거나 같은 음이 아닌 정수이며 총 합은 |S| 보다 작거나 같음이 보장된다.

출력 첫 번째 줄에 민호가 만들 수 있는 비밀번호의 종류의 수를 출력해라.

입력 예시 9 8 CCTGGATTG 2 0 1 1

출력 예시 0

코드 예시

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
arr=input()
a,c,g,t=map(int, input().split())
start=0
end=m-1
a1=0
c1=0
g1=0
t1=0
count=0
for i in range(m-1,n):
    if i==m-1:
        for temp in range(0,m):
            if arr[temp]=="A":
                a1+=1
            elif arr[temp]=="C":
                c1+=1
            elif arr[temp]=='G':
                g1+=1
            else :
                t1+=1
    else:
        if arr[i]=="A":
                a1+=1
        elif arr[i]=="C":
                c1+=1
        elif arr[i]=='G':
                g1+=1
        else :
                t1+=1
        if arr[i-m]=="A":
                a1-=1
        elif arr[i-m]=="C":
                c1-=1
        elif arr[i-m]=='G':
                g1-=1
        else :
                t1-=1
    if a1>=a and c1>=c and g1>=g and t1>=t:
        count+=1
print(count)

해당 문제의 핵심은 시간복잡도 O(n) 으로 해결해야 한다는 점이다. p,s가 백만 이기 때문에 생기는 것이다. 즉 sliding window 로 해결하면 된다. 우선 a1,c1,g1,t1 을 초기화 해야 하니 for 문이 처음일 때는 window size 를 돌며 해당 a,c,g,t 의 개수를 세어본다. 그 이외의 반복문에서는 한칸 씩 이동하며 개수를 업데이트 해야되니 새로운 index(i) char 에 대해서는 추가를 해주고 이전 index(i-m)는 삭제를 시켜준다. 마지막에서는 문제의 조건인 최소 필요 a,c,g,t와 같거나 더 큰지 비교를 해서 count를 증가시켜주면 된다.

sliding window 는 크게 어려운 개념은 아니여서 간단하게 풀 수 있었다.

문제 N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다. N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라. 수의 위치가 다르면 값이 같아도 다른 수이다.

입력 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

출력 좋은 수의 개수를 첫 번째 줄에 출력한다.

입력 예시 10 1 2 3 4 5 6 7 8 9 10

출력 예시 8

코드 예시

import sys
input=sys.stdin.readline
n=int(input())
arr=list(map(int,input().split()))
arr.sort()
count=0
for s in range(n):
    i=arr[s]
    start=0
    end=n-1
    while start<end:
        sum=arr[start]+arr[end]
        if sum==i:
            if end==s:
                end-=1
            elif start==s:
                start+=1
            else :
                count+=1
                break
        elif sum>i:
            end-=1
        else:
            start+=1
print(count)

우선 n=2000 이기 때문에 시간복잡도는 O(n^3)을 넘어서는 안된다.

sorting을 먼저 한다. 1 2 3 4 5 6 7 8 9 10 이렇게 있으면 반복문을 2번 돈다.

첫 outer 반복문에서는 find 숫자를 찾는다. 예를 들어 arr[find]=3이라면 start, end를 양 끝으로 두고 arr[start]+arr[end]==find 일때 start!=find 이고 end!=find 일 때만 count를 증가시킨다. 그리고 break (다른 두 수를 더했을 때 find 가 되야 하기 때문이다.) 같은 수가 나왔을 경우에도 index 가 다르면 다른 수로 본다. 이외의 경우에는 투 포인트 문제 처럼 end--, start++ 하면 된다.

핵심: 어차피 좋은 수만 구하면 되기 때문에 같은 숫자들이 반복되도 find는 각 1번만 찾으면 된다. break를 거는 이유!!

c++

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    int A[n];
    for(int i=0;i<n;i++){
        scanf("%d",&A[i]);
    }
    sort(A,A+n);
    int count=0;
    for(int k=0;k<n;k++){
        int find=A[k];
          int i=0;
        int j=n-1;
        while(i<j) {
            if(find==A[i]+A[j]){
                if(i==k)
                i++;
                else if (j==k)
                j--;
                else {count++;break;}
            }
            else if(find>A[i]+A[j])
            i++;
            else j--;
        }
    }
    printf("%d",count);
    return 0;
}

확실히 c++ 이 메모리나 시간적인 측면에서 훨씬 효율적임을 알 수 있다. ![](https://velog.velcdn.com/images/ddoh_k/post/f1cbfff7-acb2-42b5-aa6c-121726f9ff37/image.png)

문제 주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다. 갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오.

입력 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고유한 번호들이 공백을 사이에 두고 주어진다. 고유한 번호는 100,000보다 작거나 같은 자연수이다.

출력 첫째 줄에 갑옷을 만들 수 있는 개수를 출력한다.

입력 예시 6 9 2 7 4 1 5 3

출력 예시 2

코드 예시

import sys
input=sys.stdin.readline
n=int(input())
m=int(input())
arr=list(map(int,input().split()))
i=0
j=n-1
count=0
arr.sort()
while i<j:
    sum=arr[i]+arr[j]
    if sum==m:
        count+=1
        i+=1
        j-=1
    elif sum>m:
        j-=1
    else :
        i+=1
print(count)

해당 문제는 n=15000 이니 시간 복잡도 O(nlogn) 까지 허용한다. 그래서 sorting을 사용해도 된다.

2 7 4 1 5 3 이렇게 input을 1 2 3 4 5 7 로 sorting 한다. 이후 투 포인터인 start, end를 양 끝으로 잡는다.

A[start]+A[end]==m 이면 count++, 후에 start 와 end 둘 다 칸을 이동시킨다.

A[start]+A[end]>m 이면 더한 값이 더 크다는 의미이므로 end-- 를 해서 더한 값을 줄여준다. A[start]+A[end]<m 이면 더한 값이 더 작다는 의미이므로 start++ 해서 더한 값을 키운다.

이러한 행동을 start==end 까지 반복하면 된다.

이렇게 문제를 풀 수 있었던 이유는 배열 원소 중 2개를 선택하기 때문이다.

문제 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다. 예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다. N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.

입력 첫 줄에 정수 N이 주어진다.

출력 입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오

입력 예시 15

출력 예시 4

코드 예시

import sys
input=sys.stdin.readline
n=int(input())
start=1
end=1
count=1
sum=1
while end!=n:
    if sum==n:
        count+=1
        end+=1
        sum+=end
    elif sum > n:
        sum-=start
        start+=1
    else:
        end+=1
        sum+=end
print(count)

start index, end index 두 개의 포인터를 이동하면서 문제를 풀어야 한다.

1,2,3,4,5,6,7,8,..15 의 배열이 있다고 해보자. 1,2,3,4 까지 sum<n 이니 end만 1씩 증가한다.

1,2,3,4,5 에서 sum==n 이니 count++ 하고 end++ 로 end=6이 된다. 그리고 sum+=end 하면 21이 된다.

그러면 sum>n 이니sum-=start 하고 start를 오른쪽으로 한 칸 이동 시켜 2,3,4,5,6 이 되도록 한다.

의외로 헷갈린다?!

이런 투 포인터 문제를 접해보지 않아서 그런지 어려웠다. sum=0 으로 계속 초기화를 통해 앞으로 나아가려 했으나 그러면 시간복잡도가 훨씬 증가할 것으로 보인다.

문제 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

입력 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103) 둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)

출력 첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.

입력 예시 5 3 1 2 3 1 2

출력 예시 7

코드 예시

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
arr=list(map(int,input().split()))
temp_sum=[]
temp_sum.append(arr[0]%m) #temp_sum %m 합 배열
temp=arr[0]
ans=0
c=[0]*m
for i in arr[1:n+1]:
    temp+=i
    temp_sum.append(temp%m)
for i in temp_sum:
    if i==0:
        ans+=1
    c[i]+=1 #같은 mod sum 개수 count 배열
for i in c: 
    if i > 1:
        ans+=(i*(i-1))//2 #nC2, //을 사용하여 정수계산
print(ans)

이 문제는 생각보다 어려웠다. 우선 m 으로 나눈 나머지 합 배열을 가지고 있어야 한다. 1 0 0 1 0 이렇게 temp_sum 이 있으면 0 의 개수 먼저 세보자. 해당 부분까지의 합이 m 으로 나누어 떨어진다는 뜻이기 때문이다.

추가적으로 temp_sum 에서 같은 값들을 2개 골라 nC2 를 계산한다. temp_sum[i]%m==temp_sum[j]%m 이면 (temp_sum[j]-temp_sum[i])%m==0 이기 때문에 해당 A[i+1]~A[j] 인 부분 합 구간이 m 으로 나누어 떨어진다.

'//' 을 사용해서 소수점 나눗셈이 아닌 정수형 나눗셈으로 구한다.