본문 바로가기

전체 글

 (176)
[백준] 11501 주식 / 그리디 / python 실2 (개발자 강화/코딩 테스트) 2024. 12. 1. 16:04 https://www.acmicpc.net/problem/11501 역순으로 풀면 풀리는 문제 처음에는 정순으로 푸려고 했다 오늘 가격보다 내일 가격 작으면현재 구매했던 티켓을 다 팔아버리기 오늘 가격보다 내일 가격이 크거나 같으면한장 사기 근데 생각해보니내일 작다고 당장 팔아버리는 것보다그 다음에 더 큰 값이 나왔을 때 존버하고 파는 게 나은건가?그런 생각이 들긴 했다 처음에 구현했던t = int(input())for i in range(t): n = int(input()) a = list(map(int,input().split())) #3 #10 7 6 #감소수열은 아무것도 안사고, 안파는게 맞음 #3 #3 5 9 #증가 수열은 하루에 하나씩 사고, 마지막날..
[백준] 2668 숫자고르기 / dfs / python 골5 (개발자 강화/코딩 테스트) 2024. 11. 30. 23:14 첫째 줄 숫자를 노드로둘째 줄 숫자를 노드와 연결된 숫자로 생각하면그래프 간선이라고 생각할 수 있다 입력받을 때 방향성 그래프 형태로 구성한다 뽑힌 숫자들이 이루는 집합, 숫자들이 가리키는 숫자들이 이루는 집합이 두 개가 동일하려면 집합 내 숫자들은 사이클을 형성해야 한다최대 사이클을 찾는 문제로 해석할 수 있다 그래프를 돌면서 현재 원소를 방문한 적이 없으면 dfs함수를 돌린다해당 원소가 시작점이 되기 때문에, 해당 원소와 빈 배열을 dfs 함수로 넘겨준다 dfs 함수만약 현재 node가 이미 방문된 경우현재까지 누적된 경로에 node값이 존재한다면 사이클임path에서 사이클에 해당하는 부분을 잘라 result 집합에 추가한다 현재 node를 방문 처리한다현재 node를 path에 추가한다현재 node..
[백준] 2304 창고 다각형 / Python 실2 (개발자 강화/코딩 테스트) 2024. 11. 29. 23:49 https://www.acmicpc.net/problem/2304 가장 높은 기둥을 기준으로 좌 우로 나눔 왼쪽0부터 시작해서 가장 높은 기둥의 index까지우선 height는 가장 첫 번째 기둥 높이로 초기화한다 결과값에 height*(다음 기둥 위치-현재 기둥 위치)를 더해서 면적을 업데이트한다만약 현재 기둥보다 다음 기둥이 높은 경우에는 height값을 다음 기둥 높이로 업데이트한다 오른쪽은이 과정을 끝에서부터 가장 높은 기둥의 index까지 역순으로 진행한다height는 가장 마지막 기둥 높이로 초기화 한다결과값에 height*(현재 기둥 위치-이전 기둥 위치)를 더한다마찬가지로 현재까지 탐색한 기둥 중 가장 높은 기둥을 height에 업데이트 해야 한다 굿! https://velog.io/@ho..

티스토리툴바