본문 바로가기

분류 전체보기

 (437)
[백준] 별자리 만들기 (C++) https://www.acmicpc.net/problem/4386 좌표로 주어진 그래프를 노드그래프로 바꾼 후 크루스칼 알고리즘을 사용하면 쉽게 풀리는 문제. 다만 소수점을 주의해야한다. 크루스칼 알고리즘은 유니온 파인드와 그리디를 섞은 최소 스패닝 트리를 구할 수 있는 알고리즘이다. #include#include#include#includeusing namespace std;pair points[101];vector>> edges;bool visited[101];int par[101];int Find(int x) { if(par[x] == x) return par[x]; else return par[x] = Find(par[x]);}void Union(int x, int y){ int ..
[Opic] 오픽 후기 (난이도 3-3 강남 중국어학원) 벌써 내년 3월이 오픽 점수 만료기간이어서 이번에는 좀 더 높은 점수를 목표로 준비하고자 시험을 봤다. 나의 지난 오픽 점수는 IM2.. 솔직히 운이 엄청 좋았다. 난 영어를 개못하기 때문이다. 아무래도 삼성 공채 기간에는 점수를 잘 쳐준다는 속설이 있는데 저번에 그래서 잘나온 것 같다. 시험 장소: 강남 중국어학원이번 시험 장소는 https://naver.me/5UEcNHrc 네이버지도서울공자아카데미 강남중국어학원map.naver.com 저번엔 삼성공채 기간에 시험본거라 사람이 정~말 많았던 걸로 기억하는데 이번엔 내 파트 시간에는 사람이 그렇게 많지는 않았다. 대기공간이 넓지는 않아서 자리가 없어서 처음에 서있었다.그런데 남초딩이 옆자리에 자기 짐을 안치우고 있었더라. 바로 가서 치워달라 하고 차리..
[백준] 17609번 회문 (C++) https://www.acmicpc.net/problem/17609 회문이란?좌우대칭인 문자열을 의미한다. ABAABBA 같은 문자열이 회문이다. 해당 문제는 문자 하나까지는 봐줄 때 회문인지를 판단할 수 있는지를 물어보는 문제이다. 풀이방향1. 회문인지 파악하는 방법문자열의 시작과 끝에서 서로 비교하면서 틀린것이 없다면 회문 (시간복잡도 N) 2. 하나 생략을 하는 방법1번 로직을 진행하다가 하나만 더 진행시키면 된다. 예를들어 ABCBDA 를 하고 있었다면 B(1)와 D(5)가 다를 때, 왼족 인덱스만 1 증가 시키거나 오른쪽 인덱스만 하나 감소 시키면 된다.3. 그렇다면 이것은 같은 방식을 계속 다시 써야할 것 같다.회문파악을 계속하면서 두 값이 다를 때만 인덱스를 변화시키므로 재귀를 돌면 될 것 ..
[백준] 1459번 걷기(C++) https://www.acmicpc.net/problem/1459 오랜만에 PS를 해봤다. 꾸준히 해야되는데 일과 병행하는 것은 정말 쉽지 않다. 최소비용을 구하는 문제이다. 두가지 풀이법이 생각난다. BFS 대각선이동, 좌우이동이 가능한 BFS를 사용하면 예제는 풀릴 것이다. 그러나X와 Y는 1,000,000,000보다 작거나 같은 음이 아닌 정수이고라는 문구를 보고 BFS는 접어야함을 알 수 있다. 왜냐하면 BFS의 시간 복잡도는 행렬그래프에서는 O(M ^(N * N)) 이기 때문이다. (M은 가능한 방향) 즉 여기서는 좌우이동, 대각선이동까지 총 8방향이 가능하기 때문에 시간복잡도가 엄청나게 커진다. Greedy해당 문제는 좌우이동과 대각선의 비용이 다르다. 즉, 0,0 에서 1,1로 이동할 때..
[스프링배치] Chunk vs Tasklet (Chunk는 멀티스레딩이 아닌데 왜 빠를까?) 프로젝트를 진행하다가 Chunk는 멀티스레딩 방식이기 때문에 동시성 문제가 발생할 것이라 생각하여 Tasklet 방식으로 선회하려고 했다. 그런데 chunk방식이나 tasklet 방식이나 싱글쓰레드 방식이라고 한다. 그렇다면 왜 속도차이가 발생하는 것일까? Chunk 방식과 Tasklet 방식에 대해 먼저 살펴본다.데이터 처리 방식Chunk chunk는 spring batch의 가장 일반적인 구현방식으로 데이터를 read하여 각 “chunk”를 만들어내고 프로세스를 수행한 후 write단계에서 저장한다. 좀 더 자세히 표햔하면 위 그림과 같다. ItemRedaer에서 chunk의 크기만큼 데이터를 읽어 Read 하고 Processor 단계에서 비즈니스 로직을 처리한 후 write단계에서 저장한다.즉 ch..
[백준 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일까지 미수수익으로 인식한다.미수금외상 값과 같은 말이다. 내가 서비스를 이미 제공했지만 돈을 받지 못한 금액을 말한다.선수수익서비스(또는 이자 등)를 기간 경과에 따라 제공해야 할 의무가 있는데, 현금을 미리 받았을 때 생기는 부채예컨대 정기구독료·임대료·이자선수수익처럼, ‘수익 발생 조건’을 기간에 걸쳐 충족시켜야 인식대출이자라고 인식되면 수익으로 기록선수금상품을 판매하거나 용역을 제공하기 전, 고객으로부터 현금을 미리 받은 금액아직 ‘수익’으로 인식할 조건(인도·제공)을 충족하지 못했기 때문에 부채로 처리

티스토리툴바