알고리즘
그리디 알고리즘
탐욕적인 탐색
검토 사항 : 가장 탐욕적인 탐색 방법이 배수의 조건에 해당 되거나 (가장 먼저 우선시 해야 하는 조건에 해당되거나) 탐욕적인 선택만으로 답을 구할 수 있을 것이라 판단될 때 사용함
거스름 돈 문제
- 배수의 조건에 해당 되기 때문에 그리디 알고리즘이 통했던 문제
문제
당신은 음식점의 계산을 도와주는 점원이다.
카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다.
손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 N은 항상 10의 배수이다.풀이
def solution(n):
count = 0
coin_t = [500, 100, 50, 10]
for coin in coin_t:
count += n // coin
n %= coin
return count큰 수의 법칙 문제
- 가장 큰 수와 두번째로 큰 수 만으로 해결되었던 문제
문제
다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번을 더하여 가장 큰 수를 만드는 법칙.
단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없음.
예1) 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정. 이 경우 특정한 인덱스의 수가 연속해서 3번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6+6+6+5+6+6+6+5인 46
단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주.
예2) 순서대로 3, 4, 3, 4, 3으로 이루어진 배열이 있을 때 M이 7이고, K가 2라고 간주. 이 경우 두 번째 원소에 해당하는 4와 네 번째 원소에 해당하는 4를 번갈아 두 번씩 더하는 것이 가능. 결과적으로 4+4+4+4+4+4+4인 28
배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 동빈이의 큰 수의 법칙에 따른 결과를 출력하시오.
입력 조건
첫째 줄에 N(2≤N≤1000), M(1≤M≤10000), K(1≤K≤10000)의 자연수가 주어지며, 각 자연수는 공백으로 구분.
둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분. 단, 각각의 자연수는 1 이상 10000 이하의 수로 주어진다.
입력으로 주어지는 K는 항상 M보다 작거나 같다.
출력 조건
첫째 줄에 동빈이의 큰 수의 법칙에 따라 더해진 답을 출력한다.풀이
N, M, K = map(int, input().split())
arr = list(map(int, input().split()))
arr = sorted(arr, reverse=True)
answer=0; succ=0; pt=0;
for i in range(M):
if succ >= K:
succ = 0
pt += 1
elif pt > 0:
pt -= 1
# print(f"PT : {pt}")
answer += arr[pt]
succ += 1
print(answer)두 큐 합 같게 만들기 (출처 : 프로그래머스)
- 슬라이딩 윈도우 방식으로 풀었어야 했던 문제
First Attempt
Idea
- 각자의 큐에서 last input을 빼옴
- 빼온 값을 기존의 sum에 더했을 때 해당 값이 half 이상이라면 빼오는 것을 멈춤
- 그 후 본인의 queue에 append를 함
- sum을 다시 계산한 후 작은 queue에도 반복Problem
- big과 small의 요소를 옮기는 순서와 방법에서 비효율성을 나타냈기 때문에 실패를 한 것 같음으로 판단함def solution(queue1, queue2):
answer = 0
sum_1 = sum(queue1)
sum_2 = sum(queue2)
half = (sum_1 + sum_2) // 2
small = 0
big = 0
if sum_1 < sum_2:
small = queue1
big = queue2
else:
small = queue2
big = queue1
# small 리스트 먼저 함
i = 0
left = half - sum(small)
while i < len(big):
if left <= 0:
break
left -= big[i]
small.append(big[i])
i += 1
answer += 1
big = big[i:]
# print(big)
left_b = half - sum(big)
j = 0
while j < len(small):
if left_b <= 0:
break
left_b -= small[j]
big.append(small[j])
j += 1
answer += 1
small = small[j:]
# print(small)
if sum(small) != half or sum(big) != half:
return -1
return answerFinal
from collections import deque
def solution(queue1, queue2):
answer = 0
sum1 = sum(queue1)
sum2 = sum(queue2)
half = (sum1 + sum2) // 2
queue1 = deque(queue1)
queue2 = deque(queue2)
c_sum = sum1
c_queue = queue1 + queue2
left = 0; right = len(queue1); n = len(c_queue)
while left < n and right < n:
if c_sum == half:
return answer
elif c_sum < half:
c_sum += c_queue[right]
right += 1
else:
c_sum -= c_queue[left]
left += 1
answer += 1
return -1Django project Directory 구조
Django-prj/ # 가장 최상단 프로젝트 디렉터리
├── articles/ # 앱 디렉터리
│ ├── __pycache__/
│ ├── migrations/
│ ├── templates/ # 앱 내부의 templates
│ ├── __init__.py
│ ├── admin.py
│ ├── apps.py
│ ├── models.py
│ ├── tests.py
│ └── views.py
├── myapp/ # 가장 앞단의 앱
│ ├── __pycache__/
│ ├── __init__.py
│ ├── asgi.py
│ ├── settings.py # 해당 py파일에서 앱 등록, templates 디렉터리 등록을 관할
│ ├── urls.py # url mapping을 담당
│ └── wsgi.py
├── templates/
│ └── base.html
├── venv/
├── db.sqlite3
├── Dockerfile
├── manage.py
└── requirements.txtfor 태그 동작 방식
{% for one in arr %}
{% endfor %}form 태그 동작 방식
<label for="message"> 메시지 입력 </label>
# id는 위의 label의 for과 바인딩 되는 것임
# name을 명시해야 url 퀴리문에 제대로 message가 전달되는 것임
<input type="text" id="message" name="message">HTTP - GET
- 특정한 자원을 조회하는 데 사용
- 데이터를 서버로 전송할 때 쿼리스트링을 사용해서 전송 (== URL에 데이터가 포함되어 전송됨)
- 쿼리스트링 : 데이터를 URL 주소에 포함시켜 전송하는 방식
- ? 뒤에 데이터가 위치, &로 연결된 key=value 형태로 구성됨
CS 특강
Server는
- 클라이언트로부터 요청을 받아서 처리를 시작하고, 서비스를 제공함
- 요청은 필수 조건
네트워크
- 모든 서버는 네트워크를 통해 서비스(데이터)를 제공
네트워크 7계층
레이어 7 : 애플리케이션층사용자에게 애플리케이션을 제공함
레이어 6 : 프레젠테이션층애플리케이션 데이터를 통신 가능한 방식으로 변환함
레이어 5 : 세션층이론적인 통신로(세션)를 관리함
레이어 4 : 트랜스포트층애플리케이션 식별과 그에 대한 통신 제어를 수행함
레이어 3 : 네트워크 층_다른 네트워크에 있는 컴퓨터와 연결을 수행함
레이어 2 : 데이터링크층
레이어 1 : 물리층
IP : 인터넷에 연결되어 있는 모든 장치들을 식별할 수 있도록 각각의 장비에게 부여되는 고유 주소, 전세계로 택배(데이터)를 보낼 수 있는 택배 주소
IP 주소는 컴퓨터의 집주소, 포트는 각 집 안에서 각 어플리케이션 방 문 번호
