본문 바로가기

전체 글

 (167)
[백준] 7795번 먹을 것인가 먹힐 것인가 (C++) - binary search 문제 https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 코드 #include #include using namespace std; int a[20000]; int b[20000]; int main(){ int t,n,m; cin >> t; while(t--){ cin >> n >> m; for(int i=0; i> a[i]; } for(int i=0; i> b[i]; } sort(a,a+n); ..
[알고리즘] Analysis of Algorithms Time complexity analysis 시간복잡도 분석은 input size에 대해 basic operation(단위 연산)이 얼마나 많이 수행되었는지 구하는 것이다. 시간복잡도 분석 방법에는 Every-case analysis, Worst-case analysis, Best-case analysis, Average-case analysis가 있다. 시간복잡도는 알고리즘의 효율성을 판단하기 위해 자주 사용된다. ++단위연산(basic operation): 알고리즘 내의 어떤 명령문이나 명령문 군을 선정하여, 알고리즘이 수행한 총 작업의 양을 이 명령문이나 명령문 군을 수행한 횟수에 대략적으로 비례하도록한다. 이 명령문 또는 명령문 군을 단위연산이라 한다. ex) 비교, 할당 Every-case an..
[백준] 2089번 -2진수 (C++) 문제 https://www.acmicpc.net/problem/2089 2089번: -2진수 -2진법은 부호 없는 2진수로 표현이 된다. 2진법에서는 20, 21, 22, 23이 표현 되지만 -2진법에서는 (-2)0 = 1, (-2)1 = -2, (-2)2 = 4, (-2)3 = -8을 표현한다. 10진수로 1부터 표현하자면 1, 110, 111, 100, 101, 11010, 110 www.acmicpc.net 코드 #include #include using namespace std; int main(){ int n; cin >> n; if(n==0){ cout
[백준] 9417번 최대 GCD (C++) - substr(), find()를 활용해서 특정 문자 기준으로 자르기, Euclidean algorithm 문제 https://www.acmicpc.net/problem/9417 9417번: 최대 GCD 첫째 줄에 테스트 케이스의 개수 N (1 > n; cin.ignore(); while(n--){ int result..
[백준] 1850번 최대공약수 (C++) - Euclidean algorithm 문제 https://www.acmicpc.net/problem/1850 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net 코드 #include using namespace std; long long gcd(long long a, long long b){ while(b!=0){ long long c=a%b; a=b; b=c; } return a; } int main(){ long long a,b; cin >> a >> b; int num=gcd(a,b); for(int i=0; i
[백준] 1072번 게임 (C++) - binary search 문제 https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 코드 #include using namespace std; int main(){ long long x,y; cin >> x >> y; long long z=100*y/x; long long start=0; long long end=x; long long result=-1; while(startz){ result=mid; end=mid-1; }else{ start=mid+1; } } c..
[백준] 2512번 예산 (C++) - binary search 문제 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 코드 #include #include #include using namespace std; vector v; int n, a; long long handleSum(int cri){ long long sum_val=0; for(int i=0; icri) sum_val+=cri; else sum_val+=v[i]; } return sum_val; } int main(){ cin >> n; ..
[백준] 7576번 토마토 (C++) - BFS 문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 코드 #include #include #include using namespace std; int m,n,day=0; int box[1000][1000]; int isVisited[1000][1000]; queue q; // 북, 동, 남, 서 int dy[4] = {-1,0,1,0}; int dx[4] = {0,1,0,-1}; bool inRange(int y, int x)..

티스토리툴바