한다 공부

10814번: 나이순 정렬 (acmicpc.net) 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 두가지 값을 저장하는 것이므로 pair를 이용하면 된다. 단, 첫 번째 값인 나이순으로 정렬하되 두 번째 값인 이름은 입력 순서를 유지해야한다. #include 안에 있는 sort 함수를 써서 정렬을 했다 계속 틀렸습니다가 떠서 당황했는데, 알아본 결과 sort의 경우 비교하는 값이 같을 경우에 원래 순서를 유지한다는 보장이 없다고 한다. 다시 말해 sort로 정렬하면 나이가 같은 사람들은 정렬 순서가 원래와 다르게 ..

10816번: 숫자 카드 2 (acmicpc.net) 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net (이분 탐색) 지난 포스팅 을 통해 이분 탐색을 공부했다. 이번엔 직접 구현을 해보았다. 우선 해당 문제는 내가 원하는 카드가 몇 장 있는지 탐색해야하는 문제인데, 어떻게 구할까? 이 문제에서는 upperBound 와 lowerBound 에 대해 알아야한다. [ 1 2 2 2 3 ] 라는 배열이 있다고 했을 때, 2를 찾는다고 가정해보자. lowerBound는 내가 찾는 카드의..

1920번: 수 찾기 (acmicpc.net) 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 이분 탐색은 효율성을 요구하는 문제에서 많이 쓰인다고한다. 이러한 이분 탐색은 실생활에서도 많이 쓰인다. 최근에 무한도전을 봤는데 노홍철이 생각한 숫자를 멤버들이 특정 횟수 내에 맞춰야하는 게임을 했다. 1~100 까지의 수라고 하면, 50을 물어보고 up down을 해서 범위를 좁혀나가는게 가장 현명하다. 이 방법이 이분 탐색이다. C++에서는 #include을 통해..

1931번: 회의실 배정 (acmicpc.net) 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 탐욕 알고리즘이라고 불리는 그리디 알고리즘이란 무엇일까? 그리디 알고리즘이란, 지금 상황에서의 최선의 선택이 곧 정답이라는 알고리즘이다. 시간적으로 효율적이지만, 매번 그리디로 푼 풀이가 정답이 아닐 수도 있다!! 그리디 알고리즘을 사용하려면 현재 최선의 선택이 전체 문제의 정답이어야한다. O(N) 시간복잡도를 가지고, 백만 이상의 입력도 받을 수 있다. 주로 정렬과 우선순위 큐를 함께 이용한다. 그리디임을 확인하기 위해서는 많은 수학적 증명이 필요하다고 한다. 그러므로 보통의 경우, 직관적으로 판단하여 그리디를 사용한다고 한다..

12865번: 평범한 배낭 (acmicpc.net) 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 냅색 문제를 풀어보았다. 이 문제에서는, 들 수 있는 배낭의 최대 무게가 주어진다. 그리고 물건의 무게와 물건의 최대 가치가 주어지는데, 배낭에 넣을 수 있는 물건의 최대 가치값을 구하는 문제이다. 동적 계획법을 이용해 냅색 문제를 해결해보자. 우선 dp의 인덱스를 무게로 나타내자 예를 들어 배낭에 넣을 수 있는 최대 무게가 7Kg 이라고 하자. ..

2579번: 계단 오르기 (acmicpc.net) 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 동적 계획법 (dynamic programming) 이란 무엇일까? 바로 현재 값을 구할 때, 과거에 구한 값을 활용하는 알고리즘이다. 예를 들어 내가 한 노드에 있는데 이 노드로 올 수 있는 길은 두 갈래 라고 하자. 왼쪽 노드에서 와야 최단 경로인지, 오른쪽 노드에서 와야 최단 경로인지 구해야한다. 출발지에서 왼쪽 노드까지 가는 최소 비용의 합을 dp 배열에 저장한다. 위 그래프에서는 3의 비용으로 왼쪽 노드까지 갈 수 ..

15649번: N과 M (1) (acmicpc.net) 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹이란? 브루트 포스와 같이 완전 탐색을 하는 알고리즘이 있는데, 여기서 조건에 해당되지 않는 경우를 가지치기 하여 경우의 수를 줄여나가는 방법을 백트래킹이라고 한다. 백트래킹을 이용하면 탐색 시간이 줄어든다. 백트래킹에서는 주로 재귀함수를 이용한다. 이때, 재귀함수의 종료조건이 중요하다. 백트래킹은 주로 N의 값이 20보다 작을 때 이용한다. 위 N과 M (1)의 문제를 예로 들어보자. n=4, m=..

16563번: 어려운 소인수분해 (acmicpc.net) 16563번: 어려운 소인수분해 첫째 줄에는 자연수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 자연수 ki (2 ≤ ki ≤ 5,000,000, 1 ≤ i ≤ N)가 N개 주어진다. www.acmicpc.net 일반 에라토스테네스의 체는 bool 배열을 만들어서 소수면 true, 아니면 false를 저장한다. 그런데 이 문제에서는 소인수들을 찾아야하므로 bool 배열 대신 int 배열을 만들어서, 어떤 수로 인해 소수가 아니게 되었는지를 저장한다. 예를 들어 8의 경우, 8은 2의 곱으로 인해 소수가 아니게 되었다. >> 2 출력 8/prime[k] = 8/2 =4 가 된다. 4는 2의 곱으로 인해 소수가 아니게 되었다..

2436번: 공약수 (acmicpc.net) 2436번: 공약수 첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0 www.acmicpc.net 유클리드 호제법을 이용했다. 최대공약수를 G, 최소공배수 L이라 하자 G*L = A*B 이다. (수학적 공식이라고 한다.) A = G*a, B=G*a이라고 하면 (이때 a, b는 서로소이다. 왜냐하면 최대공약수 G로 공통부분을 끄집어 냈으므로) G*L = G*a*G*b가 되고 약분하면 L/G=a*b가 된다. L G가 주어지니 이를 이용해서 A+B, 즉 a+b가 최소가 되는 a b를 찾고 a b에 G를 구해 최종적으로 ..

우선 코랩에 대해 알아보자. 코랩이란? Colaboratory의 약자로 Google에서 교육과 과학 연구를 목적으로 개발한 도구이다. 코랩을 이용하면 Python의 다양한 라이브러리를(numpy 등) 활용하여 데이터 분석 및 시각화를 할 수 있다. 또한 코드 몇 줄만으로 이미지 data set 을 가져올 수 있고, 이미지 분류를 학습시킬 수 있다. 코랩을 이용하면 GPU를 무료로 액세스할 수도 있다. 코랩의 구조는 아래와 같다. 코랩을 이용하기 위해 아래 주소에 접속하면 된다. Colaboratory에 오신 것을 환영합니다 - Colaboratory (google.com) Google Colaboratory colab.research.google.com 그렇다면 YOLO란 무엇일까? 욜로는 You Onl..