본문 바로가기
BOJ 그리디 문제 모음1/#11047동전0/#1931회의실배정/#11399ATM/#1541잃어버린 괄호/#1744수 묶기/#2875대회or인턴 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 먼저, 그리디는 이 순간 가장 좋은 부분만을 고려해서 연산하는 것이 최적의 해가 되는 문제이다. 이게 말은 쉬운데, 증명이 어렵다. 물론, 쉬운 문제들은 굳이 증명하지 않아도 이게 그리디로 풀었을 때 최적해라는 것을 직관적으로 알 수 있다. 하지만, 문제가 어려워지면.. 아래와 같은 어려움이 따른다.. 이게 그리디로 푸는게 최적해인지..
카카오/코딩테스트 기출/추석트래픽/2018 Blind Recruitment 1차/cpp(C++)풀이 cpp(C++)로 풀었으니 참고. 카카오 기출을 한 번 풀어야겠다고 마음 먹고 처음 접한 문제다. 그냥 이름 재밌어보이는거로 잡았는데 하필이면 난이도: 상 짜리.. 눈물나게 고민하고 풀었다. 하루종일 생각했다. 솔직히 처음에 감이 안잡혀서 카카오 공식 홈페이지에 해설을 간단하게 읽어본 후 많은 고민 끝에 구현할 수 있었다.. (그러니까 후딱 안풀린다고 절대 좌절하지 말자!) 크게 아래와 같은 로직으로 생각했다. 대전제로 먼저 모든 시간은 millisecond 단위로 변환하자. 그렇다고 해도 int 범위안에 넉넉하게 담을 수 있으니 ok 각 로그 문자열마다 순회를 하면서 먼저 string을 시간으로 변환한다. 아래는 각 로그 문자열string처리 로직이다. 로그 문자열의 종료 시간(endTime)을 먼저 ..
Rails_추천 시스템에 Redis 적용(Implementaion of Redis in Ruby on Rails) 대략 100,000 건의 rows에서 20개 정도의 추천 row를 내려주는 api를 만들게 되었다. 이때 추천 rows들은 거의 변하지 않고, 모든 Client들에게 항상 동일한 추천 rows를 보여주는 로직이었다. 추천 rows는 거의 변하지 않음에도 불구하고 요청시마다 100,000개의 rows가 있는 테이블에 Query를 날리는 것보다는 캐싱을 해두고 쿼리 없이 보여주는게 좋다고 생각했다. Redis Setting in Rails Application 위와 같이 Redis Object 와 args 를 url 과 드라이버와 함께 Initialize 해준다. 아 물론, initializers directory 내 파일 들은 rails 내 library에 있는 run_intializers method에 ..
Ruby 의 Garbage Collection 을 이해할 수 있는 GC 모듈 (Ruby GC Module, which helps to understand the Garbage Collection of Ruby) C++을 공부하면서, C++의 특징은 소멸자를 기본적으로 직접 선언하여 메모리 해제도 직접 해준다는 점이다. 근데, Ruby 같은 high level 언어는 메모리 해제를 직접하지 않고, Garbage Collection 이라는 기능을 이용하여 힙 메모리에 할당된 object 가 해제된다. 여기서 궁금한 점은 아무리 Garbage Collection 기능으로 메모리 관리가 저절로 된다고 해도 메모리 누수가 생길 수 있는거 아닌가?(가령, 해제가 안되는 것으로 분류된다든지), 과연 Garbage Collection은 어떤 기준으로 메모리를 해제할까? 라는 점이 궁금했다. 궁금증에 대한 답변은 우선 아래와 같이 요약할 수 있다. -> object memory가 해제 안되는 경우는 Constant Variab..
C++ oop 관련 개념 정리 김포프 oop 정리자료다.. 메모리 관점에서 강의를 해주는 것이 참 마음에 든다. oop1: https://www.evernote.com/l/AgJ7m-39F25CQ77EgtI-oWywu9HpZQP-Vo0 oop2: https://www.evernote.com/l/AgKlLYfikFRODb1YgwC4oQRbFVX-oxAVtpw oop3: https://www.evernote.com/l/AgIQipummp1DWaCEgJhQEy125iFDpnIYmm8
Rails Application Request/Response Cycle(레일즈 애플리케이션은 서버에서 어떻게 작동할까?) 하드웨어 서버 영업을 할 때 부터 항상 궁금했던건데, 물리 서버에서 어떻게 백엔드 애플리케이션이 동작을 하는지가 항상 궁금했었다. 그런 동기에서 Rails Application을 작동 방식, 즉 서버의 핵심인 Request/Response Cycle을 정리해보았습니다. 크게 아래와 같은 1~8단계로 Cycle로 작동하며, 각 단계 위에서 Object가 새로 만들어지면서 정의된 method들을 Call한다고 볼 수 있습니다. 참고로, 같은 컨트롤러 클래스의 심지어 같은 Action Method를 요청하는 복수의 Request들이 있을 때 Object들은 어떻게 생성될까요? 이떄는 각 요청 당 Object들이 따로 만들어집니다. (the controller class creates a new instance..
RubyOnRails/Model Association Association 정리 Model간 관계를 사전에 정의하여 두 개 이상의 모델에서 동시에 데이터를 갖고 올 때, method 사용을 통해서 빠르게 갖고 올 수 있음 (Association을 사용하는 이유) Association도 결국 ActiveRecord에서 사전에 정의된 Method들이며, 알맞게 Model < ActiveRecord 파일 내에서 association을 정의한 뒤, 해당 Model에서 메쏘드처럼 사용하는 것이다. 기본적으로 모델 간 관계를 맺는 방식은 테이블의 foreign_key와 상대편 테이블의 primary_key다. primary_key는 말그대로 참조 대상 테이블의 id 이고, foreign_key는 별도의 언급이 없을 시에 참조 소스 테이블 내, (참조대상테이블 모델이름..
Rails Transaction Isolation Level (트랜잭션 격리 레벨) 트랜잭션 격리 레벨에 대해서 찾아본 이유는, 예전에 유저 등의 랭킹 시스템을 만드는 프로젝트를 맡은 적이 있었습니다. 배치 프로그램으로 매일 마다 갱신된 랭킹을 db에 삽입하는 기능을 구현해야 했는데, Transaction을 걸어서 all or not 으로 한번에 데이터를 커밋하고자 하였었습니다. 여기서 더 궁금했던 점은 랭킹 산출을 위해서는 실시간 유저의 스코어가 필요했는데, 랭킹 반복 연산 도중에 유저의 정보가 바뀌면 이것이 어떻게 저장되지? 라는 의문점에서 격리레벨이라는 것을 더 찾아보게 되었었네요. 이 결과, Backend 개발에서는 트랜잭션 격리 레벨을 만들어두고, 데이터의 특성이나 비즈니스 로직에 따라 격리 레벨을 달리 준다는 것을 알게 되었습니다. Transaction 을 먼저 짚고 넘어가면..

티스토리툴바