본문 바로가기

분류 전체보기

 (106)
백준 3055 탈출 - 확산하는 물체가 2개 있을때 bfs를 돌려야 한다면? 문제 링크 www.acmicpc.net/problem/3055 풀이 아이디어 최단경로 문제이므로 당연히 BFS를 이용해서 풀어야 한다. 문제는 확산하는 물체가 고슴도치 1개와 물 n개라는 것이다. 구체적으로 푸는 방식은 여러개가 있을 수 있다. 나는 bfs 함수를 하나만 정의했지만 물이 이동하는 bfs, 고슴도치가 이동하는 bfs 함수를 각각 짜서 비교해보며 진행을 해도 된다. 하지만 각 객체(고슴도치,물) 이 확산하는 정보는 따로 관리가 들어가야 하므로 queue는 2개를 반드시 이용해 주어야 한다. 나는 queue 2개를 이용을 하되, 함수를 하나만 정의 했다. 문제의 조건에 따라 물을 먼저 이동시키고, 그 이후에 고슴도치를 이동시키기. 추가적으로 사용한 2가지 팁은 1. for문을 이용해 큐의 사이..
2020 회고록 누군가 회고록을 쓰는 일은, 기억의 바닷속을 깊이 헤집고 들어가는 일과 똑같기 때문에 누구나 허우적 대고, 어려운 일이라고 한다. 2020년 올 한 해는 이젠 말하기도 듣기도 지겨울 정도로, 다사다난한 해였다. 우리는 외부적인 요인에 의해 사회적 교류를 단절된 채로 1년의 대부분을 보내야 했다. 올해 에른스트 디터 란터만의 ‘불안사회’라는 책을 인상깊게 읽었었는데, 현대인들은 급변하는 사회를 자기 확신의 세계와 ‘싱크’를 맞추지 못하는 현상을 불안의 주 원인으로 꼽았다. 본인의 삶의 페이스, 양식을 뺏긴 채 무기력 해지는 현상이 고작 질병 하나 때문이라는 사실이 나도 싫었고, 개인적으로는 외부와 단절된 환경 속에서 보낸 1년이 너무나도 답답했다. 평소에도 나는 사람들과의 대화를 통해 의견을 듣고, 거기서..
백준 19236 청소년 상어 : 내가 했던 4가지 놓친 점들과 함께 문제 링크 www.acmicpc.net/problem/19236 풀이 아이디어 사실 풀이 아이디어는 간단했다. 4*4의 제한된 공간과 가능한 경우 중 최댓값을 찾는 문제. 완전 탐색이다. 문제에서 말하고 있는 대로, 상어를 이동시키기 전 물고기들을 전부 이동시킨 후, 이동할 수 있는 상어를 백트래킹을 통해 탐색하면 되는 문제였다. 나는 이 문제를 풀면서 몇 가지 실수들을 했었는데, 우선 최종 solved 받은 코드를 보고 이야기를 해보겠다. 코드 #include using namespace std; int fisharr[4][4]; int dirarr[4][4]; int answer=0; int dx[8] = {0,-1,-1,-1,0,1,1,1}; int dy[8] = {-1,-1,0,1,1,1,0,-1..
201119 겨울방학때 다시 공부할 알고리즘 리스트 - 위상정렬 - 우선순위 큐를 활용한 다익스트라 - disjoint set - 트리 DP - 구현 까다로운 bfs dfs 문제들(삼성 역테) - 트라이 자료구조 프로젝트들 때문에 바쁘지만 결국은 알고리즘이 중요하다. 마감되는 대로 위 알고리즘들 우선적으로 공부 다시/새로 하고, 꾸준히 공부해 나갈 것.
인턴생활 절반을 넘겨가는 요즘의 회고 일기 운좋게 시작한 인턴생활 3주차가 끝나고, 4주차에 접어들었다. 회사생활은 어느정도 적응을 했고, 프로젝트 마무리와 최종 발표 정도만을 남겨놓고 있다. 어디에서 인턴하는지, 인턴생활은 어떠했는지(아마 회사보안때문에 자세히 쓰진 못할 것 같다.) 는 나중에 인턴생활이 끝나고 찬찬히 써보도록 하겠다. 하여튼 지금 쓰고 있는 회고록은, 인턴생활 도중에 내가 느낀 날것의 느낀 점들을 후딱 적기 위해서 또 오랜만에 블로그를 들어오게 되었다. 블로그도 자주자주 쓰도록 노력하겠다. 1. 평일에 퇴근하고 늘어져라 쉰다고 피로가 회복되진 않더라. - 첫 1주일은 퇴근 후 할 것도 별로 없었고, 수면패턴에 적응하느라 집에 오자마자 거의 그냥 뻗어서 자기만 했던 것 같다. 그에 비해 2,3주차는 퇴근 후에 항상 뭔가 할 일들..
AReal 1 - image captioning 서버 환경설정 우리 프로젝트에서는 image captioning(사진을 설명 가능한 영어 문장으로 바꿔주는) 기능을 할 수 있는 인공지능 모델을 돌릴 서버가 필요했다. AWS EC2 서버를 한 대 구축 한 후 가장 먼저 할 일은 torch를 서버에 인스톨 하는 것이었다. $home 디렉토리에다가 다음과 같이 단 세줄만 입력하면 되는 작업이지만.. $ git clone https://github.com/torch/distro.git ~/torch --recursive $ cd ~/torch; bash install-deps; $ ./install.sh 2번째 줄에서 bash install-deps를 실행하려고 할 때 실패했다. Torch를 설치하기 위한 '의존 파일' 들을 설치하기 위한 bash script였는데, ht..
2020년 상반기 회고록 처음으로 상반기의 회고록을 적어 보고자 한다. 갑갑한 마음이 들기도 했고 생각 정리가 잘 안되는 느낌이 들어서 ‘조만간 회고록이나 한번 써봐야지’ 했던게 오늘이 된 모양이다. 퍼뜩 정신을 차려보니 텅 빈 워드 파일에 이걸 쓰고 있다. 결론부터 말하면 상반기는 ‘나 빼고 주변 다 잘된’ 6개월이다. 동생도 자랑스럽게 이 시국을 뚫고 취업에 성공했고, 주위 친한 친구들도 좋은 일이 터지는 경우가 많이 있었다. 반면 나는 올해부터 준비한 취준전선에서 완벽한 패배를 경험하고, 멘탈이 나가지는 않았지만 약간 지쳐있는 상태인건 사실인 것 같다. 지난 학기에 개발자 루트로 취준을 준비해야 겠다고 다짐하면서 올해 1월부터 알고리즘 공부를 시작했다. 1월 한달 동안은 정말 빡세게 알고리즘+조교일+오픽 준비를 했고 2월엔..
백준 1972 놀라운 문자열 - substr로 해결못하는 문자열 처리 문제 문제 링크 https://www.acmicpc.net/problem/1972 1972번: 놀라운 문자열 문제 대문자 알파벳으로만 이루어져 있는 문자열이 있다. 이 문자열에 대해서 ‘D-쌍’이라는 것을 정의할 수 있는데, 이 문자열에 포함되어 있는, 거리가 D인 두 문자를 순서대로 나열한 것을 �� www.acmicpc.net 종강 기념으로 다시 알고리즘 시작한다! 길고 긴 학기였다... 해결 아이디어 문자열 처리 문제이다. 각 case에 대해 1부터 len-1 까지, 처음부터 끝까지 검사하고 , set를 이용해 하나도 겹치지 않고 나오는지 개수를 파악해서 검사했다. 총 n^3의 시간복잡도가 사용되겠지만 case수가 100개가 최대이므로 시간내에 돌아간다. 코드 #include using namespace..

티스토리툴바