티스토리

NANANAM

검색하기

블로그 홈

NANANAM

donggul-godsang.tistory.com/m

soeayun 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

1. NextJS로 간단한 홈페이지 만들기(노마드코더 무료 강의) https://nomadcoders.co/nextjs-for-beginners/lobby Next.js 시작하기 – 노마드 코더 Nomad CodersNextJS for Beginnersnomadcoders.co위에 나오는 강의에 1. INTRODUCTION의 내용을 간단히, 요약 정리를 한 글이다. NextJS가 뭐야??React framework 중에서 가장 유명한 애임!!-> 먼저 react에 대해서 알아야함!(jsx, state, props, data fetch, routing와 같은 기본 개념을 알아야함)#routing: 웹 애플리케이션에서 사용자의 요청(URL)에 따라 적절한 페이지나 리소스를 제공하는 과정! = 사용자가 웹 애플리케이션을탐색할 떄 발생하며 URL을 해석하여 해당 페이.. 공감수 0 댓글수 1 2024. 6. 16.
CS231n 4. Introduction to Neural Networks (요약,정리!) Backpropagation (gradient for neural network) 네트워크 전체에 대해 Chain rule(연쇄 법칙)을 적용하여 gradient를 계산하는 방법 중 하나로 이를 이용해 loss function의 gradient를 구해 parameter들을 최적화(optimization)하는데 사용한다. 또한 neural networks을 효과적으로 개발, 디자인 및 디버그하는데 중요하다 우리가 Backpropagation를 공부하는 이유? 실제로 #analytic_gradient 를 어떻게 계산하는지에 대해 알아볼거임! 여러개의 linear classification을 사용할 경우 gradient를 어떻게 찾을 것인지!=> 이 gradient를 이용해 loss를 구함 - 입력값 xi(이.. 공감수 0 댓글수 2 2024. 3. 14.
CS231 2. Image Classification(score function) Image Classification Problem: 입력 이미지(input image)를 미리 정해진 카테고리 중 하나인 라벨(label)로 분류하는 문제로써 Computer Vision에서 매우 핵심적인 문제로 알려져있다. 현재 이미지를 구별하는데 여러 현실적인 문제가 존재한다. - semantic gap: 우리 눈: 고양이가 한 눈에 들어온다! VS 컴퓨터: 매우 크고 다양한 숫자들로 이루어진 배열로 인식! - 컴퓨터가 이것이 무엇인지 정확히 이해하고 있는 것이 아니고 무엇을 뜻하는지 알아내는 것이 쉽지 않음 - 조금만 카메라를 돌리면 사진을 이루는 픽셀의 숫자가 바로 바뀌게 됨 -> 다시 학습을 해야함 문제점 1. Viewpoint variation(시점 변화) 2. Scale variation(.. 공감수 0 댓글수 1 2024. 1. 23.
[C/C++] 백준 14003: 가장 긴 증가하는 부분 수열 5 (Backtrace) https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 풀이! 이 문제에서 가장 긴 증가하는 부분 수열의 길이를 구하는 알고리즘의 동작방식은 12015: 가장 긴 증가하는 부분 수열 2와 같다. 12015 문제와 다른 점은 이 문제는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력해야한다. 그렇기 때문에 경로를 저장하고 나중에 이 경로를 다시 찾아야한다. 먼저 가장 긴 증가하는 부분 수열의 길이를 구하는 방법은 아.. 공감수 0 댓글수 1 2023. 10. 21.
[C/C++] 백준 1509: 팰린드롬 분할 (DP) https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 팰린드롬? 이 문제는 어떤 문자열을 팰린드롬으로 분할할 때 분할의 개수의 최솟값을 구해야하는 문제이다. 팰린드롬인지 아닌지는 10942: 팰린드롬? 문제와 같이 어떤 수가 팰린드롬일 때 양쪽끝(맨 처음과 맨 끝)을 제외한 가운데 부분도 팰린드롬이라는 사실을 이용하여 시간복잡도를 줄이며 확인할 수 있다. 그 과정은 아래 포스팅을 참.. 공감수 0 댓글수 1 2023. 10. 21.
[C/C++] 백준 10942: 팰린드롬? (DP) https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 풀이? 먼저 펠린드롬이란 거꾸로 읽어도 제대로 읽는 것과 같은 문장을 뜻한다. 이 문제에서는 각 질문에 대하여 팰린드롬인지 아닌지를 답해야 하는데 질문의 개수가 10^6이고 수열의 크기가 최대 2000이기 때문에 사실상 각 질문마다 팰린드롬인지 확인을 한다면 시간복잡도가 O(NM)이 되기 떄문에 시간안에 풀 수 없다. 그렇기 때문에 각 수가 팰린드롬인지 아닌지를 새로운 배열에 저장해가며 풀어야만 시간 내의 해결이 가능하다. 다만 각 질.. 공감수 0 댓글수 1 2023. 10. 21.
[C/C++ ] 백준 2467: 용액 (두 포인터) https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 맨 처음에는 bruteforce하게 문제 접근하여 각 경우마다 안되는 경우를 계산하여 시간복잡도가 O(n^2/4)짜리 알고리즘을 짰지만 시간초과가 나왔다. 그 후 이 문제를 "두 포인터"를 이용해 풀었다. 두 포인터란? 두 포인터/ 투 포인터는 말 그대로 두 개의 포인터를 이용해 문제를 해결하는 알고리즘이다. 즉, 2개의 포인터를 구간의 길이를 가변적으로 잡아가며 특정 조건을 만족하는 구간 .. 공감수 0 댓글수 1 2023. 10. 20.
[C/C++] 백준 7579: 앱 (Kanpsack-DP) https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 이 문제도 무게(weight)와 가치(value)이 존재하는 전형적인 배낭(Knapsack) 문제이다. 배낭 문제를 해결하는 방법은 용량/비용을 이용하여 backtracking을 하는 방법도 있지만 가장 널리 쓰이고 구현하기 쉬운 Dynamic Programming이 대표적이다. 이 문제 역시 Dynamic Programming을 이용하여 문제를 해결했다. Kanpsack 알고리즘! 배낭 문제를 DP로 .. 공감수 0 댓글수 1 2023. 10. 20.
[C/C++] 백준 9252: LCS 2 (Backtrace) https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이? 문제에서도 친절히 적혀있다싶이 LCS(Longest Common Subseuqence)를 구하면 되는데 이는 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. LCS 길이 알고리즘 무식하게 모든 경우의 수를 따지면서 풀 경우 문자열의 길이가 n,m(n>arr1>>arr2; int n=arr1.length(),m=arr2.leng.. 공감수 0 댓글수 1 2023. 10. 18.
머신러닝을 위한 수학 (개요) 머신러닝에서의 수학이란? 데이터(data) 속의 표현(특징)을 기계가 학습한 것으로 데이터의 대부분은 고차원으로 되어있다. 이것은 곧 백터와 행렬로 구성되어 있다는 것을 뜻한다. 이때 ML 알고리즘은 고차원 데이터의 표현(특징)을 학습 목적에 맞게 뽑아내는 함수(function)를 학습한다. (알고리즘은 사실상 수학으로 만든 함수) Python에서 데이터 처리 Python을 이용하는 이유: 1. 매우 직관적 2. 별도의 컴파일이 필요 없음 3. 오픈소스 라이브러리가 파이썬으로 공유됨 Numpy: 행렬이나 일반적으로 대규모 다차원 배열을 쉽게 처리할 수 있도록 지원하는 파이썬의 라이브러리(다차원 배열을 쉽게 처리)=> import numpy as np Pandas: Data Science에서 데이터 분석을.. 공감수 0 댓글수 0 2023. 10. 14.
[C/C++] 백준 1644: 소수의 연속합 (에라토스테네스의 체 & 부분 합) https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 풀이! 이 문제를 풀기 위한 과정은 크게 2가지로 나뉜다. 첫번째로는 1부터 n번째까지의 수들 중에서 소수들을 구해야하는 것이고 두번쨰로는 부분 합을 이용하여 연속된 소수의 합으로 주어진 자연수를 나타낼 수 있는 경우의 수를 구하는 과정이다. 첫번째 과정은 소수 판정을 위한 에라토스테네스의 체를 사용하면 되고 두번째는 부분 합을 이용하면 된다. 에라토스테네스의 체 에라토스네스의 체란? 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 만들어낸 소수를 찾는 방법으로 체로 치듯이 수를 걸러낸다고 하여 뒤에 '체'.. 공감수 0 댓글수 0 2023. 10. 14.
[C/C++] 백준 1806: 부분합 (누적 합 이용) https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이! 사실 문제 이름 자체도 부분합이고 문제 내용도 부분합이라서 "누적합"을 이용하여 문제를 풀어야겠다는 생각을 할 수 있었다. 부분 합(누적 합) 부분 합이란 배열의 시작부터 현재 위치까지의 원소의 합을 구해둔 배열이다. 이렇게 부분 합을 미리 구해 놓는다면 a번째 index부터 b번째 index까지의 합을 구할 때 O(b-a)의 시간이 걸릴 것을 psum[b]-psum[a-1].. 공감수 0 댓글수 0 2023. 10. 14.
[C/C++] 백준 12015: 가장 긴 증가하는 부분 수열2 (O(logn) 알고리즘) ㅣhttps://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 풀이! 이 문제를 기존의 11503: 가장 긴 증가하는 부분 수열 푼 방식으로 풀 경우에는 해결이 불가능하다. 그 이유는 11503 문제의 알고리즘은 시간복잡도가 O(n^2)로 구현해도 해결이 가능했지만 이 문제는 수열의 크기가 10^6이므로 똑같이 시간복잡도가 O(N^2)가 되어 시간초과가 발생하게 된다. 그렇기 때문에 새로운 아이디어를 생각해야한다. 일단 가장 기본적인 알고리즘은 11503 .. 공감수 0 댓글수 2 2023. 10. 14.
[C/C++] 백준 20040: 사이클 게임 (Union-Find) https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 해설! 이 문제는 최소 스패닝 트리를 구하기 위해서 필요한 연산인 Union-Find를 이용하면 쉽게 풀리는 문제였다. 이 문제를 Map이나 c++ 내부에 있는 자료구조를 이용하여 풀 경우에는 사실상 해결이 불가능한데 그 이유는 점의 개수가 최대 500,000개이며 진행되는 연산이 최대 1,000,000이기 때문이다. 그렇기 때문에 Union-find를 이용하여 그 연산시간이 O(logn) .. 공감수 0 댓글수 0 2023. 10. 12.
[C/C++] 백준 2252: 줄 세우기 (위상정렬) https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 이 문제를 풀기 위해서는 위상 정렬에 대한 이해가 필요하다! 위상 정렬? 위상 정렬은 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미하며 정렬 알고리즘의 일종이다. 위 문제와 같이 1은 3보다 먼저 와야하고 2는 3보다 먼저 들어와야 한다는 방향성이 있을 때 사용 가능하는 알고리즘이다. 따라서 위상 정렬의 결.. 공감수 0 댓글수 0 2023. 10. 11.
[C/C++] 1562: 계단 수 https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제를 10844: 쉬운 계단 수처럼 모든 경우의 수를 배열에 저장하여 풀려고 한다면 메모치 초과가 날 것이다. 그렇기 때문에 메모리 아끼면서 Dynamic Programming을 해결하기 위한 방법으로 비트마스킹을 이용하면 된다. 이 문제는 사실 10844 문제를 비트마스킹으로 풀기만 하면 되기 때문에 자세한 알고리즘은 아래 포스팅을 참고하면 된다! https://donggul-godsang.tistory.com/67 [C/C++] 10844: 쉬운 계단 수 https://www.acmicpc.net/problem.. 공감수 0 댓글수 2 2023. 10. 11.
[C/C++] 백준 1197: 최소 스패닝 트리 (Kruskal 알고리즘) https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 최소 스패닝 트리는 크게 프림의 알고리즘과 크루스칼 알고리즘을 통해 구현이 가능하다. 이 문제에서는 크루스칼 알고리즘을 이용하여 최소 스패닝 문제를 해결했다! 크루스칼(Kruskal 알고리즘)? 크루스칼 알고리즘의 가장 기본적인 아이디어는 사이클이 만들어지지 않는 한에서 간선을 가중치의 오름차순으로 정렬한 뒤, 스패닝 트리에 하나씩 추가하는 것이다. .. 공감수 0 댓글수 1 2023. 10. 10.
[C/C++] 백준 1504: 특정한 최단 경로 (다익스트라 풀이) https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이!!! 다익스트라 알고리즘! 다익스트라를 제대로 구현을 한 상태라면 사실 쉽게 풀 수도 있다. 다익스트라를 4번에서 6번 사용을 한다면 최단거리를 1부터 N까지 V1과 V2를 거치면서 최단거리를 구하면 된다. 이 문제에서 한번 이동했던 정점을 다시 이동할 수 있다는 것은 다익스트라를 여러번 사용할 때 같은 정점을 지나도 된다는 것이지 한번의 다익스트.. 공감수 0 댓글수 1 2023. 9. 30.
[C/C++] 백준 17404: RGB 거리 2 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 하나 주의해야 할건 첫번째 칠한 집과 마지막으로 칠한 집의 색깔이 같으면 안되는것이다. 그렇기 때문에 기존의 DP로 문제를 풀게 된다면 이 조건을 만족시키기에 쉽지 않다. 따라서 여기서 생각해야하는건 첫번째로 칠할 집의 색깔을 정하고 나서 for문을 3번 돌며 각각의 경우세어 모든 집을 칠하는 비용의 최솟값을 구해야한다. 즉 dp[0][1]로 시작했을 때는 dp[1][.. 공감수 0 댓글수 0 2023. 9. 28.
[C/C++] 백준 5639: 이진 검색 트리 (backtrack을 통한 후위순회) https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 풀이!! 맨 처음에는 괄호를 이용한 후위 표기식 문제와 같이 stack에 넣음으로써 문제를 해결하려고 했지만 그렇게 할 경우 코드가 너무 복잡해지고 구현할 수가 없어 다른 방법을 모색하였다. 전위 순회의 특성상 루트-왼쪽 자식-오른쪽 자식 순으로 이동하기 때문에 전체의 루트를 하나만 잡았을 때 배열이 루트(1)-왼쪽자식 (n개)-오른쪽 자식(m)개가 된다. 예를 들어 50 30 24 .. 공감수 0 댓글수 1 2023. 9. 26.
[C/C++] 백준 2206: 벽 부수고 이동하기 (BFS,tuple 이용 풀이) https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 구현! 사실 원래의 BFS를 이용한 최단거리 알고리즘에서 조금만 추가하면 쉽게 풀 수 있는 문제이다. 여기서 중요한 것은 tuple안의 4개의 원소를 집어넣어 각각 x좌표, y좌표, 벽을 뚫고 지나갔는지에 대한 여부, 현재까지의 거리를 저장해야 하는 것이다. 또한 중요한 것이 visit 배열인데 기존의 2차원으로만 표현하면 안되고 3차원으로 표현하여 벽을 뚫고 지나갔는지에.. 공감수 0 댓글수 0 2023. 9. 18.
[C/C++] 백준 11444: 피보나치 수 6 (점화식 풀이) https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 맨 처음에 다른 문제처럼 DP로 풀려고 했지만 너무 범위가 커 메모리초과가 나왔다. 구현!! 이 문제와 같이 입력의 수가 과도하게 크고 DP를 사용해야할 상황일 때 (1.)항상 점화식을 2개로 나눠서 풀 수 있도록 생각을 해야한다. 특히 (2.)한번 지난간 곳을 저장해둬서 한번 지난 곳은 다시 못 지나가게 만들어 시간을 줄여야할 필요도 있다. 1) 그래서 점화식을 나누기 위해 머리를 굴렸지만 결국 두개로 나누지 못했다. 사실 거의 다 오긴 했지만 마지막에... 그렇게 다른 .. 공감수 0 댓글수 0 2023. 9. 17.
[C/C++] 백준 11725: 트리의 부모 찾기(vector 이용) https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 맨 처음에 문제에서 트리의 루트를 1로 둔다는 조건을 확인 못해서 맨 처음에 해맸다.. 구현!! 사실 간단하게 풀이가 가능하다. 이차원 백터 vectorv1[100001]를 선언하여 각 노드와 연결되어 있는 노드를 뒤에 추가해주면 된다. 이때 무엇이 부모이고 자식 노드인지 모르기 때문에 v1[tmp1].push_back(tmp2); v1[tmp2].push_back(tmp1); 두번 다 해줘야한다. 그 다음에는 queue를 이용하여 push와 pop을 해주면 .. 공감수 0 댓글수 0 2023. 9. 17.
[C/C++] 백준 16236: 아기 상어 (BFS, 반례 및 주의점!) https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 사실 BFS로 돌면서 풀면되는 아주 간단한 문제인줄 알았지만 생각보다 해야할게 많아서 굉장히 고민을 많이 했다. 무려 3시간만에 겨우 풀었다... 문제 해설보다는 내가 실수했던 부분 위주로 한번 써보려고 한다. 주의해야할 점! 1. 지나가는 것과 먹을 수 있는 경우 문제에 그대로 나와있다싶이 자신의 크기보다 큰 물고기가 있는 칸을 제외한 칸은 모두 지나갈 수 있고 자신의 크기보다 작은 물고.. 공감수 0 댓글수 0 2023. 9. 17.
[C++] 모듈러 사칙 연산 (BOJ 1629: 곱셈) 백준 1629: 곱셈 문제를 풀다가 자꾸 시간초과가 나오다보니 결국 하는 방법을 찾게 되었는데 모듈러 계산에 대해서 공부할 필요성을 느끼게 되었다. 앞으로 모듈러 연산이 나올 때마다 여기다가 다시 정리를 해야겠다. 모듈러 사칙 연산 덧셈, 뺄셈, 곱셈에 대해서는 다음 식이 항상 성립한다. (이부분에서는 mod M을 % M이라고 표현) 덧셈 : (a+b) % M = ((a % M) + (b % M)) % M 뺄셈 : (a-b) % M = ((a%M) - (a%M)) % M 곱셈 : (a*b) % M = ((a%M) * (b%M)) % M 나눗셈 : 모듈로 연산에서 나눗셈은 곱셈 역원(multiplicative inverse)을 곱하는 방식으로 이루어진다. 모듈로 곱셈 역원은 항상 존재하는 것이 아니라, b.. 공감수 0 댓글수 0 2023. 9. 15.
[C/C++] 백준 1167: 트리의 지름 (다익스트라 풀이) https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 방법?? 문제 자체가 트리의 지름을 구하라고 하는데 이때 트리의 지름이란 임의의 두 점 사이의 거리 중 가장 긴 것을 의미한다. 그렇기 때문에 모든 노드에서 DFS 혹은 다익스트라 알고리즘을 통해 가장 긴 거리를 구하려는 것이 첫번째 생각일 것이다. 하지만 이렇게 할 경우 각 정점마다 (V) 트리를 모두 순회하며 (V) 최댓값을 구해야하기 때문에 O(V^2)의 시간이 걸려 시.. 공감수 0 댓글수 0 2023. 9. 15.
[C/C++] 백준 11660 구간 합 구하기 5 (이차원 구간 합) https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 풀이 방법? 가장 먼저 드는 생각은 합을 구해야하는 횟수마다 저장되어 있는 2차원 배열에서 이중 for문을 통해 구간 합을 각각 구하는 방법인데 이 방법으로 할 경우 최악의 경우에는 100,000*1024*1024 의 경우를 모두 확인해야하므로 시간 초과가 발생한다. 그렇기 때문에 여기서 제목에 있는 힌트를 빌려 풀이 방법을 생각해보자면 현재 있는 위치까.. 공감수 0 댓글수 0 2023. 9. 15.
[C++] Map을 이용한 tree 구현 (BOJ 1991: 트리순회) https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 이 문제를 직접 tree를 구현하여 풀지 않고 map을 이용하여 구현하였다. Map이란? map은 각 노드가 key와 value가 쌍을 이루고 있는 트리로 pair 객체로 저장되기 때문에 first-key로 second-value를 저장한다. 중복을 허락하지 않으며 기본 형태는 map m; 으로 key를 통해 value를 찾기 용이하게 되어있다. 그래서 map은 pair로 이루어진 se.. 공감수 0 댓글수 0 2023. 9. 14.
[C/C++] 백준 1916: 최소비용 구하기 (다익스트라 구현하기!) https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 이번에 드디어 다익스트라 알고리즘을 배워서 실제 문제 풀이에 적용하였다. 알고리즘 문제해결 전략에 나와있는 것을 응용하여 해결했다. 1. 준비작업 1-1. vector adj_list[100001] 먼저 각 노드들의 인접리스트를 만들 이차원 백터 vector adj_list[100001]을 선언해주었다. 이 백터의 역할은 a번째 노드와 연결되어 있는 b번째 노드까.. 공감수 1 댓글수 1 2023. 9. 13.
[C/C++] 13549: 숨바꼭질 3 (BFS,Queue) https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 결론부터 말하자면 이 문제는 queue를 이용해 bfs로 풀 수 있는데 이때 2의 배수일 때는 0초만에 도달 가능하다는 것만 유의하면 된다. 구현?? 이를 구현하기 위해서 내가 사용했던 방법은 함수 after_onesec와 after_zero이다. after_onesec는 1초뒤에 갈 수 있는 곳을 queue에 넣는 방식으로 동작되는데 이때 queue.fron.. 공감수 0 댓글수 0 2023. 9. 12.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.