본문 바로가기

전체 글

 (171)
[백준] 24037 문자열게임2 / 구현 / python 골5 (개발자 강화/코딩 테스트) 2024. 12. 2. 12:23 보자마자 슬라이딩 윈도우라는 생각 https://www.acmicpc.net/submit/20437 처음에는 '20922_겹치는 건 싫어'의 풀이를 응용해보려고 했다이 풀이는 어떤 문자를 k개 이하로 포함하는 가장 긴 부분 수열을 구하는 문제 그래서 이걸 응용해서 어떤 문자를 정확히 k개 포함하는 가장 짧은 부분 수열을 구하는 것까지는 괜찮았다근데 어떤 문자를 k개 포함하면서, 처음과 끝이 그 문자로 이뤄진 수열을 구하는 부분에서 좀 오차가 있었다 from collections import defaultdictt = int(input())for i in range(t): a = list(map(str, input().strip())) k = int(input()) n = len(a) ..
[백준] 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..

티스토리툴바