본문 바로가기

전체 글277

[BOJ] 치킨 배달 (G5, 15686) - 잃어버린 3시간 https://www.acmicpc.net/problem/15686 다 해놓고 얼탱이 없는 미스로 3시간을 날렸다. dfs 돌릴 때 돌아갈 다음 칸을 잘못 설정하였다... 얼탱이 없는 오타...dfs(pick_num + 1, i + 1) 해야 한다는걸 dfs(pick_num+1, cur_pos+1) 해버림....그 외에는 G5치고는 쉬운 그냥 dfs.잃어버린 나의 3시간....import sysinput = sys.stdin.readlinedef chick_dist(chick_list, house_list): global min_length sum_dist = 0 for cur_h in house_list: cur_min_dist = sys.maxsize for .. 2024. 11. 18.
[BOJ] 감시 (G3, 15683) https://www.acmicpc.net/problem/15683 골드 3 다운 쉽지  않은 문제.처음 들었던 생각은 이거 어차피, 각 카메라가 비출 수 있는 최대 칸을 그리디하게 비추면 되는거 아닌가?하지만, 몇 가지 문제가 있다.(1) 동률일 경우 어떻게 처리?(2) 동률일 경우 방향을 겹치게 비춰주면 그리디하다고 꼭 최대는 아님.. 안겹치게 비춰줘야 최대... 아 복잡..즉, 그리디로는 풀기 어려우니 DFS 해 줘야 한다.각 카메라별로 회전 방향이 정해져있는데, 두 개 이상의 경우는 두 개 이상의 방향이 합쳐졌다고 고려하면 된다.1번 카메라는 상/하/좌/우2번 카메라는 상하/좌우3번 카메라는 상좌/상우/하좌/하우4번 카메라는 상하좌/상하우/상좌우/하좌우5번 카메라는 상하좌우이 각각 중 1개씩 고르.. 2024. 11. 16.
[BOJ] 웜홀 (G3, 1865) - 벨만-포드 알고리즘 튜토리얼 https://www.acmicpc.net/problem/1865그 동안 학습한 최단 경로 구하기 알고리즘은 다음과 같다.- 다익스트라 알고리즘 : 힙 기반, 간선이 모두 양의 가중치일 때만 사용 가능 - 플로이드-워셜 알고리즘 : DP기반, 모든 거리를 구해주지만 V^3 만큼의 시간복잡도....이 문제는 일단 웜홀의 존재 이유 때문에 다익스트라는 사용 불가능하다.게다가 이 문제는 여러 번 워프를 타면서 시간을 돌릴 수 있는지?를 물어본다.플로이드-워셜 알고리즘에서 음의 가중치를 갖는 루프를 찾기 위해서는 자기 자신으로 돌아오는 지점의 , 즉 dp[i][i] 문제는 시간 복잡도 때문에 터져서 불가. 이 문제는 벨만-포드 알고리즘을 사용해야만 한다. 벨만-포드 알고리즘의 핵심은 모든 edge를 항상 활용한.. 2024. 11. 16.
[BOJ] 플로이드 (G4, 11404) : 플로이드-워셜 vs 다익스트라 https://www.acmicpc.net/problem/11404  이 문제를 다익스트라, 플로이드-워셜 둘 다 써서 풀어보았습니다. (1) 다익스트라- 하나의 시작점에서 각 점들까지의 최단 경로를 계산합니다.- heap 기반 알고리즘으로 최단 비용을 차례 차례 뽑아나가는 방식입니다.- 그리디 알고리즘 기반이며, 음수 가중치가 포함될 경우 다른 방법을 써야 합니다.- 시간 복잡도 : ElogV# solution (1) dijkstra로 풀어 보기. 하나의 점에서 거리 구하기.# Time complexity: VlogE# 특징점 : 음의 가치에서는 사용 불가!import sysimport heapqinput = sys.stdin.readlineINF = 1e12vertex = int(input())edg.. 2024. 11. 15.
[프로그래머스] 다단계 칫솔 (Lv 3) https://school.programmers.co.kr/learn/courses/30/lessons/77486 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제를 매우 잘 읽어야 한다. (안읽어서 또 틀린 사람 나야나)한번의 수익이 발생할 때 마다, 자신은 90%를 가지고(원단위 절사 방식) 나머지를 자신의 추천자에게 올린다.추천자는 그거를 또 바로 올려야 한다. 언제까지? 0이 될 때 까지. 혹은 더 이상 상사가 없을 때 까지.트리 문제인척 하는 단순 while 문제다. 다만, 저장해두면 도움되니까. 애초에 dict로 만들어주면 데이터 접근이 쉽겠지?while의 종료 조건은 더 이상 정산 불가인.. 2024. 11. 15.
[프로그래머스] 양궁 대회 (Lv 2) https://school.programmers.co.kr/learn/courses/30/lessons/92342 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 보기보다는 매우 간단한 문제이다. 0점을 제외하고 한 발 더 쏘거나, 아예 안 쏘거나 그리디한 케이스만 따지면 된다.남는 화살은 모두 0발로 간다. 어차피 0 안보내도 아예 질거라면 무조건 지고, 최적의 케이스는 저기 안에서만 나온다.저 케이스를 1점~10점 모두 순차적으로 따져줘야 하므로 DFS가 가장 자연스럽다.아, 점수 차가 동일할 케이스가 여러 개 나올 수도 있다. 이때 예외처리를 위해 정렬 잊지 말자. 이거 빼먹어서 두 번 실패함.wi.. 2024. 11. 15.

티스토리툴바