알고리즘 문제풀이
-
백준
백준 9470 Strahler 순서 - 노드마다 count를 세야하는 위상정렬 문제
문제 링크 www.acmicpc.net/problem/9470 9470번: Strahler 순서 지질학에서 하천계는 유향그래프로 나타낼 수 있다. 강은 간선으로 나타내며, 물이 흐르는 방향이 간선의 방향이 된다. 노드는 호수나 샘처럼 강이 시작하는 곳, 강이 합쳐지거나 나누어지는 곳 www.acmicpc.net 풀이 아이디어 (처음 틀린 방식) 오랜만에 푸는 위상정렬 문제였다. 본인은 이 문제를 2번이나 틀리고 3번째만에 맞추게 되었는데, 2번씩이나 틀린 이유는 이 문제를 노드마다 count를 안 세고 야매로 풀려다가 된통 당했기 때문이다. 맨처음 틀린 접근 방식은 다음과 같다. 위상정렬로 순서대로 접근하는 건 다른 문제들과 똑같은 방식이니 패스하겠다. 처음에 int cost[1001]을 잡고, 해당 노..
-
백준
백준 2638 치즈 - 여러번 bfs를 돌려야하는 문제
문제 링크 www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 풀이 아이디어 문제를 풀기 위해 핵심적으로 파악해야 하는 여부가 '치즈가 외부 공기와 2군데 이상 닿아 있는지 여부를 확인하자' 이다. 치즈가 전부 녹아 없어질때까지 이 여부를 확인해보면서 진행 해야한다. 주의할 것이 내부 공기는 외부 공기가 아니므로, 단순히 치즈 주변이 0으로 둘러 쌓여 있는가를 가지고 판단하면 안된다. 확실한 외부 공기로부터 bfs를 통해 치즈가 외부 공기와 닿아있는지 ..
-
프로그래머스
[프로그래머스] 2021 카카오공채 7번 매출하락 최소화-가장 쉽게 트리 dp로 푸는법, 쉬운설명
문제 링크 programmers.co.kr/learn/courses/30/lessons/72416 코딩테스트 연습 - 매출 하락 최소화 CEO를 포함하여 모든 직원은 팀장 또는 팀원이라는 직위를 가지고 있으며 그림에서는 팀장과 팀원의 관계를 화살표로 표시하고 있습니다. 화살표가 시작되는 쪽의 직원은 팀장, 화살표를 받는 programmers.co.kr 풀이 아이디어 우선 트리dp의 기본적인 풀이 방법을 알고 있다고 가정하고 작성한다. 해당 유형을 안풀어 봤을 때 hqjang.tistory.com/104?category=913845 를 참고할 것. 풀이의 핵심은 한 그룹에서 '최소 한명' 이 워크숍에 참석해야 한다는 것이다. 따라서 케이스는 두가지로 나뉜다. 1. 그룹장이 워크숍에 참석하는 경우 -dp[n..
주인장 생각
-
thoughts
2021 회고록
회고록을 약 4년째 쓰면서, 쓸때마다 ‘내가 왜 회고록을 쓰는가’ 에 대해서 생각했던거 같다. 처음 회고록을 쓸때는 한 해를 돌이켜보고, 있었던 일을 돌이켜보며 앞으로 나아가야 할 방향, 목표를 잡고 마음가짐을 새로 다잡는 마음가짐을 가지고 썼었다면 지금은 미래의 내가 과거의 나의 생각을 알기 위한 하나의 참고자료를 남긴다는 느낌으로 쓰려고 한다. 결국 회고록도 글이고, 다른 누군가(혹은 미래의 나)가 이 글을 보고 나서 이때 이사람은 이런 마음가짐으로 살았구나~ 라는 정도로만 기록이 되면 충분한 것 같다. ‘아 올해 이런게 부족했으니.. 내년에는 이렇게 살아서 이런 사람이 되어야지’ 라고 굳게 다짐하던 내 모습이, 몇년 후에봤을때는 크게 의미없는 고민이었구나를 이전 회고록을 읽으면서 많이 느꼈었다. 오..
-
thoughts
[펌] 데브옵스 엔지니어가 공부해야 하는 것?
brunch.co.kr/@topasvga/1385 69.DevOps 엔지니어가 공부해야 하는것? DevOps 엔지니어가 공부해야 하는것? Cloud Linux AWS cloud formation Ansible Terraform Git IT Infra전문가 되기 네트워크 이해하기 이미지 출처 : https://cordelia273.space/7 Cloud 1. 구글 brunch.co.kr
-
thoughts
2020 회고록
누군가 회고록을 쓰는 일은, 기억의 바닷속을 깊이 헤집고 들어가는 일과 똑같기 때문에 누구나 허우적 대고, 어려운 일이라고 한다. 2020년 올 한 해는 이젠 말하기도 듣기도 지겨울 정도로, 다사다난한 해였다. 우리는 외부적인 요인에 의해 사회적 교류를 단절된 채로 1년의 대부분을 보내야 했다. 올해 에른스트 디터 란터만의 ‘불안사회’라는 책을 인상깊게 읽었었는데, 현대인들은 급변하는 사회를 자기 확신의 세계와 ‘싱크’를 맞추지 못하는 현상을 불안의 주 원인으로 꼽았다. 본인의 삶의 페이스, 양식을 뺏긴 채 무기력 해지는 현상이 고작 질병 하나 때문이라는 사실이 나도 싫었고, 개인적으로는 외부와 단절된 환경 속에서 보낸 1년이 너무나도 답답했다. 평소에도 나는 사람들과의 대화를 통해 의견을 듣고, 거기서..
-
thoughts
인턴생활 절반을 넘겨가는 요즘의 회고 일기
운좋게 시작한 인턴생활 3주차가 끝나고, 4주차에 접어들었다. 회사생활은 어느정도 적응을 했고, 프로젝트 마무리와 최종 발표 정도만을 남겨놓고 있다. 어디에서 인턴하는지, 인턴생활은 어떠했는지(아마 회사보안때문에 자세히 쓰진 못할 것 같다.) 는 나중에 인턴생활이 끝나고 찬찬히 써보도록 하겠다. 하여튼 지금 쓰고 있는 회고록은, 인턴생활 도중에 내가 느낀 날것의 느낀 점들을 후딱 적기 위해서 또 오랜만에 블로그를 들어오게 되었다. 블로그도 자주자주 쓰도록 노력하겠다. 1. 평일에 퇴근하고 늘어져라 쉰다고 피로가 회복되진 않더라. - 첫 1주일은 퇴근 후 할 것도 별로 없었고, 수면패턴에 적응하느라 집에 오자마자 거의 그냥 뻗어서 자기만 했던 것 같다. 그에 비해 2,3주차는 퇴근 후에 항상 뭔가 할 일들..
-
thoughts
2020년 상반기 회고록
처음으로 상반기의 회고록을 적어 보고자 한다. 갑갑한 마음이 들기도 했고 생각 정리가 잘 안되는 느낌이 들어서 ‘조만간 회고록이나 한번 써봐야지’ 했던게 오늘이 된 모양이다. 퍼뜩 정신을 차려보니 텅 빈 워드 파일에 이걸 쓰고 있다. 결론부터 말하면 상반기는 ‘나 빼고 주변 다 잘된’ 6개월이다. 동생도 자랑스럽게 이 시국을 뚫고 취업에 성공했고, 주위 친한 친구들도 좋은 일이 터지는 경우가 많이 있었다. 반면 나는 올해부터 준비한 취준전선에서 완벽한 패배를 경험하고, 멘탈이 나가지는 않았지만 약간 지쳐있는 상태인건 사실인 것 같다. 지난 학기에 개발자 루트로 취준을 준비해야 겠다고 다짐하면서 올해 1월부터 알고리즘 공부를 시작했다. 1월 한달 동안은 정말 빡세게 알고리즘+조교일+오픽 준비를 했고 2월엔..
