[백준 31809] malware 박멸하기 : https://www.acmicpc.net/problem/31809문제 조건시간을 신경쓸 필요가 없어보인다. 하루에 박멸 이후 감염이 차례로 진행된다고 이해할 수 있다. 따라서 자신에게 진입 간선이 존재한다면 박멸 이후 감염이 이뤄지므로 아무런 일도 일어나지 않는다. 위에서 말했던 것에 대한 예시를 확인할 수 있다. 진입 간선이 존재한다면, 박멸 이후 감염된다.주기(P)와 C의 크기가 다른 것이 처음 문제를 읽을 때 조금 헷갈렸다.  문제 해결 방법 문제의 핵심은 현재 박멸이 진행되는 컴퓨터(노드)에 진입하는 간선(즉, 외부에서 감염될 가능성)이 있다면, 해당 컴퓨터는 다시 감염될 수 있어 즉시 처리할 수 없다는 점이다.따라서 진입 간선이 없는 노드를 우선적..

[백준 4196] 도미노 : https://www.acmicpc.net/problem/4196문제 조건 도미노가 한쪽 방향으로만 넘어지기에 단방향 간선으로 표현되지만, 실제로는 우리가 원하는 방향(왼쪽 또는 오른쪽)으로 도미노를 밀어 넘어뜨릴 수 있다. 즉, 한 도미노가 넘어진 방향에 따라 연쇄 반응을 일으키는 관계가 결정되는데, 이때 도미노를 그래프로 나타내면 간선이 기본적으로 한 방향(진출 간선)만 표시된다. 하지만 만약 어떤 도미노가 한쪽 방향에서는 연쇄 반응을 일으키지 못한다면, 그 도미노의 반대쪽(진입 간선) 방향으로도 연쇄 반응을 고려할 수 있어야 한다. 그래서 DFS를 진행할 때, 상황에 따라 진출 간선과 진입 간선을 서로 뒤바꿔서 탐색할 수 있다는 뜻이다. 이는 단순히 양방향 그래프가 되는..

https://school.programmers.co.kr/learn/courses/30/lessons/49191 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 접근 방법 위상 정렬위상 정렬로 열내면서 풀어봤지만 문제를 풀수록 미궁 속으로 빠졌다. 위상 정렬로 풀이하면 처음과 끝에 있는 선수들의 순위는 비교적 쉽게 정할 수  있지만, 중간에 있는 선수들의 순위는 모호하고, 접근하기 까다로워진다. 문제를 풀면서 이상하다고 생각해서 찾아보니 위상 정렬은 순서가 명확히 정해진 상황에서 사용하는 게 올바르다고 한다.(순서가 명확, 사이클X -> 위상 정렬) 플..

https://school.programmers.co.kr/learn/courses/30/lessons/340210 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  문제 접근 방법  특별히 떠오르는 알고리즘은 없었다. 문제에서 제시한 힌트와 비슷한 방식으로도 풀이해봤고, 조금 더 최적화해서 진행해보기도 했지만 실행결과는 비슷해서 아쉬웠다. 풀이 방법 (2가지) 1. 문제 설명대로 풀어본 코드 문제에서 제시한 힌트는 아래와 같다. 가능한 STRAT진수 ~ END진수 를 체크해보고, 그 결과들이 다르다면 ?를 출력하고 결과가 같다면 풀이 가능한 문제로 표현하는..

[백준 22954] 그래프 트리 분할 : https://www.acmicpc.net/problem/22954문제 조건 정리 정점 𝑁개, 간선 𝑀개의 그래프가 주어진다.각 정점은 1부터 𝑁까지 번호가 매겨져 있고,간선도 입력되는 순서대로 1부터 𝑀까지 번호가 매겨져 있다.그래프에서 원하는 만큼 간선을 삭제해, 서로 다른 크기의 트리 2개로 분할해 보자!각각의 트리는 하나 이상의 정점을 가지고 있어야 하며, 두 트리가 동일한 정점이나 간선을 공유해서는 안 된다.입력과 출력   문제를 풀기 전 그래프를 분할할 수 없는 경우를 올바르게 짚는다면 효율적으로 해결할 수 있다.2개의 트리로 분할할 수 없는 경우    -> 주어지는 정점 개수가 1개    -> 진작에 3개 이상의 분할된 그래프가 주어짐 (간선으..

이분(이진)탐색에서 항상 헷갈리던 Upper / Lower Bound 에 대해서 복습하자.feat. (백준 14003, 소프티어 3307의 LIS 문제를 해결하며.)개요 이분 탐색은 정렬된 요소중 찾고 싶은 값, target(key)을 빠르게 찾는 방법이다. O(logN) 단순히 타겟을 찾는 것을 넘어서, 이진 탐색의 원리를 확장하여 ‘Upper Bound’와 ‘Lower Bound’ 개념을 적용함으로써, 데이터 집합 내에서 특정 값의 범위를 정확하고 빠르게 찾을 수 있어야한다.개념 비교하기 Upper Bound는 주어진 값보다 큰 첫 번째 요소를 찾는다. Lower Bound는 주어진 값 이상의 첫 번째 요소를 찾는다. idx012345678value112223334 찾고 싶은 value, 즉 targ..