리나 Dev토리

이것이 코딩테스트다 파이썬(나동빈 저) 그리디 - 볼링공 고르기 그리디 문제를 풀다가 답안지와 다르게 풀어서, 혹시 나처럼 다른 답안을 찾는 사람들에게 도움이 될까 해서 올린다. 문제 A,B 두사람이 볼링을 치고 있고, 서로 다른 무게의 볼링공을 고르려고 한다. 볼링공은 총 N개, 공의 번호는 1번부터 순번이다. 같은 무게의 공이 여러개 있을 수 있는데, 다른 공으로 간주한다. 볼링공의 무게는 1~M까지의 자연수이다. 입력이 5 3 1 3 2 3 2 라면, 공의 갯수는 5개, 공은 3kg 까지이다. (kg는 임의로 붙인 단위입니다.) 1번 공부터 5번까지 공의 무게가 그 다음 줄에 입력된다. 이때 두사람이 고를 수 있는 공 번호의 조합은 1,2 1,3 1,4 1,5 2,3 2,5 3,4 4,5번으로 총 ..

자료구조/알고리즘 4주차 알고리즘 마지막 주차 이번주에는 이진탐색, 최단경로, 다이나믹 프로그래밍을 배웠다. 마지막 주차라서 그런지 난이도도 상당히 높았다. 이진탐색 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아낼 때, 반절씩 범위를 좁혀나가서 원하는 데이터를 찾는 알고리즘이다. 1에서 100까지 숫자 중에 친구가 임의 값을 고르고, 내가 그 숫자를 맞추는 게임을 한다고 할때 내가 50을 말하면, 친구는 up 이나 down 중에 말하게 된다. up이라 말하면 나는 50 ~ 100 범위에서 반절인 75를 물어본다. down이라 하면 50 ~ 75 범위에서 중간인 58을 물어본다. down이라 하면 50 ~ 58 범위에서 중간인 54를 물어본다. up이라 하면 ... 이런식으로 답을 찾아내듯이 중간 값을..