동아리에서 DP를 배우면서 과제로 푼 '이진수 찾기'의 풀이 과정을 정리하고자한다. 처음에 문제를 딱 읽었을 때는 무슨 말인지 긴가민가 했다. 직접 써보면 간단하다. 만약 3자리 이진수 중, 2개 이하의 비트만 1인 것을 크기순으로 나열하면 다음과 같다. 000 001 010 011 100 101 110 이제 주어진 조건하에서 주어진 숫자 번째의 이진수를 찾아야한다. 처음에는 어떻게 풀어야할지 감이 안왔다. 그래서 예제 입력 1번 5 3 19 크기순으로 직접 나열해봤다. 00000 00001 00010 00011 00100 00101 00110 00111 01000 01001 01010 01011 01100 01101 01110 10000 . . . 근데 여기까지 쓰고보니 뭔가 규칙이 보인다. 위 사진처..
다른 사람의 코드를 보고 아이디어를 얻었음에도 구현을 정확하게 하지 못해 결국 질문게시판의 반례 코드를 보고 해결한 문제. '과제'를 풀면서 깨달은 것을 정리해보고자 한다. 과제의 문제 설명 자체는 간단하다. 마감일, 과제 완료시 얻는 점수에 대한 정보가 과제 수만큼 주어진다. 이제 남은 기간동안 효율적으로 최대한의 점수를 얻기만 하면 된다. 나는 당연히 첫날부터 과제를 어떻게 선택하는 것이 좋은지에 대해 고민했다. 점수가 가장 높은 순으로 고르는 것이 제일 먼저 떠올랐다. 그리고 반례도 바로 떠올랐다 ㅋㅋ 3 30 2 20 1 10 최대값은 60이지만, 점수가 높은 순으로 뽑았다가는 50밖에 얻지 못한다. 그렇다면 마감일이 빠른 순으로 뽑으면 되는가? 과제 문제의 예시 입력을 보면 하루 남은 과제는 아..
아무리 고민해봐도 해답을 알 수 없었던 문제였던 난로 문제에 대해 정리해보고자 한다. (결국 다른 사람의 아이디어를 참고하여 내 나름대로의 방법으로 풀었다) 당연히 처음에 떠올렸던 풀이는 시간 간격별로 잘라서 비교하는 것이었는데, 처음에는 그 방법으로 풀 수 없다고 생각했다. 단순히 인접한 친구의 방문 시간 간격이 길 수록 성냥을 먼저 쓴다고 생각하기에는 그렇게 소비한 성냥 때문에 오히려 더 많은 시간에 난로를 지펴야 하는 것 아닌가 하는 생각을 했다. 사실 문제를 풀면서 계속 헷갈렸던 것이, 친구가 올 때까지 난로를 핀다는 이상한 생각에 계속 사로잡혀 있었다. 가령 다음과 같이 친구가 방문을 하는 상황에 성냥이 2개 있다고 하자. 최적해의 알고리즘대로라면 '10' 시간에 방문하는 친구가 올 때 난로를 ..
이전의 등산 문제와 마찬가지로.. 수많은 "맞왜틀?!!" 을 외치게 만든 문제. 분명 알고리즘은 맞는 것 같은데, 다른 사람의 정답 알고리즘과 같은 틀의 알고리즘인데 왜 런타임에러가 나고, 시간초과가 발생하는 것인지 몰라서 고생했던 문제이다. 다른 사람의 코드와 내 코드를 비교하면서 배운 점들을 기록해보고자 한다. 다음은 내가 비교했던 분의 정답코드가 담긴 블로그 주소이다. https://developmentdiary.tistory.com/442 [Python]트리 백준 5639 문제 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 � developmentdiary.tis..
교내 동아리에서 진행한 알고리즘 스터디의 마지막 수업으로 다익스트라를 배웠다. 연습 문제 중 이 문제가 개인적으로 막힌 부분이 많았고, 그로부터 배운 것들을 정리하고자 한다. 우선 이 문제를 풀기 위한 아이디어도 떠오르지 않았다. 결국엔 동아리 스터디 내용을 통해 아이디어를 얻고, 아이디어를 구현하여 제출하였다. 아이디어는 다음과 같다. 집에서 갈 수 있는 모든 산의 정상들 학교에서 갈 수 있는 모든 산의 정상들 이 두가지를 따로 구한다음 각각에서 구한 산의 정상의 교집합을 취하여 문제가 원하는 방식대로 계산하면 된다. 만약 교집합이 없다면, 답이 없다는 뜻. 나는 다익스트라를 구현하고, 다익스트라의 결과로 나온 집/학교에서 출발 했을 때 갈 수 있는 모든 산의 정상들 (노드) 번호, 각각의 노드로 가는..
지난 번에는 맥주축제를 제일 먼저 떠올랐던 이분탐색으로 풀어보았다. 이번에는 학습 목적에 맞게 우선순위 큐로 풀어보고자 한다. 우선순위 큐로 풀 때는 다음과 같은 알고리즘을 사용하였다. 1. 맥주를 도수가 낮은 순으로 우선 정렬하고나서 선호도 순으로 정렬한다. 2. 맥주가 있는 리스트를 돌면서 맥주를 하나씩 뽑는다. 2-1. 뽑은 맥주의 도수를 현재 도수로 한다. 2-2. 뽑은 맥주의 선호도를 우선순위 큐에 넣는다. 2-3. 우선순위 큐에 있는 선호도 합과 기준 합을 비교한다. 2-4-1. 기준 합보다 크거나 같다면 find변수를 True로 바꾸고 현재 도수를 출력한다. 2-4-2. 기준합보다 작다면 우선순위 큐에서 선호도가 가장 작은 원소를 pop한다. 3. 2번과정을 반복한다. 4. 만약 find변수..
교내 동아리에서 진행한 알고리즘 스터디에서 '우선순위 큐' 의 연습문제로 주어졌던 문제이다. 우선순위 큐를 사용하기 전에 제일 먼저 떠오른 풀이는 '이분 탐색' 아니나 다를까 문제 알고리즘 분류에도 '이분 탐색'이 있었다. 이분 탐색은 항상 익숙하지 않고 힘들었기에, 오랜만에 연습해보기 좋은 문제라고 생각했다. 내가 떠올린 아이디어는 '맥주의 선호도' 값을 기준으로 정렬하고 설정한 맥주의 도수보다 작은 맥주 중, 선호도가 높은 것들만을 그리디하게 뽑아서 선호도의 합을 구하는 것이다. 그리고 맥주의 도수를 기준으로 이분탐색을 진행하여 가능한 최소 도수를 구하고 최소 도수가 없다면 -1을 출력하도록 하면 된다 def check(mid): global kind, day, sum_taste s = 0 cnt =..
solved.ac 기준 실버2 수준이었던 제게는 매우 어려웠던 스터디 연습 문제 이 문제를 푸는 과정을 적으며, 효율적인 알고리즘에 대한 복기를 해보려고 합니다. [문제] 복면산이란 수학 퍼즐의 일종으로, 어떤 계산식의 각 숫자들을 특정 문자로 바꾸면 각 문자가 어떤 숫자인지 맞추는 퍼즐이다. => 각 문자가 어떤 '숫자' 인지 맞추는 퍼즐입니다. 저는 '숫자'와 '수'를 혼동해서 "A = 10 같은 것도 가능할까?" 같은 쓸데없는 고민도 했었습니다. 복면산 문제가 주어질 때, 답이 존재하는지 여부를 출력하시오. 단, 같은 문자는 같은 숫자에 대응되어야 하며, 서로 다른 문자는 서로 다른 숫자를 나타낸다. 또한, 수는 0으로 시작할 수 있다. =>아래 예시 힌트가 없었다면 빼먹고 체크를 안할 수도 있었던..
