문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K무게까지의 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

예제 입력 1

4 7

6 13

4 8

3 6

5 12

예제 출력 1

14

knapsack probelm / 동적 프로그래밍 문제

물품 수 N, 배남 담을 수 있는 무게 K

동적 프로그래밍을 이용하여 시간복잡도 O(NK)로 문제 해결할 수 있음

모든 무게에 대하여 최대 가치를 저장

D[i][j] = "배낭에 넣은 물품 무게 합이 j일때 얻을 수 있는 최대 가치"

각 물품 번호 i에 따라서 최대 가치 D[i][j] 를 갱신하여 문제 해결

D[i][j] = 1. D[i-1][j]                                                                  //if j < W[i]

                2. max(D[i-1][j], D[i-1][j-W[i]] + V[i])               //if j >= W[i]

n,k = map(int, input().split())
dp = [[0]*(k+1) for _ in range(n+1)]
for i in range(1, n+1):
    w, v = map(int, input().split()) #w = weight / v = value
    for j in range(1, k+1):
        if j < w:
            dp[i][j] = dp[i-1][j] #작을 때는 위의 값과 동일 값 삽입
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v) #위의 값과 이전 값의 최대 가치에 이전 값을 더해 삽입
print(dp[n][k])
    

문제

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

입력

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

출력

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

예제 입력 1 복사

10 5 2 3 1 4 2 3 5 1 7

예제 출력 1 복사

1 1 2 2 3 3 4 5 5 7

import sys

n = int(sys.stdin.readline())
array = [0] * 10001

for i in range(n):
	data = int(sys.stdin.readline())
    array[data] += 1

for i in range(10001):
	if array[i] != 0:
    	for j in range(array[i]):
        	print(i)

좌표 정렬하기

문제

2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

출력

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

알고리즘

N = int(input())
dot = []

for _ in range(N):
    x, y = map(int, input().split(" "))
    dot.append((x,y))
    
dot_sort = sorted(dot, key=lambda x : (x[0], x[1]))

for x,y in dot_sort:
    print(x,y)

1. 정렬이란?

• 어떤 데이터들이 주어졌을 때, 정해진 순서대로 나열하는 것
• 다양한 정렬 알고리즘 이해를 통해 동일한 문제에 대한 다양한 알고리즘이 고안될 수 있고, 각 알고리즘 간 성능 비교를 통해 알고리즘 성능 분석도 이해할 수 있음

2. 버블 정렬(bubble sort)

• 두 인접한 데이터를 비교하여 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘

## https://visualgo.net/en 사이트에서 보면 쉽게 그림으로 이해할 수 있다. 

3. 패턴 찾기

• 데이터가 4개 일 때 
  • data_list = [1,9.3.2]
    • 1차 로직
      • 1 vs 9 => X
      • 9 vs 3 => [1, 3, 9, 2]
      • 9 vs 2 => [1, 3, 2, 9]
    • 2차 로직
      • 1 vs 3 => X
      • 3 vs 2 => [1, 2, 3, 9]
      • 3 vs 9 => X
    • 3차 로직
      • 1 vs 2 => X
      • 2 vs 3 => X
      • 3 vs 9 => X

==> N 개의 리스트가 있는 경우 N-1 로직을 적용한다

==> 로직을 1번 적용할 때마다, 가장 큰 수가 뒤에서부터 1개씩 결정된다 

==> 로직이 일찍 끝날 수도 있다 

        => 로직을 적용 시,  한 번도 데이터가 교환되지 않는다면 이미 정렬된 상태므로 더 이상 로직을 반복 적용할

             필요가 없다 

==> 로직 한 회 끝날 때 마다 가장 큰 숫자가 뒤에서 1개씩 결정된다

4. 알고리즘

<프로토 타입>
1. for num in range(len(data_list)) 반복
2. swap = false // 교환되어있는지 확인,  false 가 기본값이여야 아래 for문에서 swap 이 멈춰야 알고리즘 종료
3. 반복문 안에서 , for index in range(len(data_list) - num - 1) 를 n-1번 반복해야한다 
    //num 을 빼는 이유는  data_list에서 로직이 돌면 맨 뒤에 가장 큰 값이 고정되기 때문에 
4. 반복문안의 반복문 안에서, if data_list[index] > data_list[index + 1]  이면
5. swap 시켜야한다
6. 더이상 swap 되지 않고 false 값이 나오면 break

def bubblesort(data):
    for index in range(len(data) - 1):
        swap = False
        for index2 in range(len(data) - index - 1):
            if data[index2] > data[index2 + 1]:
                data[index2], data[index2 + 1] = data[index2 + 1], data[index2]
                swap = True
        
        if swap == False:
            break
    return data

import random

data_list = random.sample(range(50), 20)
bubblesort(data_list)

>>[3, 5, 10, 11, 18, 19, 20, 21, 24, 26, 28, 29, 31, 33, 34, 38, 39, 44, 46, 49]

5. 분석

• 반복문이 두개  :  O(𝑛2)
  • 최악 : 𝑛∗(𝑛−1)2
• 완전 정렬 되어 있으면 최선 : O(n)

# python은 간결해서 컴퓨터 과학의 기초와 문제 해결에 집중할 수 있다.

#웹 사이트들 언어 수요

#분야별 자주 사용하는 언어

• 데이터 과학, 공학 => Python, R, MATLAB
• 웹 프런트엔드 => HTML/CSS + JavaScript
• 웹 백엔드 (서버) => Python, Ruby, JavaScript, Java, Go, C, C++, PHP 등
• 아이폰 어플 => Objective-C, Swift (거의 Swift로)
• 안드로이드 어플 => Java, Kotlin (Kotlin으로)
• 게임 개발 => C#, C++
• 임베디드 시스템 => C, C++

1. python 설치

• 파이썬 사이트

 -> Python 3 설치 -> python-3.7.2.exe 다운로드 -> Add Python 3.7 to PATH 체크박스 체크

 -> 계속 동의 

2. PyCharm 설치하기 

•  JetBrains 사이트

->PyCharm 다운로드 -> Community용 다운로드 -> pycharm-community-2019.1.exe

3. pycharm 사용하기

• create new project