안녕하세요!
모각코-멋쟁이용두리처럼 팀입니다!
11월 29일날 모각코-멋쟁이용두리처럼이 벌써 마지막 회의까지 왔습니다..!
모각코도 이제 끝이여서 너무 아쉽네요 ㅠㅠ,,! 학기가 끝나진 않았으니 우리 모두 계속해서 정진해봅시다..!
모각코가 아니여도 꾸준히 화이팅..^ㅠ^
이번 시간에는 각자 공부한 내용정리와 알고리즘 문제풀이를 가져왔습니다!
마지막 시간의 내용은 웹스크래핑을 통한 정보추출 코드와 알고리줌 풀이, 그리고 디자인패턴에 대한 CS정리에 대해 알아보러 가볼까요~? ^__^
김xx
"저는 requests와 bs4를 사용한 웹 스크래핑을 통해 최신 IT뉴스, 오늘의 영어회화, 최신 해외축구 뉴스를 추출하는 프로그램을 짜봤습니다!"
노xx
"면접 준비 겸 공부를 위해 이번에도 CS 부분을 기록해보았습니다. 이번주는 디자인 패턴을 주제로 공부했습니다!"
최xx
"저는 코딩테스트 대비를 위해 프로그래머스에 문제를 푸는 시간을 가졌습니다! 그 중 몇 문제를 추려볼게요!"
김x연
"DFS/BFS와 DP의 약점을 계속적으로 공부하기 위해 집중적으로 DFS/BFS와 DP문제를 백준을 통해 풀어봤습니다!"
✏️ PART6. 웹 스크래핑
# Project ) 웹 스크래핑을 이용하여 IT뉴스와 오늘의 영어 회화, 최신 해외축구 뉴스를 가져와보자.
import re
import requests
from bs4 import BeautifulSoup
def create_soup(url):
headers = {
"User-Agent": "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/87.0.4280.141 Safari/537.36"}
res = requests.get(url, headers=headers)
res.raise_for_status()
soup = BeautifulSoup(res.text, "lxml")
return soup
def print_news(index, title, link):
print("{}. {}".format(index+1, title))
print(" (링크 : {})".format(link))
def scrape_it_news():
print("[IT 뉴스]")
url = "https://news.naver.com/main/list.nhn?mode=LS2D&mid=shm&sid1=105&sid2=230"
soup = create_soup(url)
news_list = soup.find("ul", attrs={"class": "type06_headline"}).find_all(
"li", limit=3) # 3개 까지 가져오기
for index, news in enumerate(news_list):
a_idx = 0
img = news.find("img")
if img:
a_idx = 1 # img 태그가 있으면 1번째 a 태그의 정보를 사용(기사 링크)
a_tag = news.find_all("a")[a_idx]
title = a_tag.get_text().strip()
link = a_tag["href"]
print_news(index, title, link)
def scrape_todaty_english():
print("[오늘의 영어 회화]")
url = "https://www.hackers.co.kr/?c=s_eng/eng_contents/I_others_english#;"
soup = create_soup(url)
sentences = soup.find_all("div", attrs={"id": re.compile("^conv_kor_t")})
todaysExpression = soup.find_all("b", attrs={"class": "conv_txtTitle"})
print()
print("(영어 지문)")
# 8문장이 있다고 가정할 때, index 기준 4~7까지 잘라서 가져오면 된다.
print("<Today's expression>")
print(todaysExpression[1].get_text())
print()
for sentence in sentences[len(sentences)//2:]:
print(sentence.get_text().strip())
# 8문장이 있다고 가정할 때, index 기준 0~3까지 잘라서 가져오면 된다.
print()
print("(한글 지문)")
print("<오늘의 표현>")
print(todaysExpression[0].get_text())
print()
for sentence in sentences[:len(sentences)//2]:
print(sentence.get_text().strip())
print()
def scrape_football_news():
print("[오늘의 해외축구 뉴스]")
print()
url = "https://sports.news.naver.com/wfootball/index.nhn"
soup = create_soup(url)
news_list = soup.find("ul", attrs={"class": "home_news_list"}).find_all(
"li") # 3개 까지 가져오기
news_list += soup.find("ul", attrs={"class": "home_news_list division"}).find_all(
"li") # 3개 까지 가져오기
for index, news in enumerate(news_list):
a_idx = 0
img = news.find("img")
if img:
a_idx = 1 # img 태그가 있으면 1번째 a 태그의 정보를 사용(기사 링크)
a_tag = news.find_all("a")[a_idx]
title = a_tag.get_text().strip()
link = "https://sports.news.naver.com"+a_tag["href"]
print_news(index, title, link)
if __name__ == "__main__":
scrape_it_news() # IT 뉴스 정보 가져오기
scrape_todaty_english() # 오늘의 영어 회화 가져오기
scrape_football_news() # 해외축구 최신뉴스 가져오기[IT 뉴스 정보 가져오기]
[오늘의 영어회화 정보 가져오기]
[오늘의 해외축구 뉴스 정보 가져오기]
웹 스크래핑을 통해서 매일 업데이트 되는 IT뉴스와 오늘의 영어회화 그리고 해외축구 뉴스를 얻을 수 있게 됐습니다!
beautifulsoup 라이브러리와 lxml 라이브러리, requests 라이브러리는 pip install을 통해 설치해주셔야 합니다!
정보를 끌어오시고 싶은 웹페이지의 DevTools를 킨 후, 적절한 값을 찾아주시면 원하시는 정보를 얻을 수 있을 거에요!
다음은 CS 부분에 대해 살펴볼까요~?
✏️ 디자인패턴 CS정리
디자인 패턴은 프로그램을 설계할 때 발생했던 문제점들을 객체 간의 상호 관계 등을 이용해 해결할 수 있도록 하나의 규약 형태로 만들어 놓은 것이다.
- 싱글톤 패턴 (Single Pattern)
하나의 클래스에 오직 하나의 인스턴스만 가지는 패턴으로, 데이터베이스 연결 모듈에 많이 사용한다. 하나의 인스턴스 를 생성하고 해당 인스턴스를 다른 모듈들이 공유하며 사용하므로 인스턴스를 생성하는 비용을 줄일 수 있는 장점이 있 지만 의존성이 높아진다는 단점이 있다.
- 팩토리 패턴 (Factory Pattern)
객체를 사용하는 코드에서 객체 생성 부분을 떼어내 추상화한 패턴으로, 상속 관계에 있는 두 클래스에서 상위 클래스 가 중요한 뼈대를 결정하고 하위 클래스에서 객체 생성에 관한 구체적인 내용을 결정하는 패턴이다.
상위 클래스와 하위 클래스가 분리되므로 느슨한 결합을 가지고 상위 클래스는 인스턴스 생성 방식에 대해 알 필요가 없으므로 더 많은 유연성을 가지고 리팩토링 시 한 곳만 고치며 유지 보수성이 증가하는 장점이 있다,
- 전략 패턴 (Strategy Pattern)
객체의 행위를 바꾸고 싶은 경우 직접 수정하지 않고 전략이라 부르는 '캡슐화한 알고리즘'을 컨텍스트 안에서 바꿔주며 상호 교체가 가능하게 만드는 패턴이다.
- 옵저버 패턴 (Observer Pattern)
주체가 어떤 객체의 상태 변화를 관찰하다가 상태 변화가 있을 때마다 메서드를 통해 옵저버 목록에 있는 옵저버들에게 변화를 알리는 패턴이다. 옵저버는 객체의 상태 변화에 따라 전달되는 메서드 등을 기반으로 변화 사항이 생기는 객체 들을 의미한다.
- 프록시 패턴 (Proxy Pattern)
대상 객체에 접근하기 전 그 접근에 대한 흐름을 가로채 대상 객체 앞단의 인터페이스 역할을 하는 패턴이다. 이는 객체 의 속성, 변환 등을 보완하여 보안, 데이터 검증, 캐싱, 로깅에 사용하고 프록시 서버로도 사용된다.
프록시 서버는 서버와 클라이언트 사이에서 클라이언트가 자신을 통해 다른 네트워크 서비스에 간접적으로 접속할 수 있게 해주는 컴퓨터 시스템, 프로그램을 의미한다.
- 이터레이터 패턴 (Iterator Pattern)
이터레이터를 사용하여 컬렉션의 요소들에 접근하는 디자인 패턴이다. 이를 통해 순회할 수 있는 여러 가지 자료형의 구조와는 상관없이 이터레이터라는 하나의 인터페이스로 순회가 가능하다는 장점이 있다.
- 노출모듈 패턴 (Revealing Module Pattern)
즉시 실행 함수를 통해 접근 제어자를 만드는 패턴으로, 자바스크립트와 같이 접근 제어자가 없어 전역 범위에서 스크립트가 실행되어 노출모듈 패턴을 통해 private와 public 과 같은 접근 제어자를 구현한다.
- MVC 패턴
모델 (Model), 뷰 (View), 컨트롤러 (Controller)로 이루어진 디자인 패턴으로, 애플리케이션의 구성 요소를 3가지 역할로 구분하여 개발 프로세스에서 각각의 구성 요소에만 집중해 개발이 가능하여 재사용성과 확장성이 용이하다는 장점이 있 다. 하지만 애플리케이션이 복잡해질수록 모델과 뷰의 관계가 복잡해진다는 단점이 있다.
- 모델: 애플리케이션의 데이터인 데이터베이스, 상수, 변수 등을 의미한다.
- 뷰: input box, text area와 같은 사용자 인터페이스 요소를 의미한다. 그리고 변경이 일어나면 컨트롤러에 전달한다.
- 컨트롤러: 모델과 뷰를 잇는 다리 역할로, 메인 로직을 담당한다.
MVC 패턴
- MVP 패턴
MVC 패턴으로부터 파생되었으며 C에 해당하는 컨트롤러가 프레젠터 (Presenter)로 교체된 페턴이다. 뷰와 프레젠터가 1대1 관계이므로 MVC 패턴보다 더 강한 결합을 지닌 패턴이다. 하지만 애플리케이션이 복잡해질수록 뷰와 프레젠터 사이의 의존성이 강해지는 단점이 있다.
MVP 패턴
- MVVM 패턴
MVC에 C에 해당하는 컨트롤러가 뷰모델 (View Model)로 바뀐 패턴이다. 뷰모델은 뷰를 더 추상화한 계층으로 MVC패 턴과는 다르게 커맨드와 데이터 바인딩을 가지는 것이 특징이다. 뷰와 뷰모델 사이의 양방향 데이터 바인딩을 지원하며 UI를 별도의 코드 수정 없이 재사용할 수 있고 단위 테스팅을 하기 쉽다는 장점이 있다. 하지만 설계가 어렵다는 단점이 있다.
MVVM 패턴
* 데이터 바인딩: 화면에 보이는 데이터와 웹 브라우저의 메모리 데이터를 일치시키는 기법
다음은 알고리즘 풀이를 살펴봅시다~!
✏️코테 준비 프로그래머스&&백준 풀기
1. 주식가격 ( Level 2)
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
########### Brute Froce ###########
def solution(prices):
answer = []
for i in range(0,len(prices)):
ans = 0
for j in range(i+1,len(prices)):
if prices[j]<prices[i]:
ans+=1
break
else:
ans+=1
answer.append(ans)
return answer
########### Stack ###########
def solution(prices):
answer = [0]*len(prices)
stack = [0]
for i in range(1,len(prices)):
if prices[i] > prices[i-1]:
stack.append(i)
else:
while(len(stack)>0 and prices[i] < prices[stack[-1]]):
idx = stack.pop()
answer[idx] = i-idx
stack.append(i)
for i in stack:
answer[i] = len(prices)-(i+1)
return answer- stack을 이용한 brute force 알고리즘입니다!
2. 주차 요금 계산 ( Level 2)
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
import math
def solution(fees, records):
answer = []
time_record = {}
fee_record = {}
for i in records:
time,car,status = map(str,i.split())
minute = 60*int(time[:2])+int(time[3:])
if status == "IN":
if car in time_record:
time_record[car][0] += minute
time_record[car][2] +=1
else:
time_record[car] = [minute,0,1,0] ## 입차,출차,입차횟수,출차횟수
elif status =="OUT":
time_record[car][1] += minute
time_record[car][3] +=1
for car,record in time_record.items():
if record[3] != record[2]:
result = (60*23 + 59 + record[1]) -record[0]
else:
result = record[1]-record[0]
if result <=fees[0]:
fee_record[car] = fee_record.get(car,0) + fees[1]
else:
fee_record[car] = fee_record.get(car,0) + fees[1] + math.ceil((result-fees[0])/fees[2]) * fees[3]
fee_record = sorted(fee_record.items(), key = lambda x: x[0])
for i in fee_record:
answer.append(i[1])
return answer- 문자열을 이용한 구현 문제입니다! 저번 시간에도 언급했듯이 구현은 코딩테스트의 필수 문제입니다. 포기하지 마시고 차근차근 코드를 이어나가세요!
3. DFS와 BFS
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
풀이
# 입력 변수 받기
N, M, V = map(int, input().split())
# 인접 영행렬 생성
matrix=[[0] * (N + 1) for i in range(N + 1)]
# 방문한 곳 체크를 위한 배열 선언
visited = [0] * (N + 1)
# 입력 받는 두 값에 대해 영행렬에 1 삽입
for i in range(M):
a, b = map(int, input().split())
matrix[a][b] = matrix[b][a] = 1
def dfs(V):
# 방문한 곳은 1 넣기
visited[V] = 1
print(V, end=' ')
# 재귀 함수 선언(V와 인접한 곳을 찾고 방문하지 않았다면 함수 실행)
for i in range(1,N+1):
if(visited[i]==0 and matrix[V][i]==1):
dfs(i)
def bfs(V):
# 방문해야 할 곳을 순서대로 넣을 큐
queue = [V]
# dfs 를 완료한 visited 배열(1로 되어있음)에서 0으로 방문체크
visited[V] = 0
# 큐 안에 데이터가 없을 때 까지
while queue:
V = queue.pop(0)
print(V, end=' ')
for i in range(1, N + 1):
if(visited[i] == 1 and matrix[V][i] == 1):
queue.append(i)
visited[i] = 0
dfs(V)
print()
bfs(V)
4. 전쟁 - 전투
1303번: 전쟁 - 전투
첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는
www.acmicpc.net
문제
전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다. 그러나 당신의 병사들은 흰색 옷을 입고, 적국의 병사들은 파란색 옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다. 문제는 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다.
N명이 뭉쳐있을 때는 N2의 위력을 낼 수 있다. 과연 지금 난전의 상황에서는 누가 승리할 것인가? 단, 같은 팀의 병사들이 대각선으로만 인접한 경우는 뭉쳐 있다고 보지 않는다.
입력
첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 병사가 한 명 있다. B는 파란색, W는 흰색이다. 당신의 병사와 적국의 병사는 한 명 이상 존재한다.
출력
첫 번째 줄에 당신의 병사의 위력의 합과 적국의 병사의 위력의 합을 출력한다.
풀이
방문 기록이 없고 현재 값이 W인 값 혹은 방문기록이 없고 현재 값이 B인 값을 함수로 넣어준다.
color별로 cnt를 증가시킨다.
return cnt+1 한 값에 제곱해주고 색깔별로 누적시킨다.
def bfs(x, y, color):
cnt = 0
queue = deque()
queue.append((x, y))
visited[x][y] = True
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < m and 0 <= ny < n:
if graph[nx][ny] == color and not visited[nx][ny]: # each color check
visited[nx][ny] = True
queue.append((nx, ny))
cnt += 1 # each color count
return cnt + 1
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
n, m = map(int, input().split())
graph = [list(input()) for _ in range(m)]
visited = [[False] * n for i in range(m)]
white, blue = 0, 0
for i in range(m):
for j in range(n):
if graph[i][j] == 'W' and not visited[i][j]:
white += bfs(i, j, 'W') ** 2 # count accumulate
elif graph[i][j] == 'B' and not visited[i][j] :
blue += bfs(i, j, 'B') ** 2 # count accumulate
print(white, blue)
5. 음식물 피하기
1743번: 음식물 피하기
첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다
www.acmicpc.net
문제
코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다.
이 문제를 출제한 선생님은 개인적으로 이러한 음식물을 실내화에 묻히는 것을 정말 진정으로 싫어한다. 참고로 우리가 구해야 할 답은 이 문제를 낸 조교를 맞추는 것이 아니다.
통로에 떨어진 음식물을 피해가기란 쉬운 일이 아니다. 따라서 선생님은 떨어진 음식물 중에 제일 큰 음식물만은 피해 가려고 한다.
선생님을 도와 제일 큰 음식물의 크기를 구해서 “10ra"를 외치지 않게 도와주자.
입력
첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다.
좌표 (r, c)의 r은 위에서부터, c는 왼쪽에서부터가 기준이다. 입력으로 주어지는 좌표는 중복되지 않는다.
출력
첫째 줄에 음식물 중 가장 큰 음식물의 크기를 출력하라.
풀이
from collections import deque
input = sys.stdin.readline
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
def bfs(i, j, trash):
q = deque([[i, j]])
trash[i][j] = 2 # visited
result = 1
while q:
x, y = q.popleft()
for d in range(4):
nx, ny = x + dx[d], y + dy[d]
if 0 < nx <= n and 0 < ny <= m and trash[nx][ny] == 1:
q.append([nx, ny])
trash[nx][ny] = 2
result += 1
return result
n, m, k = map(int, input().split())
trash = [[0] * (m + 1) for _ in range(n + 1)]
answer = 0
for _ in range(k):
x, y = map(int, input().split())
trash[x][y] = 1
for i in range(1, n + 1):
for j in range(1, m + 1):
if trash[i][j] == 1:
ans = bfs(i, j, trash)
answer = max(ans, answer)
print(answer)
6. 퇴사2
15486번: 퇴사 2
첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000)
www.acmicpc.net
문제
상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.
오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.
백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.
각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.
N = 7인 경우에 다음과 같은 상담 일정표를 보자.
1일2일3일4일5일6일7일
| Ti | 3 | 5 | 1 | 1 | 2 | 4 | 2 |
| Pi | 10 | 20 | 10 | 20 | 15 | 40 | 200 |
1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.
상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.
또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.
퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.
상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다.
둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000)
출력
첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.
풀이
각각의 날들을 '그날 상담을 시작하는 경우'와 '그날 상담을 시작하지 않는 경우'로 나눌 수 있다
만약 1일이라면 T = 3인 일을 시작할 수도 있고, 시작하지 않을 수도 있는 것이다
상담을 시작한다면, 상담이 끝난 다음 날의 수익이 P[i]만큼 증가한다
n = 1이면 n = 4일 때의 수익이 10이 되는 것이다
상담을 시작하지 않는다면
n에 +1을 해줘서 다음 날로 넘어간다
n+1번째 날에도 동일한 처리를 반복해 나간다
M은 이전에 저장된 M의 값과 dp[i]중 큰 것으로 갱신한다
dp[i]는 '현재까지의 수익에 이번 상담의 수익을 더한 값'과 '오늘의 상담이 끝나는 시점의 수익' 중 큰 값을 저장한다.
n = int(input())
t,p = [],[]
dp = [0] * (n+1)
for i in range(n):
x,y = map(int,input().split())
t.append(x)
p.append(y)
M = 0
for i in range(n):
M = max(M,dp[i])
if i+t[i] > n :
continue
dp[i+t[i]] = max(M+p[i],dp[i+t[i]])
print(max(dp))
7. 점프
1890번: 점프
첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장
www.acmicpc.net
문제
N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.
각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다.
가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다.
출력
가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수는 2^63-1보다 작거나 같다.
풀이
n=int(input())
a=[list(map(int,input().split())) for i in range(n)]
dp=[[0]*n for i in range(n)] # 방문 횟수
dp[0][0]=1
for i in range(n):
for j in range(n):
if i == n-1 and j == n-1:
break
d=i+a[i][j] # 아래쪽
r=j+a[i][j] # 오른쪽
if d < n:
dp[d][j] += dp[i][j]
if r < n:
dp[i][r] += dp[i][j]
print(dp[n-1][n-1])👊 코드리뷰 & 향후일정 👊
- 이로써 모여서 각자 코딩, 일명 모각코의 활동이 마무리 됐습니다!
- 처음으로 시행되는 모각코 활동을 취준생4명이 한 학기동안 진행해봤는데요,, 정말 뜻깊은 시간이었던 것 같습니다!.
- 누구나 취업준비생이 될 터인데, 조급해하지말고 자신이 하고자 하는 것을 계속 한다면, 분명 꼭 성장하는 자신을 발견하실 수 있으실 겁니다!
- 초조해하지말고 차근차근 밟아나갑시다! 모두들 화이팅!!!
앞으로도, 취준생 4명의 취뽀를 응원해주세요!
한 학기 동안 이상 모각코-멋쟁이용두리처럼 였습니다! 감사합니다!
'2022_모각코' 카테고리의 다른 글
| [2022년 11월 22일 멋쟁이용두리처럼 5번째 회의] (0) | 2022.11.30 |
|---|---|
| [2022년 11월 08일 멋쟁이용두리처럼 4번째 회의] (0) | 2022.11.30 |
| [2022년 10월 19일 멋쟁이용두리처럼 3번째 회의] (2) | 2022.11.11 |
| [2022년 10월 14일 멋쟁이용두리처럼 2번째 회의] (2) | 2022.10.28 |
| [2022년 9월 28일 멋쟁이용두리처럼 1번째 회의] (0) | 2022.10.03 |