Categories

  1. /Frontend/Upgrade-Blog

    Upgrade Blog

    Upgrade Blog 블로그를 업그레이드 할 때가 온 것 같다. 블로그를 처음 만들때는 9개월 전인 2020년 6월이고, 2020년쯤에 프론트엔드 직군으로 개발 및 진로 방향을 정했고 그때 당시에는 재학 중이였기 때문에 거의 시작한지 3개월 쯤 되는 정말 뉴비의 실력으로 만들었었다. 기술스택을 하나하나 살펴보며 장단점을 비교해 만들기에는 실력이 부족했고…
  2. /Frontend/Javascript-this

    자바스크립트: this 키워드의 의미는 무엇일까?

    자바스크립트: this 키워드의 의미는 무엇일까? 2021년 3월 8일에 web.dev에 Jake Archibald님이 올린 글을 번역한 것입니다. JavaScript: What is the meaning of this? 자바스크립트의 는 되게 복잡한 키워드이기 때문에, 다양한 개발자 개그의 밈으로 주로 쓰이곤 합니다. 그래서 그런진 몰라도, 개발자들이 …
  3. /Frontend/Rollup-Typescript-Storybook-Design-System

    Rollup.js + Typescript + Storybook으로 디자인 시스템 구축하기

    Rollup.js + Typescript + Storybook으로 디자인 시스템 구축하기 본 포스트는 다음 포스트들을 참고하여 작성되었습니다. 자세하거나 추가적인 지식을 얻고자 하는 분은 다음 포스트를 함께 보시는 것을 추천드립니다. Ideveloper님의 Rollup.js + Typescript + Storybook으로 구축하는 디자인 시스템 velo…
  4. /2020-2R/Computer-Networking-6

    Computer Networking - Lecture 6

    컴퓨터 네트워크 6강 Application Layer P2P file distribution (P2P) 항상 켜져 있는 기반구조 서버에 최소한(또는 거의 안함)으로 의존한다. → 간헐적으로 연결되는 (Intermittently connected) 호스트 쌍 (peer) 이 직접 통신한다. No always-on server Arbitrary end sys…
  5. /2020-2R/Computer-Networking-3to5

    Computer Networking - Lecture 3~5

    컴퓨터 네트워크 3 ~ 5강 2020-2R 고려대학교 주창희 교수님 컴퓨터네트워크 교재 : Computer Networking: A top-down approach 20200907 애플리케이션 계층 Application Layer 네트워크 애플리케이션을 개발 할 때는 여러 종단 시스템에서 실행되는 소프트웨어를 작성해야 한다. 네트워크 코어 장비는 네트워크…
  6. /ML/python-keras-ML-2

    파이썬과 케라스로 배우는 강화학습 D+2

    본 노트는 교재 "파이썬과 케라스로 배우는 강화학습"을 공부하며 만든 필기입니다. 강화학습 기초 2 : 그리드월드와 DP 다이나믹 프로그래밍 DP 작은 문제가 큰 문제 안에 중첩되어 있는 경우, 작은 문제의 답을 다른 작은 문제에 이용함으로써 효율적으로 계산하는 방법 DP로 벨만 기대 방정식 풀기 → 정책 이터레이션 Policy Iteration DP로 …
  7. /Project/HellSolver-1

    Helltaker C++ API (HellSolver) Code Review

    HellSolver Code Review 2020년 9월 7일쯤에 시작한 헬테이커 C++ API 구현은 4일이 지난 11일쯤에 최종 PR을 넣을 수 있을 정도로 완성되었다. 첫 C++ 프로젝트였고, 찬호형이 코드 리뷰를 해준 덕분에 여러가지 중요한 것들을 알게 되었고 리마인드의 필요성을 느꼈기에 이렇게 포스트로 쓴다. 소중한 시간 내어 코드를 고쳐준 옥찬…
  8. /2020-2R/Computer-Networking-2

    Computer Networking - Lecture 2

    컴퓨터 네트워크 2강 2020-2R 고려대학교 주창희 교수님 컴퓨터네트워크 교재 : Computer Networking: A top-down approach 20200907 손실과 지연 패킷은 한 호스트에서 시작하고 일련의 라우터들을 통과하며 다른 호스트에서 끝난다. 경로의 각 노드를 따라 전달되기 때문에 각 노드에서 다양한 지연을 겪게 된다. 노…
  9. /2020-2R/Computer-Networking-1

    Computer Networking - Lecture 1

    컴퓨터 네트워크 1강 2020-2R 고려대학교 주창희 교수님 컴퓨터네트워크 교재 : Computer Networking: A top-down approach 20200903 구성요소로 본 인터넷 컴퓨터 네트워크 → 호스트 혹은 종단 시스템 End system 이라는 이름을 가진 장치들이 연결되어 있는 것. 호스트 혹은 종단 시스템 → 통신 링크와 패킷…
  10. /2020-2R/Computer-Organization-1

    Computer Organization and Design - Chapter 1

    컴퓨터구조 - 1장 2020-2R 고려대학교 정성우 교수님 컴퓨터구조 교재 : Computer Organization and Design 20200901 ~ 20200910 성능 컴퓨터 사용자 개인의 입장 응답시간 Response time = 작업 개시에서 종료까지의 시간 = 실행시간 Execution time 이 중요하다. 데이터센터 관리자의 입장 처리…
  11. /ML/python-keras-ML-1

    파이썬과 케라스로 배우는 강화학습 D+1

    본 노트는 교재 "파이썬과 케라스로 배우는 강화학습"을 공부하며 만든 필기입니다. 강화학습 개요 강화학습의 개념 "강화" = "시행착오" 머신러닝Machine Learning = 지도학습Supervised + 비지도학습Unsupervised + 강화학습Reinforcement 지도학습 → 정답이 있는 데이터 (label이 있는 데이터) 를 이용해서 자신…
  12. /BOJ/5651

    백준 #5651 완전 중요한 간선

    BOJ #5651 - 완전 중요한 간선 https://www.acmicpc.net/problem/5651 # 문제 분류 최대 유량 풀이 접근 방법 crucial path인 경우에는 max flow일 때 flow를 통해 다른 간선을 이용, 서로 만나는 것이 불가능함.
  13. /BOJ/17412

    백준 #17412 도시 왕복하기 1

    BOJ #17412 - 도시 왕복하기 1 https://www.acmicpc.net/problem/17412 # 문제 분류 최대 유량 풀이 접근 방법 최대 유량을 사용하면 되는 문제이다.
  14. /BOJ/2188

    백준 #2188 축사 배정

    BOJ #2188 - 축사 배정 https://www.acmicpc.net/problem/2188 # 문제 분류 이분 매칭 OR 최대 유량 풀이 접근 방법 이분 매칭으로 풀 수도 있다는데 이분 매칭을 몰라서 최대 유량으로 접근했다. kks227 블로그에 잘 나와있는 것처럼 양쪽에 소스와 싱크를 넣고 해보면 최대 매칭이 가능한 수를 알 수 있다.
  15. /BOJ/4358

    백준 #4358 생태학

    BOJ #4358 - 생태학 https://www.acmicpc.net/problem/4358 # 문제 분류 Trie + map 풀이 접근 방법 트라이랑 맵을 이용해서 해당 종이 몇번 나오는지 마지막 노드로 체크할 수 있게 했다.
  16. /BOJ/5670

    백준 #5670 휴대폰 자판

    BOJ #5670 - 휴대폰 자판 https://www.acmicpc.net/problem/5670 # 문제 분류 Trie 풀이 접근 방법 트라이의 노드에 child 개수를 기록함으로써 한 시점에서 몇가지 분기점이 나오는가에 대해 기록한다. 개수를 세야 할 때는, 루트일 때 자식이 두개 이상일 때 이 부분만 잘 지켜주면서 autoComplete 함수를 짜…
  17. /BOJ/6086

    백준 #6086 최대 유량

    BOJ #6086 - 최대 유량 https://www.acmicpc.net/problem/6086 # 문제 분류 최대 유량 풀이 접근 방법 최대 유량을 사용하면 되는 문제이다. 그리고 같은 간선에 유량이 증가하는 입력이 존재할 수 있으므로, 유량을 더하는 방식으로 입력을 받아야 한다.
  18. /BOJ/1865

    백준 #1865 웜홀

    BOJ #1865 - 웜홀 https://www.acmicpc.net/problem/1865 # 문제 분류 최단 경로 알고리즘 (벨만 포드) 풀이 접근 방법 벨만 포드에서 INF 비교를 안 해야한다 ... 벨만 포드 알고리즘에서 INF 비교를 하지 않아야 AC가 나오는 이유는 뭘까 https://www.acmicpc.net/board/view/50494 …
  19. /BOJ/1219

    백준 #1219 오민식의 고민

    BOJ #1219 - 오민식의 고민 https://www.acmicpc.net/problem/1219 # 문제 분류 벨만 포드 알고리즘 풀이 접근 방법 도달 불가능하면 gg 음수 사이클 + 도달 가능 gee 나머지 -출력
  20. /BOJ/1256

    백준 #1256 사전

    BOJ #1256 - 사전 https://www.acmicpc.net/problem/1256 # 문제 분류 DP 풀이 접근 방법 모르겠어서 justicehui님의 코드를 참고했다. skip은 항상 어려운듯. 그리고 dp 배열을 dpN+M으로 가져가시는게 신기했다. 근데 skip 중에 쉬운거래서 놀람 ㅋㅋ
  21. /BOJ/1738

    백준 #1738 골목길

    BOJ #1738 - 골목길 https://www.acmicpc.net/problem/1738 # 문제 분류 최단 경로 알고리즘 풀이 접근 방법 양의 경로와 음의 경로를 바꿔준다. 경로는 양인게 부정적인 것이니까 이정도는 바로 생각해낼 수 있다. 문제는 사이클인데, 경로에 해당하지 않지만 사이클이 존재할 수 있는 가능성이 있다. 그런 경우 -1을 내주면 …
  22. /BOJ/10775

    백준 #10775 공항

    BOJ #10775 - 공항 https://www.acmicpc.net/problem/10775 # 문제 분류 Disjoint-Set 풀이 접근 방법 유니온파인드를 새로운 관점으로 보게 해 준 문제. 방 청소@9938이랑 비슷하다고는 하는데 그건 너무 어려워서 건들지도 못했어서.. 이렇게도 유니온파인드를 적용시킬 수 있다~ 정도? 구현은 어렵지 않았다.
  23. /BOJ/17398

    백준 #17398 통신망 분할

    BOJ #17398 - 통신망 분할 https://www.acmicpc.net/problem/17398 # 문제 분류 Disjoint-Set 풀이 접근 방법 그래프를 쓰는 문제나 그래프를 만드는 문제에서 간선들을 역방향으로 구성해야 하는 경우는 빈번하게 존재한다. 그대로 disjoint-set을 역으로 만들면 된다.
  24. /BOJ/2213

    백준 #2213 트리의 독립집합

    BOJ #2213 - 트리의 독립집합 https://www.acmicpc.net/problem/2213 # 문제 분류 트리 DP 풀이 접근 방법 되게 어려운 문제.. 트리 DP를 처음 접했을 뿐만 아니라 발문이 사실 이해가 안됐다. 체크/언체크를 하는 이진수 찾기@2248 , 사회망 서비스@2533이랑 비슷한 트리 DP 형태.
  25. /BOJ/3780

    백준 #3780 네트워크 연결

    BOJ #3780 - 네트워크 연결 https://www.acmicpc.net/problem/3780 # 문제 분류 Disjoint Set 풀이 접근 방법 센터만 바뀐다는 것을 알아야 해결할 수 있는 것 같은데.. find 연산을 요리조리 바꾸면 된다.
  26. /BOJ/10986

    백준 #10986 나머지 합

    BOJ #10986 - 나머지 합 https://www.acmicpc.net/problem/10986 # 문제 분류 Prefix Sum 풀이 접근 방법 sumj - sumi-1 % M = 0 -> sumj % M = sumi-1 % M 순서쌍 찾기이므로 개수 C 2
  27. /BOJ/16713

    백준 #16713 Generic Queries

    BOJ #16713 - Generic Queries https://www.acmicpc.net/problem/16713 # 문제 분류 Prefix Sum 풀이 접근 방법 XOR이 어느 연산에 닫혀있는지 생각해보면 쉽습니다. 나중에 XOR 세그먼트 트리 같은 것으로도 응용될 수 있습니다.
  28. /BOJ/2193

    백준 #2193 이친수

    BOJ #2193 - 이친수 https://www.acmicpc.net/problem/2193 # 문제 분류 DP 풀이 접근 방법 dpn = dpn-1 + dpn-1 dpn = dpn-1 dpn-1 = dpn-2 -> dpn = dpn-1 + dpn-2 fibonacci
  29. /BOJ/3197

    백준 #3197 백조의 호수

    BOJ #3197 - 백조의 호수 https://www.acmicpc.net/problem/3197 # 문제 분류 Disjoint Set + BFS 풀이 접근 방법 처음부터 안되는 저격 테케 있을 수 있음. 케이스 잘 관리 안하면 런타임 에러 나니까 주의.
  30. /BOJ/4195

    백준 #4195 친구 네트워크

    BOJ #4195 - 친구 네트워크 https://www.acmicpc.net/problem/4195 # 문제 분류 Disjoint Set 풀이 접근 방법 union-find + rank 쓰면 되는 문제. map을 이용해서 이름마다 번호를 부여하고 그 번호를 유니온 파인드 시키면 깔끔하게 해결할 수 있는 문제
  31. /BOJ/16434

    백준 #16434 드래곤 앤 던전

    BOJ #16434 - 드래곤 앤 던전 https://www.acmicpc.net/problem/16434 # 문제 분류 이분 탐색 풀이 접근 방법 던전 들어가는게 까다로움. -1 해주는 것 처리 안하면 안됨. 서로 1턴만에 죽는 상황에서 플레이어가 우위에 있으므로 피가 0턴만큼 깎여야만함 ,,
  32. /BOJ/2110

    백준 #2110 공유기 설치

    BOJ #2110 - 공유기 설치 https://www.acmicpc.net/problem/2110 # 문제 분류 이분 탐색 풀이 접근 방법 적당하게 최대 거리를 이분 탐색을 이용해서 찾으면 되는데, 그 거리보다 큰 값을 기준으로 잡는 것이 중요! 이 아이디어를 생각하지 못하면 힘들 수 있다
  33. /BOJ/2343

    백준 #2343 기타 레슨

    BOJ #2343 - 기타 레슨 https://www.acmicpc.net/problem/2343 # 문제 분류 이분 탐색 풀이 접근 방법 전형적인 이분 탐색 문제 max(maxx, ~) 이 함수가 그냥 바꿔주는 줄 알았는데 레퍼런스 보니까 그냥 참조해서 들고가더라 ;; 20분 날린 문제 ㅋㅋ ㅠ
  34. /BOJ/2512

    백준 #2512 예산

    BOJ #2512 - 예산 https://www.acmicpc.net/problem/2512 # 문제 분류 이분 탐색 풀이 접근 방법 2805와 마찬가지로 validation을 해주지 않으면 터질 것으로 예상한다.
  35. /BOJ/2512

    백준 #2805 나무 자르기

    BOJ #2805 - 나무 자르기 https://www.acmicpc.net/problem/2805 # 문제 분류 이분 탐색 풀이 접근 방법 이분 탐색의 원리를 제대로 파악하지 못하면 풀기 힘든 문제. 1 3 5에서 4를 찾으려고 할 때 lo<=hi로 만들어진 이분 탐색의 경우에는 lo가 5를 가리킨 후에 이분 탐색이 종료되게 된다. 그러나 이 문제의 경…
  36. /BOJ/6236

    백준 #6236 용돈 관리

    BOJ #6236 - 용돈 관리 https://www.acmicpc.net/problem/6236 # 문제 분류 이분 탐색 풀이 접근 방법 flag로 예외처리 하면 좋을 것 같지만 사실 for문이 loop가 되는 일은 없을 것 같기 때문에 괜찮을듯
  37. /BOJ/1300

    백준 #1300 K번째 수

    BOJ #1300 - K번째 수 https://www.acmicpc.net/problem/1300 # 문제 분류 이분 탐색 풀이 접근 방법 이분 탐색보다 min(mid / i, N) 떠올리는건 세시간 줘도 못할듯 ㅋㅋ ㅠ
  38. /BOJ/1654

    백준 #1654 랜선 자르기

    BOJ #1654 - 랜선 자르기 https://www.acmicpc.net/problem/1654 # 문제 분류 이분 탐색 풀이 접근 방법 이분 탐색을 해주면 된다. 너무 자명하다.
  39. /ALPS/2020-07-contest-review

    ALPS 7월 내부대회 후기

    7월 내부대회를 끝내며. 서론 내부대회로 문제를 내는 것은 세번만이다. 7월 내부대회 후기를 먼저 쓰게 됐는데, 아무래도 블로그 관리를 하지 않았을 때 한 번 냈었어서 꼬인 것 같다. CMSJudge 이제 공식 문서가 읽히기 시작한다. 1.3 버전에서 1.4 버전으로 업데이트하기도 했고, 여러 방면으로 조작을 가해보려고 했지만 쉽게 되지는 않았다. 그래도…
  40. /BOJ/13904

    백준 #13904 과제

    BOJ #13904 - 과제 https://www.acmicpc.net/problem/13904 # 문제 분류 그리디 풀이 접근 방법 과제는 미룰 수 있다면 미루는게 좋다. 따라서 과제의 점수대로 정렬을 한 다음, 최대한 미룰 수 있는만큼 미룬다. 만약 미룰 수 없다면 포기한다. 정말 그리디는 정렬과 선택 두 가지를 적절히 잘 해주는게 중요한 것 같다.
  41. /BOJ/2212

    백준 #2212 센서

    BOJ #2212 - 센서 https://www.acmicpc.net/problem/2212 # 문제 분류 그리디 풀이 접근 방법 맨 왼쪽과 맨 오른쪽을 연결하는 선분 (집중국)이 있다고 하자. 이 집중국을 적절히 K개로 나누기 위해서는 K-1번의 절단이 필요하다. 그래서 인접한 센서 사이의 거리를 모두 재서 정렬을 한 후 K-1개까지 빼준다. 그러면 K…
  42. /BOJ/1493

    백준 #1493 박스 채우기

    BOJ #1493 - 박스 채우기 https://www.acmicpc.net/problem/1493 # 문제 분류 분할 정복, 수학 풀이 접근 방법 사실 분할 정복으로 못풀고 블로그 포스팅을 찾다가 방법을 발견했다. 면적만 주어진다면 될 것 같다는 생각이 들었긴 했는데, 과 1, 1, 8짜리 직사각형이 주어진 경우 불가능하다는 것을 알 수 있다. 그래서 …
  43. /BOJ/15897

    백준 #15897 잘못 구현한 에라토스테네스의 체

    BOJ #15897 - 잘못 구현한 에라토스테네스의 체 https://www.acmicpc.net/problem/15897 # 문제 분류 수학, 정수론 풀이 접근 방법 = 12나 13 정도 두고 돌려보면 어느정도 규칙을 알 수 있습니다. 루트 정도까지는 어느정도 계속 변하는 모습을 보여주지만, 그 이후에는 일정한 값을 유지하는 부분이 존재합니다. 제…
  44. /BOJ/11758

    백준 #11758 CCW

    BOJ #11758 - CCW https://www.acmicpc.net/problem/11758 # 문제 분류 벡터의 외적 풀이 접근 방법 벡터의 외적을 이용해서 AB BC 벡터 간 외적의 부호를 판별하면 됩니다. 제가 외적을 몰랐어서 포스트로 남겨둡니다.
  45. /BOJ/7469

    백준 #7469 K번째 수

    BOJ #7469 - K번째 수 https://www.acmicpc.net/problem/7469 # 문제 분류 세그먼트 트리 (Merge Sort Tree) + 이분 탐색 풀이 접근 방법 세그먼트 트리를 머지 소트 하듯이 관리해줍니다. 즉, 각각의 노드가 벡터로 이루어지게끔 합니다. 구간 내의 k번째 수는 특별한 성질이 있습니다. 바로 자기 자신보다 작…
  46. /BOJ/13925

    백준 #13925 수열과 쿼리 13

    BOJ #13925 - 수열과 쿼리 13 https://www.acmicpc.net/problem/13925 # 문제 분류 세그먼트 트리 with Lazy Propagation 풀이 접근 방법 lazy이긴 lazy인데 곱, 합 두개를 따로 관리해야 합니다. 일단 node가 들고 있는 값은 곱 * 값 + 합으로 관리합니다. 실제로 트리를 어느정도 그려보면 …
  47. /BOJ/16404

    백준 #16404 주식회사 승범이네

    BOJ #16404 - 주식회사 승범이네 https://www.acmicpc.net/problem/16404 # 문제 분류 세그먼트 트리 with Lazy Propagation + DFS Numbering 풀이 접근 방법 각각 사수 / 부사수 관계를 트리로 나타낼 수 있음은 자명합니다. 이 트리를 DFS numbering으로 번호를 매겨가면서 자식 노드가…
  48. /BOJ/10713

    백준 #10713 기차 여행

    BOJ #10713 - 기차 여행 https://www.acmicpc.net/problem/10713 # 문제 분류 누적 합 OR 세그먼트 트리 with Lazy Propagation 풀이 접근 방법 날이 지날때마다 여러 도시를 경유하여 다닙니다. 만약 경유하는 도시를 모두 셀 경우에, 최악의 경우가 되는 경우에는 시간 초과가 일어날 수 있습니다. 따라서…
  49. /BOJ/14942

    백준 #14942 개미

    BOJ #14942 - 개미 https://www.acmicpc.net/problem/14942 # 문제 분류 그래프 순회, 희소 테이블 풀이 접근 방법 번 오른 뒤의 굴과 굴 간의 거리를 희소 테이블을 이용해 동일하게 표현할 수 있음은 자명하다. 그러나 중요한 사실은 트리의 루트가 없기 때문에, 만약 0으로 가는 경우가 있다면 막아주어야 한다. 번 점프…
  50. /BOJ/3006

    백준 #3006 터보소트

    BOJ #3006 - 터보소트 https://www.acmicpc.net/problem/3006 # 문제 분류 세그먼트 트리 풀이 접근 방법 정렬하면서 어떤 숫자를 옮긴다는 행위는 그 범위 밖으로 빼는 것과 같다. 그 말인 즉슨, 배열의 양 옆에 테두리를 두었다 생각하고 문제의 조건대로 나타내어 보자. 방문하지 않는 수 중 작은 숫자를 골라서 테두리의 왼…
  51. /ALPS/2020-01-contest-review

    ALPS 1월 내부대회 후기

    1월 내부대회를 끝내며. 서론 첫 대회 출제기도 했고, 알프스에서 부회장으로써 준비하는 첫 공식 행사였기 때문에 긴장이 되는게 없지 않아 있었다. 일단 내부대회 + 출제진 부족으로 문제 수를 늘리기보다는 한 문제에 서브태스크를 여러 개를 만드는 식으로 하는 것으로 결정이 났다. 그래서 DOMJudge나 백준을 사용하지 않고 CMSJudge를 이용해 컨테스…
  52. /ALPS/2020-01-contest-B-solution

    ALPS 내부대회 B번 - 연애고수 최용욱 풀이

    연애고수 최용욱 ALPS 2020 1월 내부대회 B번출제자: ALPS 최용욱2020. 01. 31 서브 태스크 Index Constraints Time Complexity TC #1 (15 points) , TC #2 (45 points) TC #3 (140 points) 풀이 DP 점화식 Index Solution TC #1 모든 미팅에 참…
  53. /BOJ/9465

    백준 #9465 스티커

    BOJ #9465 - 스티커 https://www.acmicpc.net/problem/9465 # 문제 분류 Dynamic Programming 풀이 접근 방법 2행짜리 배열을 요리조리 왔다갔다하면서 최댓값이 결정된다는 것이 좀 골치아파 보이는 문제이다. 하나를 제거하면 마주보는 변의 스티커는 제거할 수 없기 때문에, 대각선 방향으로 보는 것으로 생각하면…
  54. /BOJ/11060

    백준 #11060 점프 점프

    BOJ #11060 - 점프 점프 https://www.acmicpc.net/problem/11060 # 문제 분류 Dynamic Programming 풀이 접근 방법 칸에 있는 수만큼 오른쪽 칸들을 보고 dpcurrent에 1을 더해서 dpjumped에 넣으면 된다. 단순하네! 점화식은 dpcurrent+jump = min(dpcurrent+jump, …
  55. /BOJ/10844

    백준 #10844 쉬운 계단 수

    BOJ #10844 - 쉬운 계단 수 https://www.acmicpc.net/problem/10844 # 문제 분류 Dynamic Programming 풀이 접근 방법 0으로 시작하는 수는 없다는 점을 생각하며 DP 테이블을 작성해보자. 그러면 0 → 1 만 가능, 9 → 8 만 가능하다는 것이 보이게 된다. dp0 = prev1, dp9 = prev…
  56. /algorithm/shortest-path

    최단 경로 알고리즘

    최단 경로 알고리즘 - algorithm for shortest path problem 개인적인 정리를 위한 포스트로, 학습용으로는 적합하지 않을 수 있습니다.참조에 적힌 블로그 포스트를 읽으시는 것을 추천드립니다. :) 최단 경로를 구하는 문제에서 적용할만한 알고리즘을 알아보자. 0) 모델링 그래프에 대한 정보는 인접 행렬이나 인접 리스트를 이용해 모델…
  57. /BOJ/4485

    백준 #4485 녹색 옷 입은 애가 젤다지?

    BOJ #4485 - 녹색 옷 입은 애가 젤다지? https://www.acmicpc.net/problem/4485 # 문제 분류 최단 경로 찾기 (Dijkstra Algorithm) 풀이 접근 방법 결국 바둑판처럼 생긴 격자에서 최단 경로를 찾는 것과 다를 바가 없다. 시작점 (0, 0)과 끝점 (n-1, n-1)이 정해져 있으므로 Dijkstra 알고…
  58. /BOJ/1389

    백준 #1389 케빈 베이컨의 6단계 법칙

    BOJ #1389 - 케빈 베이컨의 6단계 법칙 https://www.acmicpc.net/problem/1389 # 문제 분류 최단 경로 찾기 (Floyd-Warshall Algorithm) 풀이 접근 방법 각각 노드 쌍에 대한 최단 경로를 모두 구해야 하므로 Floyd-Warshall 알고리즘을 사용하자. 회장뽑기@2660 처럼 생각하면 가중치를 통해…
  59. /BOJ/1238

    백준 #1238 파티

    BOJ #1238 - 파티 https://www.acmicpc.net/problem/1238 # 문제 분류 최단 경로 찾기 (Dijkstra Algorithm) 풀이 접근 방법 input size가 크므로 Dijkstra 알고리즘을 사용한다. 각각의 노드마다 Dijkstra하면 되므로, n번 돌리면 이므로 가능하다. → 사실 엄밀히 말하면 긴 하다 ,, …
  60. /BOJ/10159

    백준 #10159 저울

    BOJ #10159 - 저울 https://www.acmicpc.net/problem/10159 # 문제 분류 최단 경로 찾기 (Floyd-Warshall Algorithm) 풀이 접근 방법 각각 물건의 대소관계를 directed graph로 생각한다면 최단 경로 알고리즘으로 해결할 수 있다는 것을 알 수 있다. 따라서 마찬가지로 모든 쌍들에 대한 거리를…
  61. /BOJ/1613

    백준 #1613 역사

    BOJ #1613 - 역사 https://www.acmicpc.net/problem/1613 # 문제 분류 최단 경로 찾기 (Floyd-Warshall Algorithm) 풀이 접근 방법 각 노드쌍에 대한 최단 경로를 모두 구해야 하므로 역시 Floyd-Warshall 알고리즘을 사용하면 된다. INF와 0으로 각각 초기화 한 후, dist[i]j가 IN…
  62. /BOJ/1956

    백준 #1956 운동

    BOJ #1956 - 운동 https://www.acmicpc.net/problem/1956 # 문제 분류 최단 경로 찾기 (Floyd-Warshall Algorithm) 풀이 접근 방법 마을과 마을 사이를 연결하는 도로는 일방통행 도로이다. 자기 자신의 가중치를 0으로 설정하지 말고 INF로 두어 갱신 가능하게 설정, Floyd-Warshall. 답이 …
  63. /BOJ/2660

    백준 #2660 회장뽑기

    BOJ #2660 - 회장뽑기 https://www.acmicpc.net/problem/2660 # 문제 분류 최단 경로 찾기 (Floyd-Warshall Algorithm) 풀이 접근 방법 일단 최단 경로 찾는 알고리즘을 사용해야 한다. 각각의 노드 별로 최단 경로를 계산해야 하므로, Floyd-Warshall 알고리즘이 적합하다. (input size…
  64. /BOJ/1753

    백준 #1753 최단경로

    BOJ #1753 - 최단경로 https://www.acmicpc.net/problem/1753 # 문제 분류 최단 경로 찾기 풀이 접근 방법 다익스트라 알고리즘을 사용하면 된다. 그러나 개미들을 구분짓지 않는다면? 개미가 부딪혀 돌아가는 것을 그저 통과하는 것으로 볼 수 있다. 따라서 막대의 중간에서 가장 가까이 있는 개미가 끝을 향해 달리는 최단시간이…
  65. /BOJ/4307

    백준 #4307 개미

    BOJ #4307 - 개미 https://www.acmicpc.net/problem/4307 # 문제 분류 상상력 풀이 접근 방법 모든 개미들의 이동경로를 알아봐야한다면, 개미가 부딪힐 때를 모두 계산해야하므로 정말 복잡해질 것이다. 그러나 개미들을 구분짓지 않는다면? 개미가 부딪혀 돌아가는 것을 그저 통과하는 것으로 볼 수 있다. 따라서 막대의 중간에서…
  66. /BOJ/4796

    백준 #4796 캠핑

    BOJ #4796 - 캠핑 https://www.acmicpc.net/problem/4796 # 문제 분류 그리디 알고리즘 풀이 접근 방법 캠핑을 오래 하기 위해서는 휴가가 시작하자마자 캠핑을 가서 최대치를 채우면 쉬고 다시 가면 된다. 구현해보자. 남은 휴가일 수 V가 연속 P일 중 가능일 수 L보다 크거나 같다면,가능일 수 L만큼 모두 캠핑을 즐길 수…
  67. /BOJ/1449

    백준 #1449 수리공 항승

    BOJ #1449 - 수리공 항승 https://www.acmicpc.net/problem/1449 # 문제 분류 그리디 알고리즘 풀이 접근 방법 입력들은 파이프에서 물이 새는 위치이므로, 그리디 알고리즘을 사용하기 위해 정렬해준다. 물이 새는 위치를 발견하면 테이프의 시작점을 붙인다고 생각하고 tmp 값에 저장해준다. 다음 입력이 tmp + L - 1 …
  68. /BOJ/11000

    백준 #11000 강의실 배정

    BOJ #11000 - 강의실 배정 https://www.acmicpc.net/problem/11000 # 문제 분류 그리디 알고리즘 풀이 접근 방법 size = 200000, 1초 제한이므로 으로는 절대 풀 수 없다. → 우선순위 큐를 이용, 풀이 강의를 빨리 시작하는 순서대로 정렬해준다. a. greater 연산자로 만든 우선순위 큐에 정렬된 첫 …
  69. /BOJ/1700

    백준 #1700 멀티탭 스케줄링

    BOJ #1700 - 멀티탭 스케줄링 https://www.acmicpc.net/problem/1700 # 문제 분류 그리디 알고리즘 풀이 접근 방법 입력을 받을 때 입력 빈도 수를 기록하는 arr 배열과 작동 순서를 기록하는 shd 배열에 각각의 정보를 저장한다. 그리디 알고리즘을 이용해서 문제를 해결하기 위해서 해야 하는 작업은 다음과 같다. a. 멀…