https://www.acmicpc.net/problem/20500 20500번: Ezreal 여눈부터 가네 ㅈㅈ 문제의 답을 $1\,000\,000\,007$로 나눈 나머지를 출력한다. www.acmicpc.net 초급 알고리즘 DP 강의를 수강 후 연습문제로 풀게된 문제이다. 문제는 간단하다 1과 5로 이루어진 N자리 수 중 15의 배수를 구하는 문제이다. 어떻게하면 이 문제를 DP를 활용하여 구할 수 있을까? 아무런 아이디어가 떠오르지 않았다. 그래서 그냥 무작정 써봤다. 1자리수 1, 5 0개 2자리수 11, 15, 51, 55 1개 3자리수 111, 115, 151, 155, 511, 515, 551, 555 근데 3자리수를 쓰고보니 15의 배수가 한눈에 안보인다. 일일히 나눠보는 생각을 했지만..
중급 알고리즘 - 그리디 수강 후 연습 문제로 풀게된 문제이다. https://www.acmicpc.net/problem/2878 2878번: 캔디캔디 첫째 줄에 M(1 ≤ M ≤ 2×109)와 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 친구들이 받고 싶어하는 사탕의 개수가 주어진다. 이 개수는 2×109보다 작으며, 친구들이 받고 싶어하는 www.acmicpc.net 친구들에게 사탕을 나눠줘야하는데 사탕은 반드시 모자라다. 내가 원하는 사탕이 10개인데, 사탕을 5개만 받았다면 그 친구는 못받은 사탕개수의 제곱만큼 분노하게 된다. (분노치 5*5 = 25) 각 친구들의 분노치 합을 최소로 만드는 문제이다. 이제부터 내가 이 문제를 풀기까지 사고한 과정을 정리하고자 한다..
https://www.acmicpc.net/problem/5520 5520번: The Clocks Read nine numbers from the standard input. These numbers give the start positions of the dials. 0=12 o'clock, 1=3 o'clock, 2=6 o'clock, 3=9 o'clock. The example in figure 1 gives the following input data file: www.acmicpc.net 백준 5520 The Clocks 문제이다. Figure 1과 같이 3x3 배열로 시계들이 있다. 우리의 목표는 모든 시계를 12시 정각을 가리키도록 최소한의 횟수로 돌리는 것이다. 시계를 돌리는 방법은 Fig..
냅색 문제를 공부하고나서 도전했던 문제이다. 스스로 아이디어를 찾는데에 실패해서 결국 검색을 통해 해결했지만, 이 문제를 통해 얻어갈 수 있는 부분이 있었기에 정리하고자 한다. 어떤 앱을 실행시키기 위해서 추가로 M의 메모리를 확보해야 하는 상황이다. 따라서 이 메모리를 확보하기 위해 기존에 실행 중이었던 앱을 끄고자 한다. 실행 중인 앱을 한번 끄면 다시 키는데 드는 시간 등 추가 비용이 발생하게 된다. 이 비용을 수치화 할 수 있다고 가정하면 실행 중이던 어떤 앱을 껐을 때 얻을 수 있는 메모리가 m, 발생하는 비용이 c로 정해진다. 이제 N개의 앱이 주어진다. 각각의 앱마다 m, c 의 값을 갖는다. 이 문제는 M이상의 메모리를 확보하기 위해 필요한 최소 비용을 구하는 것이다. 아직 냅색문제가 익숙..
동아리에서 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' 시간에 방문하는 친구가 올 때 난로를 ..
겨울 방학동안 연합 알고리즘 스터디 동아리 활동을 하게 됐다. 동아리 활동은 알고리즘 강의를 듣고 BOJ에 올린 연습문제를 푸는 것이다. 연습문제 풀이 여부를 통해 출석체크를 한다. 이번에 나는 동아리 멘토의 역할로 일정 동아리원을 담당하여 출석체크를 하는 역할을 맡게 되었다. 그런데 문제점이 있었다. 현재 스터디 구성원이 총 300명 가까이 되는데, 그 중에 내가 담당한 스터디원은 약 30명이다. 그리고 백준 연습문제는 스코어보드 형식이기 때문에, 먼저 문제를 다 푼 사람 순서대로 정렬된다. 백준 연습문제의 300명치 스코어보드를 보고 내가 담당한 30명을 골라내어 일일히 체크한다..? 사실 30명 정도면 그렇게 많은 사람도 아니고, 실제로 300명이 모두 출석을 다하지는 않기 때문에 생각보다 오래 걸..
인턴을 하면서 스스로 공부하고, 회사에서 배운 델파이 관련 내용과 개인적으로 느낀 점을 정리하고자 쓴 게시글 입니다. 여름 방학 때는 정말 기본적인 개념들을 배우고(SQL, 네트워크 개념) 회사에서 사용하는 델파이를 가볍게 맛만 봤다면, (사실 겉을 핥지도 못한 수준이었다) 이번 겨울 방학 때는 본격적으로 델파이를 배우기 시작했다. 델파이를 배우기 전에 학교에서 자바를 수강한 건 정말 신의 한수였다. 자바를 공부한 덕분에 GUI에 대한 기본적인 구현 방법을 알 수 있었다. (컴포넌트의 개념, 이벤트의 개념, 이벤트 처리 등등) 여름 방학때는 이런 것을 전혀 모르고 설명을 듣다보니 와닿지가 않았는데, 공부하고 다시 들으니 이해가 매우 잘 됐다. 자바를 배울 때는 코딩만을 사용해서 윈도우 창을 디자인하고 컴..
본 게시글은 'Do It! 안드로이드 프로그래밍 개정7판' / '단계별로 배우는 안드로이드 프로그래밍' 두 권의 교재를 통해 학습한 내용을 스스로 정리하는 목적으로 작성한 게시글 입니다. *프래그먼트 내용은 '단계별로 배우는 안드로이드 프로그래밍'에는 없는 내용입니다. Fragment, 우리말로 '파편' 이라는 뜻이다. 안드로이드에서 프래그먼트는 '부분화면'을 만드는데 사용된다. 또 각각의 프래그먼트는 액티비티처럼 독립적이어서 따로 관리할 수 있다. 프래그먼트는 반드시 액티비티 '위에' 존재해야한다. 액티비티로 만든 화면을 '프래그먼트'라는 부분 단위로 쪼개 관리하는 것이기 때문이다. 프래그먼트가 동작하는 시점은 메모리에 생성된 시점이 아닌, 액티비티 위에 존재하게된 시점이다. 프래그먼트는 '프래그먼트매..
