분류 전체보기 (432) 썸네일형 리스트형 [백준 2616번/Java] 소형기관차 https://www.acmicpc.net/problem/2616 [문제 분석] 길이 N의 수열을 M개씩 3개로 묶을 때 최댓값을 구하는 문제이다.[알고리즘]1. 연속된 수열을 가져와야하기 때문에 누적합을 사용하여 시간을 단축한다.2. 이 문제는 결국 모든 경우의 수를 살펴봐야하는데 그것을 얼마나 효율적으로 메모이제이션하느냐에 따라 달려있다. DP[i][j] = i번 열차가 j번 수열까지 도달했을 때 최대 값 이 점화식은 배낭문제에서 아이디어를 가져올 수 있다. 다만 배낭문제는 각 배낭에 각 객체를 넣을 수 있을지 없을지 확인하는데 이것은 연속된 객체를 삽입할지 말지 결정해야하는 다른점이 있다. 그렇다면 점화식은 어떻게 구성해야할까 먼저 예제로 시뮬레이션 해보자. N = 7, M = 235 40 50 .. [백준 2240번] 자두나무 (C++) https://www.acmicpc.net/problem/2240 최댓값을 구하는 문제로 가장 먼저 그리디, 완전탐색, DP가 떠오르는 것이 일반적이다.어떻게 풀 수 있을까? 먼저 최대 자두가 떨어지는 숫자는 1000이고 움직일 수 있는 횟수는 30이다. 1. Greedy탐욕법으로 풀 수 있을까? 탐욕법이 성립하기 위해서는 지금 선택하는 조건이 이후의 선택에 영향을 주어선 안된다.즉, 2번에서 자두가 떨어질 때 이동하여 잡는 이 선택이 뒤에서 영향을 주어선 안되는데 조금만 생각해도 당연히 영향을 줄 수 밖에 없는 구조이다. 그러므로 탐욕법으로는 풀 수 없다.2. 완전탐색완전탐색으로는 정확도만 풀이가 가능하다. 한 지점에서 취할 수 있는 경우의 수는 두가지다. 이동하거나, 가만있거나 그러므로 2^30의 시.. [금융IT] 미수금, 미수수익, 선수금, 선수수익 미수수익고객이 응당일에 원리금을 수납하지 않았을 경우 90일까지 미수수익으로 인식한다.미수금외상 값과 같은 말이다. 내가 서비스를 이미 제공했지만 돈을 받지 못한 금액을 말한다.선수수익서비스(또는 이자 등)를 기간 경과에 따라 제공해야 할 의무가 있는데, 현금을 미리 받았을 때 생기는 부채예컨대 정기구독료·임대료·이자선수수익처럼, ‘수익 발생 조건’을 기간에 걸쳐 충족시켜야 인식대출이자라고 인식되면 수익으로 기록선수금상품을 판매하거나 용역을 제공하기 전, 고객으로부터 현금을 미리 받은 금액아직 ‘수익’으로 인식할 조건(인도·제공)을 충족하지 못했기 때문에 부채로 처리 [백준 2169번] 로봇 조종하기 (C++) https://www.acmicpc.net/problem/2169 꽤 생각할 것이 있는 다이나믹프로그래밍 문제였다. 먼저 이 왜 다이나믹 프로그래밍인가? 1. N이 약 1000으로 백트래킹으로 모든 경우의 수를 다 진행할 시 당연히 시간초과에 걸린다.2. 한 지점에 도착할 수 있는 경우의 수가 정해져있다.3. 2번에 의해 큰 문제를 작은 문제로 쪼갤 수 있다. 이 근거로 다이나믹 프로그래밍이라고 유출할 수 있겠다. 그렇다면 어떻게 풀어야할까? 처음에는 0,0 에서 시작하는 재귀 + DP를 생각했다. 그러나 문제가 있었다. 이 문제는 왼쪽과 오른쪽으로 이동을 할 수 있다. 1 2 34 5 67 8 9 라고 할 때 재귀를 진행하면 1번에서 2번으로 이동하면 2번은 다시 1번으로 이동할 수 있다. 그.. [백준 17298번] 오큰수 (C++) https://www.acmicpc.net/problem/17298 O(N^2)으로 풀면 쉽게 풀리지만 그러면 골드난이도가 아닐 것이다. N이 크기 때문에 O(N) 혹은 O(N Log N)으로 풀어내야한다.어떻게 최적화 할 수 있을까? 2, 9, 10, 2, 11 예제를막대로 그려보면 다음과 같다. 그리고 각 A, B, C, D, E의 꼭대기에서 오른쪽으로 갈 때 가장먼저 부딫히는 막대의 크기를 출력해야하는 문제다. 아하.. 그렇다면 맨 오른쪽에서부터 막대를 새우면서 진행하면 될 것 같다. 1. 11 막대를 새운다.2. 2막대를 새우고 11과 비교한다. 오큰수: 113. 10 막대를 새우고 2와 먼저 비교한다. 앗.. 2보다 10이 더 크다. 즉, 이제 2는 절대로 누군가의 오큰수가 될 가능성이 없다. .. [백준 1949번] 우수 마을 (C++) https://www.acmicpc.net/problem/1949 이전에 비슷한 문제의 유형을 풀어본적이 있기 때문에 트리에서 다이나믹 프로그래밍 문제라는 것을 알 수 있었다. 사실 말은 거창하지만 DFS + DP 와 다를 것이 없다. 문제를 살펴보자 '우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을 모두 '우수 마을'로 선정할 수는 없다. 즉 '우수 마을'끼리는 서로 인접해 있을 수 없다.선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다.뭔가 조건이 많아보이는데 사실 1,2번을 만족하면 3번은 자동으로 될 수밖에 없다... [금융IT] 네트워크 통신 (FEP, MCI, EAI) FEPFront-End Processor의 약자로 주로 내부시스템과 대외계를 연결해주는 전처리 서버이다. 대외계란 우리 금융사가 아닌 금융감독원, 금융결제원, 타 금융사 등을 이야기한다.FEP는 대외계의 전문을 받아 내부 포맷에 맞게 만들어 전송해주는 역할을 수행한다.MCIMulti Channel Integration, MCI는 인터넷뱅킹, 모바일뱅킹, 텔레뱅킹 등 고객 접점 채널의 인터페이스를 통합 관리하는 시스템EAI역할 설명연계API 서버에서 요청한 데이터가 어떤 시스템으로 가야 하는지 라우팅데이터 변환각 시스템마다 요청/응답 포맷이 다르기 때문에 포맷 통일트랜잭션 관리여러 시스템이 동시에 처리되는 요청일 경우 전체 처리 보장로깅/모니터링어떤 시스템에 요청이 갔고 응답이 어떻게 왔는지 추적 가능비동.. [백준 1719번] 택배 (C++) https://www.acmicpc.net/problem/1719 위 그림에서 1번에서 4번으로 가기 위해 최단거리로 이동하는 방법은 3번으로 이동한 후 3번에서 4번으로 이동하는 것이다. 그리고 결과값으로 처음으로 이동한 노드의 번호를 출력하는 것이 문제다. 전체 노드의 개수는 200, 간선의 개수는 10000이므로, 다익스트라알고리즘을 N번한다고 하면 O(N^3) 으로 문제를 해결할 수 있다. 그렇다면 대략적인 알고리즘은 이렇게 될 것이다. 1. 큐에 현재 시작 노드의 이웃 노드들을 집어넣는다.2. 집어넣을 때 현재 시작 노드를 따로 관리하여 만약 다익스트라 DP가 갱신된다면 첫 입력값을 넣어준다. 오 문제가 해결된 것 같다. 코드로 바꿔보면 #include #include #define MAX.. 이전 1 2 3 4 ··· 54 다음
