결국 빛나리라

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net > dfs 활용 단방향 그래프가 아닌 양방향 그래프임에 주의해야한다. ▷ 처음에는 단방향 그래프로 다음과 같이 구현했다. 그러나 위 코드는 다음과 같은 예제는 풀지 못한다. 위와 같은 그래프가 있다고 할때 단방향 그래프는 1번 노드에서 출발했을 때 3번과 2번노드와 연결되어 있다고 인식하기 때문에 다음과 같이 1과 연결된 노드의 수로 2를 출력한다. ▷ 그러나 문제에 따르면 1번 노드는 2,3번 노드 ..

https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net > 그리디 알고리즘 가장 큰 단위의 동전가치부터 순회하면서 동전의 가치가 입력받은 k보다 작은 숫자이면 해당 동전으로 k의 가치를 차감할 수 있다는 뜻이다. 따라서 해당 가치로 k를 나눈 몫(몇 번 사용할 수 있는지 그 횟수를 나타냄)을 result에 더해주고 나머지 동전의 가치로 k값을 갱신시킨다. 여기서 중요한 점은 필요한 동전의..

https://www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net > 큐 활용 큐의 기본 개념을 확인하는 문제이다. 만약 시간 초과가 나온다면 다음 포스팅을 참고하자. https://westshine-data-analysis.tistory.com/63?category=843975 [백준 | 파이썬3] 1753. 최단경로- 다익스트라/ 런타임에러 input() vs stdin.readline https://www.acmicpc.net/pr..

https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net > 힙 활용 힙을 활용한 다익스트라 알고리즘 구현에서 최대 힙과 최소 힙을 구현해보았었다. 해당 문제는 최대힙을 활용해 풀 수 있었다. 힙은 요소를 꺼낼때 가장 작은 값부터 뽑아온다. 이를 활용하여 가장 큰값부터 뽑아오게 하기 위해 요소에 -를 붙여서 가장 큰값을 가장 작은 값으로 변환하여 힙에 넣고 뺄 때는 -부호를 다시 붙여서 양수로 뽑히게끔 만들었다.

밑바닥부터 시작하는 딥러닝을 교재로 한 유튜브 강좌와 파이토치로 배우는 자연어처리 책을 참고하여 작성하였습니다. ▶ 퍼셉트론이란? 뉴런을 본떠 만든 가장 간단한 신경망으로 구성요소로 입력x, 출력y, 파라미터로는 가중치w와 절편b가 있다. 신경망의 기초가 되는 부분이기 때문에 해당 개념에 대해 짚고 넘어갈 필요가있다. 가중치와 절편은 데이터를 학습하면서 계속 업데이트 되는 파라미터들로, 가중치는 해당 입력값이 얼마나 중요한지를 나타내고 절편(=편향)은 임계값 역할을 하여 학습데이터와 가중치를 계산한 값이 해당 절편을 넘어야 하는 값이 된다. 따라서 편향이 높으면 높을 수록 입력값이 True가 되는 장벽이 더 높아진다고 할 수 있다. 아래 그림에서 편향은 -theta로 표현할 수 있다. 수학적으로 퍼셉트론..

https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net > 동적계획법 이미 계산된 적이 있는 값들은 dp리스트에서 빼와 사용하고 계산된 적이 없는 값들만 재귀함수를 호출하여 계산하도록 한다. a 또는 b또는 c가 0이하이면 바로 1을 돌려주고 20초과면 dp에서 20,20,20위치에 있는 값을 가져오면 되기 때문에 funny함수의 매개변수를 20,20,20으로 두고 실행한다. 실제로 계산을 통해 dp값을 구해놓아야 하는 범위는 1에서 20 사이의 값들 이..

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net > 이진탐색 활용 #1. 런타임 에러 처음에는 target number가 있는 리스트들에 대한 반복문을 돌리면서 타겟이 A리스트에 있으면 if target in A: 1을 출력하고 아니면 0을 출력하도록 했다. 하지만 역시 런타임 에러가 났다. 1초당 1억번의 연산을 할 수 있다고 하면 n과 m에 최대 100,000개의 정수가 들어가기 때문에 최악의..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 코드 출처: https://github.com/ndb796/python-for-coding-test ▶ 사이클 판별 서로소 집합 알고리즘을 무방향 그래프 내에서 사이클이 발생하는지(서로 연결되어 순환할 수 있는 구조인지) 판별하는데 사용할 수 있다. ▶ 작동 과정 step 1. 각 간선을 확인하며 루트노드를 보았을 때 루트 노드가 같다면 사이클이 발생한 것이고, 같지 않으면 두 노드에 대한 union연산을 수행한다. step 2. 모든 간선에 대해 step1을 반복한다. ▷ 예시 아래와 같은 그래프가 있다고 해보자. 1,2,3 노드에서 사이클이 발생하고 있으므로 사이클이 존재하는 그래프이다. 작동 과정을 경로 ..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 코드 출처: https://github.com/ndb796/python-for-coding-test ▶ 경로압축기법을 사용한 서로소 집합 알고리즘 특정 원소의 루트노드를 찾기 위해 경로 압축 기법을 사용하여 효율적으로 문제를 해결할 수 있다. 이전 방식에서 루트 노드를 구하는 함수에선 부모노드 테이블의 원소가 루트 노드가 아닌 바로 위에 존재하는 부모노드의 루트노드로 설정하였지만 경로압축기법을 사용하면 부모노드 테이블의 원소를 해당 원소의 루트노드로 바로 갱신시켜줄 수 있다. 즉 경로압축기법을 사용하면 이전 포스팅의 예시에서 다뤘던 결과 테이블이 다음과 같은 형태로 바뀐다. 해당 방법을 사용하면 계속해서 루트노..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 코드 출처: https://github.com/ndb796/python-for-coding-test ▶ 서로소 집합이란 공통원소가 없는 두 집합을 의미한다. 서로소 집합은 서로소 부분 집합들로 나눠진 원소들의 데이터를 처리하기 위한 자료구조로, 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 Union, 특정 원소가 속한 집합은 어느 집합인지 알려주는 Find 연산을 수행할 수 있다. ▶ 트리자료구조를 이용한 서로소 집합 계산 알고리즘 step 1. 서로 연결된 두 노드 A,B를 확인한다. 두 노드의 루트 노드 A'과 B'을 찾는다. step 2. 일반적으로 두 루트 노드 중 더 번호가 작은 원소의 부모노..