고인물을 지양하는 블로그

https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 기존 조합 문제에서 한 레벨 위의 문제라 할 수 있는데.. 크게 두 가지 부분에서 그렇다. 1) 일단 nCm 에서 n과m의 범위가 100으로 매우 크다. 2) long long을 쓰더라도 100C50의 결과값을 저장할 수 없다. 따라서 DP를 이용해 큰 수의 조합을 구하고, String을 이용해 결과값을 저장해 해결했다. string Add(string a, string b) { string ans; long long sum = 0; while(!a.empty() || !b.empty() || sum) { if(..

둘 다 Sliding Window를 이용해 패킷을 전송하는 방식으로, 쪼개진 데이터가 다시 합쳐졌을 때 보낸 그대로(in order) 해석 될 수 있도록 보장한다. 또한 두 ARQ 모두 Pipelining을 통해 N개(Window Size만큼)의 패킷이 ACK 없이 receiver로 전달될 수 있다. (오해의 소지가 있으므로 아래에서 다시 풀어서 설명하도록 하겠다.) 두 프로토콜의 속성을 간단하게 살펴보면 다음과 같다. Go-Back-N (GBN) Sender는 크기가 N인 Window, Window의 시작점인 Window Base, 다음에 보낼 프레임 번호인 Sequence number(이하 보낼 Seq#), 세 가지로 구성된다. Receiver는 이번에 받을 프레임 번호를 나타내는 Next Seque..

어쩌다가 첫 코딩대회 출제를 맡게 된 이야기. 학교도 외진곳에 있는데, 작년 까지만 하더라도 그렇다 할 교내 행사가 공대 학술제가 다였다. 그나마 작년부터 마이크로소프트 스튜던트 파트너에서 Azure 관련 세션을 진행한게 전부였을 정도로 정말 아무것도 없었다. 그러던 중 올해 SW 중심대학 막차를 타게돼 DSC & 소프트웨어중심대학사업단 주관으로 처음! 코딩페스티벌 (aka 알고리즘 대회)를 개최한다는 소식을 10월 말경 듣게됐다. (그땐 몰랐지..) 그러던 중 교수님이 부르셔 연구실로 갔더니 같이 코딩페스티벌 준비를 해보는 것이 어떻겠냐고 권유하셔 별 생각 없이 준비하게 되었다. 첫 대회라 얼마나 올지 몰라 두 트랙 합쳐 총 100명이라는 꽤 큰 목표를 잡았는데, 생각보다 그 반응이 뜨거워 106명이나..

https://m.blog.naver.com/drvoss/20207977991 유용한 전처리기 살펴보기 전처리기를 모르는 개발자는 없을 것이다. 그러나 주변을 둘러보면 유용한 전처리기를 전체적으로 파악하고... blog.naver.com

근황에 관심 있는 사람은 없지만, 추억팔이 용도로 적어본다. 학기 초만 하더라도 알고리즘 1일 1솔, 스칼라 공부 등 거창한 계획을 세워뒀지만, 예상을 훠얼씬 뛰어넘게 바쁘고 감사하게도 1회 알고리즘 문제 출제를 떠맡게 돼 유래없이 바쁜 한 학기를 보내고 있다. 특히 이번/저번주는 과제와 문제 선정과 조교 업무 과제 자료 만들기, TC 만들기 등등등..으로 지난 2주가 어떻게 지나갔는지 전혀 기억이 나지 않을 정도로 바빴는데, 그래도 이번주는 운동갈 시간, 짬내서 알고리즘 풀 시간은 있어서 행복한것같다. 체감상 한 학기가 이렇게 빨리 지나간건 처음인데, 이게 하나도 한게 없다는 반증인지 아니면 바쁘게 살았다는 증거인지 잘 모르겠다.

없는 시간 쪼개서 팀원들과 주 1~3회 만남을 가지고 기출 풀어보는 시간을 가졌지만, 프로그래밍 스타일을 비슷하게 맞치기에는 부족한 시간이었고, 각자 컴퓨터로 연습하던 때와 컴퓨터 한 대로 문제를 풀어내야하는 대회는 정말 많이 달랐다. 특별히 긴장하지는 않았지만, 예상했던것만큼 문제가 잘 풀리지 않아 시간이 지나면 지날수록 더 초조해지고, 마음만 급해졌다. 올해 예선에서는 온라인 저지 오류로 스코어보드 보고 전략을 짤 수 있는 기회가 거의 없었는데, 사실 스코어보드 오류가 아니었어도 쉬운 문제들만 제출하고 막혀서 전혀 진도가 안나가는 상황이었지만 그래도 아쉬웠다. 비교적 쉬웠던 2017, 2018 문제 난이도 기준, 6~7 문제를 목표로 잡았었는데 한참 모자라는 5문제 제출, 3솔로 마무리했다. 제출 문..

이 또한 방학 때 교수님께서 알려주신 알고리즘으로, 모든 가능한 순열을 생성해본다. https://yunjae-gong.tistory.com/29 Brute Force: 조합 N개의 수가 주어졌을 때. 그중에서 K개를 뽑는 경우 혹은 그 수를 구할 때, 다음과 같은 방법을 이용해 구할 수 있다. 순서는 조합에서 의미가 없으므로, 크게 i를 사용하는 경우, 사용하지 않는 경우 혹은 다른.. yunjae-gong.tistory.com 조합 알고리즘은 i번째 원소로 n을 채택할지 하지 않을지 재귀적으로 함수를 호출해 해결했다. 순열 알고리즘의 경우, N개중 K개를 뽑아 나열해야 하므로, 추가로 각 원소의 위치를 바꿔주는 동작이 추가된다. inline void swap(int &a, int &b) { int t..

N개의 수가 주어졌을 때. 그중에서 K개를 뽑는 경우 혹은 그 수를 구할 때, 다음과 같은 방법을 이용해 구할 수 있다. 순서는 조합에서 의미가 없으므로, 크게 i를 사용하는 경우, 사용하지 않는 경우 혹은 다른 말로 i번째 수로 m을 사용하는 경우, 사용하지 않는 경우로 나누어 생각할 수 있다. 1. 1~N까지 N개의 수 중에서, K개를 뽑는 경우 2. 입력된 N개의 수 중에서. K개를 뽑는 경우 두 가지 경우에 대해 다뤄보겠다. 코드_1 #include int N,K, cnt=0; void Combination (int c[], int i, int n) { if(i