study/알고리즘

https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 이 경우 2개의 네트워크가 있는거(1-2, 3) 이 경우 1개의 네트워크가 있는거(1-2-3) 연결된 네트워크까지 쭉 dfs로 탐색하고 아직 탐색도 안했고 연결도 안됐으면 dfs가 다시 실행되니까 그 새로 실행되는 dfs가 몇 번인지 알면 된다!! #include #include using namespace std; int check[200]; // 노드에..

https://programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 우선순위큐를 사용한다면 어렵지 않은 문제!!!! #include #include #include using namespace std; int solution(vector scoville, int K) { int answer = 0; priority_queue pq; for(int i: scoville) { pq.push(i); } while(pq.t..

https://programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr 각 작업은 병렬적으로 실행 가능하지만, 앞의 기능이 배포가 되어야만 뒤에꺼도 배포할 수 있음. 어떤 작업이 배포할 때까지 걸리는 시간이 앞 작업의 배포 시간보다 작다면 나중에 앞 작업이 배포될때 같이 배포될 수 있음! #include #include #include #include using namespace std; vector solution(vect..

https://programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 참여자중에 한 명만 완주를 못하고 나머지는 다 완주를 하니까 참여자, 완주자를 각각 정렬했을 때 같은 위치에 완주자랑 참여자 이름이 다를 때 그 참여자가 완주 못한 친구겠구만!!! 이라고 생각!!! #include #include #include using namespace std; string solution(vector participan..

https://programmers.co.kr/learn/courses/30/lessons/81301 코딩테스트 연습 - 숫자 문자열과 영단어 네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다. 다음은 숫자의 일부 자 programmers.co.kr one4sevneeight -> 1478 23four5six7 -> 234567 1zerotwozero3 -> 10203 이렇게 영어로 된 친구들까지 숫자로 바꿔주는 문제다!! #include #include #include #include using namespace std; map number = {{"zero", 0}, {"one", 1}, {"..

보호되어 있는 글입니다.

백준 11728번 www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 문제 : 정렬되어있는 두 배열 A와 B가 주어진다. 두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성하시오. 그냥 일반적인 정렬 방식을 쓰면 O(N^2) 시간이 걸리는데 여기서 배열의 최대 크기가 100만이므로 시간이 너무 오래 걸린다. 배열 A, B가 정렬되어있기 때문에 머지 소트를 이용해서 풀면 빠르게 풀수있다.(merge sort의 시간 복잡도는 ..

백준 10816번 www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제 : 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 ..

백준 10815번 www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제 : 숫자 카드는 정수 하나가 적혀 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오. 이 문제를 풀기 전에 이분 탐색(Binary Search)에 대해서 짧게 설명을 하자면 그냥 쉽게 생각해서 반으로 잘라서 그 반보다 같냐/크냐/작냐를..

백준 1202번 www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 문제 : 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다. 상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 ..

백준 12813번 www.acmicpc.net/problem/12813 12813번: 이진수 연산 총 100,000 비트로 이루어진 이진수 A와 B가 주어진다. 이때, A & B, A | B, A ^ B, ~A, ~B를 한 값을 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 : 총 100,000 비트로 이루어진 이진수 A와 B가 주어진다. 이때, A & B, A | B, A ^ B, ~A, ~B를 한 값을 출력하는 프로그램을 작성하시오. 비트 연산에 대해서 이해만 하면 된다!! &(AND)는 둘 다 1일 때 1 |(OR)은 하나만 1이면 1 ^(XOR)은 둘이 다른 수일 때 1(정확하게는 1이 홀수개일 때 1이지만 여기서는 두 개만 비교하니까 이렇게 표현했다) ~는 모든 비트를 반전시..

백준 2138번 www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는(1) 상태와 꺼져 있는 (0) 상태 중 하나의 상태를 가진다. i(1