본문 바로가기

분류 전체보기

 (65)
2022/08/08 (월) 오늘은 백준 11401 이항 계수 3 문제를 풀었다. 암호학 시간에 배웠던 내용이어서 반가웠고 재밌게 풀었던 것 같다. 추가적으로 재귀적으로 함수를 구현하지 않고 shift를 통한 while문으로 구현하는 방식도 고려해서 테스트해볼 생각이다. 토익 단어장 Day 7 진행 respondent 응답자 / monopoly (상품의) 독점, 전매 / appreciate 고맙게 생각하다; 높이 평가하다; 감상하다 / demonstration 설명; 드러냄, 시연 / examine 조사하다 / effective 효과적인; (법률 등이) 발효되는, 시행되는 / closely 면밀히, 엄밀히 / reserve 예약하다, 지정하다; 보존하다 / consecutive 연속적인 / publicize 공표하다; 광고하다, 선..
[백준 11401][C++] 이항 계수 3 문제 https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 과정 이 문제는 중요 포인트가 두 가지 있었다. (1) 분할 정복으로 연산 시간 감소 POW연산을 수행할 때 지수가 최대 4000000까지 입력이 가능하다. 따라서 일반적인 연산으로는 시간 초과가 발생한다. 이를 두배로 적용시켜 분할 정복하는 power 함수를 만들어 해결한다. 2^22 = 4194304의 값을 가진다. 하나씩 곱셈하는 식으로 power 연산을 구현하면 최대 4000000번 수행해야 하는 연산..
2022/08/06 (토) 오늘은 백준 12865 평범한 배낭 문제를 풀었다. 분명히 이전에 학교 수업에서도 배웠었고 다이나믹 프로그래밍 관련 문제를 풀어 봤음에도 오랜만에 풀어보려니까 조금 막막했다. 최근엔 그래프 탐색과 구현, 시뮬레이션 문제들 위주로 풀었어서 다이나믹 프로그래밍의 개념을 적용하는 것이 유연하지 않았었다. 토익 단어장 Day 8 진행 marginal 약간의; 주변의 / agressively 적극적으로 / indicate 보여주다, 나타내다 / absence 부재; 결근, 결석 / means 방법, 수단 / contemporary 동시대의; 현대의, 당대의 / resolve (문제를) 해결하다 / intensify 강화하다, 증대하다, 강렬하게 만들다 / favorably 호의적으로; 순조롭게 / cover 포함..
[백준 12865][C++] 평범한 배낭 문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 과정 이 문제는 다이나믹 프로그래밍하면 가장 대표적인 가방에 무게와 가치가 있는 물건을 최대 가치가 되도록 담는 문제이다. 다이나믹 프로그래밍의 핵심이라고 한다면 이전의 계산을 통해 중복되는 계산을 피하는 것에 있다. 이는 분할 정복과 느낌이 비슷하다. N개의 입력에 의해 발생할 수 있는 가짓수는 2^N 가지이다. DP는..
2022/08/05 (금) 오늘은 백준 23291 어항 정리 문제를 공부했다. 배운 점이 많은 문제와 포스팅이었다... 아직 갈길이 멀다... 토익 단어장 Day 9 진행 stagnant 침체된, 불경기의 / brisk 활발한, 호황의 / soar (물가 등이) 폭등하다, 높이 치솟다 / assert 단언하다, 주장하다 / potential 잠재적인; 가능성 / remain 계속 ~한 상태이다; 아직 ~해야 하다 / costly 비용이 많이 드는, 손실이 큰 / particular 특정한 / drastic 과감한; 급격한 / evenly 고르게, 균등하게 / indicator 지표, 지수 / likely ~할 것 같은 / boom 붐, 호황 / director 임원, 책임자 / substitute 대용품, 대신하다 / fairly..
[백준 23291][C++] 어항 정리 문제 https://www.acmicpc.net/problem/23291 23291번: 어항 정리 마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바 www.acmicpc.net 풀이 과정 해당 문제는 풀이에 실패했다. 따라서 해당 문제에 대한 다른 사람들의 코드를 둘러보게 되었다. 그중 정말 깔끔하고 잘 구현되었다고 생각되는 포스팅의 코드를 살펴보는 식으로 글을 진행할 것이다. https://kimjingo.tistory.com/111 [백준 23291번] 어항 정리(C++ 풀이) https://www.acmicpc.net/problem/23291 23291번: 어..
2022/08/04 (목) 오늘은 백준 23290 마법사 상어와 복제 문제를 풀었다. 부분 부분 실수하는 과정이 있었지만 오히려 더 배울 수 있었던 문제이다. 벡터의 memcpy 사용, std::copy 등등 배울 수 있었다. 토익 단어장 Day 10 진행 installment 할부 / affordable (가격이) 알맞은, 감당할 수 있는 / autehntic 진정한, 진짜의, 진품의 / charge 요금, 청구 금액; 책임, 의무; ~을 청구하다; (외상으로) 달아놓다 / notice 통지, 공고 / instruction 설명, 지시 / exclusdively 오로지, 독점적으로 / description (제품 등의) 설명, 해설 / spare 아끼다, 할애하다; 예비의, 여분의 / clearance 정리, 없애기; 허가 / ..
[백준 23290][C++] 마법사 상어와 복제 문제 https://www.acmicpc.net/problem/23290 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net 풀이 과정 1. 현재 저장되어 있는 물고기들의 상태를 복사한다. (이후 모든 과정을 수행 후 fish_map에 추가) 2. 물고기들을 조건에 맞게 이동시킨다. 3. 상어의 이동할 경로를 DFS를 통해 찾은 후, 이동시킨 상태를 fish_map에 반영한다. 4. 물고기를 먹은 흔적인 냄새를 감소시킨다. 5. 복사했던 물고기들을 fish_map에 추가한다. 6...

티스토리툴바