분류 전체보기80 그리디 - 1931 회의실 배정 with Python https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 해결 그리디 문제 중 대표적인 문제라 생각 된다. 간단하게 생각해보자 앞의 회의실이 끝나지 않으면 뒤의 회의실은 시작하지 못한다. 즉 앞에서 끝나는 시간이 빠르면 빠를 수록 그 다음에 시작할 수 있는 애들도 많아진다로 생각해도 된다는 것이다. 자 그러면 우린 끝나는 시간을 기준으로 정렬을 한다. 이렇게 정렬 된 후 이 끝나는 시간보다 더 큰 start를 가진 제일 먼저 나오는 녀석으로 또 골라 반복하면 되는 것이다. 코드 import sys input = sys.stdin.readline n = int(in.. 2023. 2. 27. 그리디 - 10610 with Python https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 문제 해결 그리디로 간단히 풀리는 문제이다 30의 배수라는 것을 생각해보자 30 60 90 120 150 180 210 240 270 300 330 360 390 420 450 480 510..... 반대로 보면 이는 뒤에는 0이 꼭 들어가고 3의 배수라는 것이다. 3의 배수는 무엇인가 각 자리수의 합이 3의 배수이면 그 숫자는 3의 배수인 것이다. 즉 0이 꼭 하나 이상있어야하고 각 자리수의 합이.. 2023. 2. 27. Dijkstra with Python 소개 다익스트라는 최단경로 알고리즘 중에서도 대표적인 예시라고 할 수 있다. 하나의 시작 정점에서부터 모든 다른 정점까지의 최단 경로를 구하는 알고리즘이다. (다만 weight값이 음수이지만 않는다면) 배경 최단 경로 알고리즘은 graph 자료구조를 사용하며, node와 edge를 이용해 실제 거리를 나타낸다. 1. 출발 노드, 도착 노드 설정 2. edge에 값을 부여 3. 출발 노드부터 시작해 방문하지 않은 인접 노드 방문, 거리를 계산하고, 현재거리와 비교해 더 작은 값을 넣는다. 4. 방문하지 않은 노드 중 가장 비용이 적은 노드 선택 5. 해당 노드를 거쳐 특정 노드로 가는 경우를 고려해 최소 비용 갱신 6. 4~5를 반복 ex) 이런 그래프가 있다 가정하자 자 그럼 표를 만들어서 보자 0 2 .. 2023. 2. 26. 소마 14기 - 코테 1차 후기 배경 처음으로 소마를 지원하게 되었다. 나이가 조금 있고, 대학을 졸업을 했어서 아 이걸 내가 지금 지원해도 옳은가 라는 생각이 계속 들었다. 그렇게 고민을 하다보니 어느새 2/25일... 일단 코테 1차를 보기로 결정하였다. 문제는 알고리즘 4개! SQL 1개로 저번 기수랑은 Web이 없어지고 문제수도 줄었다. 2시에 시작을 하였으나 중간 중간 멈추는 느낌이 들기는 하였는데.... 일단 미리 말하자면 난 2솔을 하였다. 사실 문제는 4개를 풀었으나 예외처리라던가 히든 케이스를 제대로 고려하지 못하여 2문제는 확실하게 틀린것으로 판단되었다. 문제를 간단히 요약하자면 1번 아마 단순 구현인것같다 2번 또한 단순 구현이다 3번 알고보니 완탐 + 조합의 문제였다 4번 bfs로 풀리는 문제이다. 이렇게가 알고리.. 2023. 2. 26. 이전 1 ··· 6 7 8 9 10 11 12 ··· 20 다음 728x90
