https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 이 문제 풀다가 사람들의 풀이를 찾아보는데 다들 max(map(max, arr)) 이런 식을 쓰는 걸 발견했다 읭?? 저건 뭐지 map(int, sys.stdin.readline().split()) 할 때는 써봤어도 저건 뭐지?? 했는데! 찾아보니 2차원 배열에서 가장 큰 값을 찾아주기 위해 쓴거였다. 이걸 쓰지 않으면 강수량의 가장 큰 값을 일일이 for문을 돌면서 찾아야 해서 무척 비효율적이었을 것이..
[BaekJoon] 1931 회의실 배정 - python
https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 학교 알고리즘 수업시간에 배웠던 회의실 배정문제.. 어떻게 하는건지는 아는데 막상 코드로는 생각이 안났다. 내가 원래 짠 코드는 정말 복잡하고 보기 어려운 쓰레기(?) 코드였는데 인터넷을 찾아보다가 람다식으로 내가 하고자 했던 걸 완벽히 구현한 코드를 발견했다!! 정말 존경스럽다.. 회의실 배정의 핵심 풀이는 회의의 종료시간이 가장 이른 것을 우선적으로 선택하는 것이다. 따라서 맨 처음에 lambda식으로 회의의 시작시간을 기준으로 먼저 정렬하고, 그 다음으로 회의의 종료시간을 기준으로 lambda식을 사용하여 ..
[Algorithm] Greedy(그리디) 개념 정리
수업시간에 교수님께서 그리디 알고리즘을 소개하실 때 단어 뜻 그대로 '탐욕' 알고리즘이라고 설명하셨던게 기억난다. 실제로 이 알고리즘은 가장 좋아보이는, 당장 좋은 것을 먼저 고르는 알고리즘이다. 대표적으로 동전 개수 구하기, 회의실 배정 등의 문제들이 있다. 무조건적으로 그리디가 최적해를 보장하지는 않기 때문에 (오히려 그리디로 최적의 해를 찾기 어렵다고 한다.) 그리디를 사용할 때는 문제 유형을 보고 판단하도록 하자. 동전문제는 그리디의 대표적인 문제인데, 이때 그리디 알고리즘으로 최적해가 보장되는 경우는 아래의 조건을 만족한 경우이다. - 동전의 액면이 모두 바로 아래 액면의 배수가 된다. 백준에 올라와있는 동전 문제는 주어진 동전들이 배수의 관계이므로 그리디 알고리즘을 사용하여 풀 수 있었다. h..
다이나믹 프로그래밍이란, 한마디로 똑같은 계산을 두번 다시 하지 않도록 하는 알고리즘이다. DP는 메모리 공간을 조금 더 사용하는 대신, 연산 속도를 증가시키는 방법이다. 따라서 한번 구한 결과값을 별도의 메모리 공간에 저장하는 방식을 따른다. 이러한 방식을 Memoization(메모이제이션)이라고 한다. DP에도 두가지 방식이 있는데 하나는 Top-Down(하향식), 하나는 Bottom-Up(상향식)이다. '이것이 코딩테스트다' 교재에도 나와있고 백준에도 나와있는 DP의 가장 베이직한 문제 "1로 만들기"를 다이나믹 프로그래밍으로 푼 코드이다. 이때 Bottom-Up(상향식)을 사용했다. Top-Down 방식으로도 구현해보려고 했는데 찾아보니 메모리 초과가 난다고... https://www.acmicp..