본문 바로가기
  • 실행력이 모든걸 결정한다
반응형

분류 전체보기580

[그리디] 튜플 - 2019 카카오 개발자 겨울 인턴십 해결 방법 Step1) 문자열을 파싱하여 각 집합을 벡터 v로 만들고, 벡터 v들로 이루어진 2차원 벡터 allv를 구성한다. Step2) allv의 v들을 크기가 작은 순으로 정렬한다. allv를 구성하는 벡터들의 크기는 순서대로 1, 2, 3, ..., allv.size()가 될 것이다. Step3) allv의 마지막 벡터를 이용하여 각 요소의 개수를 카운트 한다. Step4) allv의 n번째 벡터에서 카운트(element_cnt)가 0이 아닌 요소를 answer의 n번째 요소로 넣고, 해당 요소의 카운트를 1 감소시키는 작업을 allv의 첫 번째 벡터부터 수행한다. Step4 예시 {{1}, {2, 1}, {1, 2, 2}, {4, 1, 2, 2}} -> 요소를 카운트해보면 1은 1개, 2는 2개.. 2022. 4. 10.
[DFS] 불량 사용자 - 2019 카카오 개발자 겨울 인턴십 경우의 수를 구하는 유형의 문제는 DFS 또는 DP 문제일 확률이 높다. 경우의 수를 조합이나 순열같은 수식으로 해결해보려고 시도해보았지만 꽤 복잡해서 DFS로 풀기로 결정했다. 해결 방법 먼저, banned_id의 1번째 id와 매칭 가능한 user_id가 있는지 확인해서 매칭 가능한 user_id를 발견했다면 save 벡터에 해당 user_id를 저장해둔다. 그리고 이후의 banned_id들에 대해서도 동일한 과정을 반복하여 모든 banned_id가 매칭되었다면 하나의 경우가 완성된 것이다. 이 때의 save 정보를 다른 벡터에 저장해놓고 DFS를 이어서 수행해주면 된다. 조건에 맞는 모든 경우들을 모두 저장했다면 중복되는 아이디 목록을 최종적으로 제거해주고 남은 경우의 수를 구하면 문제가 해결된다... 2022. 4. 5.
[DFS] 다단계 칫솔 판매 - 2021 Dev-Matching 난이도가 Level3인 것 치고는 쉽게 해결한 것 같다. 이 문제는 DFS로 해결할 수 있으며, 분배금을 10% 떼어내고 남은 몫은 자신이 가지고 다음 노드(인원)에게 10%의 분배금을 전달하는 과정을 반복하면 된다. 그리고 일일이 간선을 연결하는 과정 없이 map을 활용하여 간단히 DFS를 수행할 수 있다. 주의할 점이 있다면, 분배금이 1원 미만일 때에도 DFS를 진행하면 시간초과가 난다. 그래서 반드시 분배금이 있을 때만 DFS 함수를 호출해야 한다. 소스 코드 #include #include using namespace std; map mres; map mref; vector answer; void distribute(string seller, int money) { if(seller=="-") .. 2022. 4. 3.
[Spring] 여러 AOP 및 트랜잭션 기법들 1. AOP란? Aspect Oriented Programming - 애플리케이션에 흩어져 있는 부가적인 공통 기능들을 독립적으로 모듈화하는 프로그래밍 모델이다. Aspect는 핵심기능에 부가되는 모듈을 의미한다. - 핵심 기능과 공통 기능을 분리 시켜놓고, 핵심 기능들 중에서 공통 기능을 필요로 하는 것이 있을 때 사용된다. 핵심 기능은 프로그램의 특정 목적에 대해 사용되는 기능이고, 공통 기능은 일반 연산처럼 다양한 프로그램들에서 공통적으로 사용되는 기능이다. 2. 비즈니스 로직과 트랜잭션의 분리 1) 원리 - 비즈니스 로직과 트랜잭션 코드를 분리할 때, 동일한 인터페이스를 상속하는 트랜잭션용 구현체를 만들면 된다. - 아래 코드처럼 UserServiceTx의 트랜잭션 메소드 안에서 UserServi.. 2022. 4. 1.
[이분 탐색] 징검다리 건너기 - 2019 카카오 개발자 겨울 인턴십 코딩테스트 문제가 이분 탐색 문제인지를 확인할 수 있는 꼼수가 있다. 그것은 주어진 값의 범위를 확인하는 것이다. 이 문제는 주어진 범위를 아무리 잘 조합해봐도 복잡도가 터무니없는 수(억 단위)가 나온다. 보통 코딩테스트에서 효율성을 따질 때 최대 복잡도가 억 단위 이상이 나오면 거의 실패한다. 이분 탐색은 값을 미리 가정하고 푸는 알고리즘이다. 처음으로 가정하고 싶은 값은 어떠한 값을 골라도 상관이 없지만 보통 중간값을 선택한다. 해결 방법 중간값을 m으로 지정했다면 m명이 모두 징검다리를 건널 수 있는지를 체크해야 한다. m명이 모두 건널 수 없다면 m명 이상인 경우는 전부 건널 수 없다는 뜻이므로 범위의 최댓값을 m-1명으로 지정하고, m명이 모두 건널 수 있다면 범위는 m명~2억명 사이에 있다는 .. 2022. 3. 29.
[시뮬레이션] 행렬 테두리 회전하기 - 2021 Dev-Matching 해결 방법 단순한 시뮬레이션 문제지만 한 가지 주의할 점이 있다. 그것은 칸에 있는 숫자를 저장하는 변수가 하나 필요하다는 것인데, 칸에 있는 숫자를 기억하지 않고 이동해버리면 값이 덮어 씌워져서 데이터가 날아가버릴 수 있기 때문이다. 그래서 현재의 좌표에 있는 숫자를 저장해뒀다가 다음 칸에 넣을 수 있는 save라는 변수를 하나 추가했다. 그리고 회전의 경우에는 상하좌우 4개의 테두리를 지나는 상황으로 나눠서 반복문을 수행했다. 각 반복문은 각 꼭짓점 사이에서 수행되는 것이다. 소스 코드 #include using namespace std; vector v; int rotate(vector query) { int mini=10001; int x, y; // 현재 좌표 저장 int save; // 현재 .. 2022. 3. 27.
[Spring] 트랜잭션 추상화 트랜잭션의 기본 개념을 설명한 포스팅을 첨부했으니 필요하다면 참고하길 바란다. https://kimcoder.tistory.com/242 [Spring] JDBC 트랜잭션 1. 개념 트랜잭션의 개념을 이해하기 전에 COMMIT과 ROLLBACK이 무엇인지 알 필요가 있다. COMMIT : 변경된 내용을 모두 영구적으로 저장하는 명령어 ROLLBACK : 문제가 발생 했을 때, 이전에 COMMIT 했던 시 kimcoder.tistory.com 1. 트랜잭션 추상화란? - 트랜잭션 추상화는 JDBC, JTA, Hibernate, JPA 등과 같이 트랜잭션의 개념을 갖는 여러 기술들에 독립적인 구조를 가지게 하기 위한 방법이다. 즉, 트랜잭션 기술의 공통점을 담은 것이다. - 아래 그림처럼 트랜잭션 기술마다 .. 2022. 3. 27.
[투 포인터] 보석 쇼핑 - 2020 카카오 인턴십 gems 배열의 크기는 최대 100000이기 때문에 O(n^2) 이상의 알고리즘으로는 효율성에서 통과하지 못할 것이다. 즉, 구간의 왼쪽과 오른쪽 끝점을 조절해가며 해답을 찾는 투 포인터 알고리즘이 필요하다. 해결 방식을 그림으로 표현하면 이렇다. 모든 보석의 종류를 포함하는 첫 구간(0부터 시작)을 기준으로 투 포인트 알고리즘을 수행하면 되는 방식이다. 왼쪽 끝점은 이동할 수 있는 만큼 이동하고 오른쪽 끝점은 1만큼 이동하는 과정을 반복했고, 각 과정이 끝날 때마다 구간의 길이가 최솟값이면 벡터에 저장했다. 왼쪽 끝점에 있는 보석이 구간에 단 1개만 있는 상태에서 왼쪽 끝점을 이동해버리면 그 구간은 모든 보석의 종류를 포함할 수 없게 된다. 반대로, 왼쪽 끝점에 있는 보석이 구간에 여러개가 있다면 왼쪽.. 2022. 3. 20.
[Spring] 예외처리 전략 1. 일반적인 예외 처리 방법 1) 예외 복구 - 예외 상황에 대한 문제를 해결해서 정상적인 작업 흐름으로 돌아오게 하는 방법이다. - 사용자에게 다른 접근 방법을 안내하거나, 정해진 횟수만큼 작업을 재시도하도록 처리하는 경우가 대표적인 사례다. 2) 예외 회피 - 예외처리를 자신이 담당하지 않고 throws 또는 throw문을 통해 자신을 호출한 쪽으로 던져버리는 방법이다. - 예외 회피를 너무 남발하면 예외의 위치와 종류를 찾기 힘들어질 수 있다. - 예외 회피를 사용할 때는 자신을 호출한 쪽에서 예외를 다루는 것이 최선의 방법이라는 확신이 있어야 한다. public void task() throws SQLException { try { ... } catch(SQLException e) { // 로그.. 2022. 3. 20.

티스토리툴바