사실 DP 문제는 겁부터 난다. 다른 알고리즘과 마찬가지로 익숙해지고 많이 풀어보면 쉽게 느껴지지만 처음에는 도무지 내 지능이 닿지 못하는 영역인것만 같은 느낌이 들고, 그 좌절감이 참 씁쓸하기 때문이다. DP 문제는 가장 쓴 맛이 컸던 알고리즘이었다. 쉬운 문제부터 천천히 시작하자는 마음으로 만만한 녀석을 골랐다. 초기 아이디어 사실 타일 채우기는 DP 의 가장 쉬운 문제인 피보나치와 닮아있다. 다만 이전 타일에서 새로운 경우의 수를 곱해주는 것과 별개로 아예 새로운 배열이 생겨난다는 점을 염두에 두어야 한다. 처음에는 dp[n-2] *3 + dp[n-3] *2 두가지만 고려했었는데, 아예 새로운 배열도 나오겠구나 라는 생각에서 dp[n-2*i]*2 로 전부 더해주어야 한다는 생각에 닿았다. 문제풀이 ..
분류 전체보기
어제 토비의 스프링 5장 챕터를 읽으면서 Transaction 의 원자성 에 대해서 처음 알게 되었다. 사실 Transaction 을 선언함에 있어서 가장 중요하고 핵심적인 이야기로 보이는데, 이걸 이제서야 개념적인 지식으로 습득했다는 데서 다소 충격적이었다. 가끔씩 Service 단에 Transaction 이 진행되는 메서드를 작성하면서 뚜렷한 이유는 없지만 왠지 모를 불안감, 다소 완성도가 떨어지는 듯한 느낌이 들곤 했는데, 바로 원자성에 대한 보장이 없다는 점이 그 원인임을 알게되었다. 이걸 깨닫고 TIL 에 Transaction 의 특성 4가지를 정리해서 아주 그럴듯하게 정리해놓고 싶었지만 솔직히 원자성 이외의 특성들에 대해서 잘 알지도 못하면서 떠드는 것은 기만같다. 그래서 간단하게 원자성에 대..
초기 아이디어 딱맞는 알고리즘이 별다르게 방법이 안 떠오를는 완전탐색이 먼저 떠오른다. 이럴 때는 치킨집의 최대 개수가 13 인것도 하나의 힌트가 된다. 이 이상 넘어가면 조합의 개수가 너무 커지기 때문이다. 재귀적으로 치킨집의 조합을 만들고 마지막에 최소 거리를 계산하는 식으로 정답을 찾았는데, 이전에 푼적이 있던 문제였다. 그때 참 최적화를 잘 해놓았는데, 벡터 배열에 모든 경우의 수를 담아내고 차례로 이걸 꺼내서 최소거리를 만들어내는 방식이었다. 이번에는 비트마스킹을 써서 개선해 보았다. 사용하는 메모리가 더 적어졌다. 문제풀이 조합 벡터배열 이용 #include using namespace std; int n, m; int a[55][55]; vector house; vector chicken; ..
개발자는 코드를 작성할 때 언제나 런타임 시 발생하는 예외 상황에 대해 고려 해야한다. 코드가 항상 의도대로 동작하는 것은 아니기 때문이다. 예상하지 못한 상황들을 적절하게 핸들링 함으로써 원하는 대로 로직이 작동하지 않은 경우에도 어플리케이션을 올바르게 작동하게 한다거나, 아니면 예외를 의도적으로 발생시켜 여러가지 시나리오를 핸들링 하게 만들 수 있다. 1. RestControllerAdvice 예외 처리를 위해서는 기본적으로 RestControllerAdvice 어노테이션을 사용 할 수 있다. RestControllerAdvice 어노테이션은 Controller 계층의 예외를 전역적으로 처리하는 AOP 기술의 일종이다. Advice 라는 단어에서 프록시 객체를 생성하거나 바이트 코드 조작하는 AOP ..
이전 글 : 채팅 서비스에 Redis 도입 (1) [ https://techforme.tistory.com/16 ] 이전 글 : 채팅 서비스에 Strategy Pattern 적용 [ https://techforme.tistory.com/15 ] 구독 정보 Repository 로서 Redis 도입 이전 글에서 채팅 서비스에 Message Broker 로서 Redis 를 도입했던 글을 썼었는데, 이번에는 구독 정보 Repository 로서 Redis 를 적용한 부분에 대해서 쓰려고 한다. 구독 정보 Repository 는 이전에 인메모리 캐시를 이용한 ConcurrentHashMap 으로 구현하면서 Strategy 패턴을 적용했었는데, 그렇기 때문에 아래와 같이 인터페이스만 구현하고 yml 파일 설정만 변경..
초기 아이디어 조합이 가장 먼저 떠올랐다. 알파벳 스물여섯개 중 주어진 숫자만큼 조합으로 이용해서 뽑고, 단어마다 해당 단어가 뽑은 단어에 포함되어 있는지를 셈해보는 것이다. 최악의 경우 21C10 의 경우의 수에 각각 50개의 단어를 판별해야 한다. (acnti 다섯글자는 반드시 있어야 하므로) 대충 보면 시간 초과가 날 것 같진 않은데 ... 비슷한 문제를 재귀를 이용한 조합으로 단순히 풀었다가 시간 초과가 난 기억이 있어서 그냥 비트마스킹 연습도 할겸 비트마스킹으로 풀어보기로 한다. 비트마스킹은 사실 근본적인 알고리즘이라기 스킬의 일종이다. 이진법으로 나타낸 수의 각 자리를 하나의 불리언이라고 생각하고 특정 조합을 하나의 숫자로 나타내는 것이다. 예컨대 13을 이진수로 표현하면 1101 인데 '첫번..
초기 아이디어 부분적으로 최단거리를 구하는 문제이므로 DFS, BFS 가 쓰일 것 같다는 생각은 바로 들었는데, 다소 복잡하다. 처음엔 "가장 먼 두 지점" 이라는 말에서 DFS 를 생각했는데 돌아서 가면 안된다는 조건 때문에 결국 가장 먼 지점이라고 해도 BFS 로 풀어내야 한다는 것을 깨달았다. 모든 육지에 대해서 BFS 를 수행하고 가장 멀리까지 갈 수 있는 지점을 계산 해보기로 했다. 문제풀이 1. 모든 두 지점을 순회하면서 BFS #include using namespace std; int n, m; char a[51][51]; int visited[51][51]; int dx[4] = {0, 1, 0, -1}; int dy[4] = {1, 0, -1, 0}; int bfs(int sX, int..
초기 아이디어 최단 거리를 묻는 문제는 우선 직관적으로 DFS, BFS 를 생각할 수 있다. 더 코드가 짧은 DFS 를 하기로 해보고 연습겸 BFS 로도 구현해보기로 한다. 문제 풀이 1. DFS #include using namespace std; int a[101][101]; int visited[101][101]; int n, m, ret=987654321; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; void dfs(int x, int y, int dept){ if(x==n-1 && y==m-1) { ret = ret>dept?dept:ret; return; } for(int i=0;i> n >> m; for(int i=0;i> m; for(in..
파사드 패턴이란? 파사드(Facade)는 '건축물의 외관, 겉면'을 뜻하는 단어로, 프랑스어(façade)에서 건너온 단어이다. 원래 어원은 라틴어에서 얼굴(Face)을 뜻하는 facies(파시에스) 라고 하는데 건출물 외관 = 얼굴 로 이해해볼 수 있다. 디자인 패턴에서 말하는 파사드 패턴은 내부의 코드를 가려놓고 전면에 단순화된 인터페이스를 내세우는 구조가 마치 내부의 인테리어나 구조를 덮어놓은 건축물의 외벽과 유사하다는 데서 차용되었다. 여러 클래스들을 직접 가져와서 쓰게 되면 가독성도 떨어지고 의존관계도 복잡해지니, 하나의 단순화된 클래스를 만들어서 이를 쉽게 이용할 수 있도록 만드는 것이다. 아래 그림과 같이 말이다. 언뜻 듣기에 너무 쉬운 개념이라서 '이걸 따로 배울 필요가 있었나?' 라는 생..
오늘은 너무 유명한 N+1 문제와 이와 관련한 EntityManager 의 getReference 라는 메서드를 이야기 하려고 한다. 사실 N+1 이 발생하는 원인이나 해결책은 간단한데, 조금 애매한 부분이 있어서 혼란을 겪었다. N+1 문제 N+1 문제는 자바 ORM 에서 객체 내부의 연관된 객체에 접근하려고 할때 발생한다. DB에서 객체를 로드해 올때 객체의 필드에 다른 엔티티가 포함되어 있는 경우, ORM 은 해당 엔티티의 정보를 전부 가지고 오지 않는다. (select query 를 생각해보면 당연하다. 연관된 다른 테이블의 자료는 조회해오지 않는다.) 그 대신 객체 행세(?)를 할 수 있는 프록시 객체(위임 객체)를 넣어주는데, 이 프록시 객체는 껍데기만 가지고 있을 뿐이고 변수에 데이터를 가지..
