Algorithm

백준 9205 맥주마시면서걸어가기 c++ // bfs, 출력시 "\n을 빼먹지마라.."

https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 1. 의사코드 sy,sx,ey,ex : 시작점, 끝점 좌표저장 vector : 편의점의 좌표들 저장 vis[i] : i번 편의점의 방문여부 저장 = > 중복방문 안하도록 50*20==1000이므로 1000미터 이내를 인접노드로 본다! if(거리 인접노드에 추가한다 2.bfs 복습(문어박사) 1. q초기값넣기, 초기화 등 2. cur값체크, !종료조건! 3.nxt값체크, 큐에넣기 3. 전체코드..

백준 5014 스타트링크 c++ // bfs 를 사용하라. (dfs는 시간초과)

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 1.시행착오 범위가 1~f~1000000이므로 if(f>=0) continue; //정답 , 범위를 정확히 맞춰야함, 안맞추면 f==0일때를 탐색하여 오답이됨 if(f>0) continue; //오답! 2. 전체코드 #include using namespace std; int f, s, g, u, d,ret=987654321; int v[1000000 + 4]; int main() { cin.tie(0); c..

백준 13458 시험감독 c++ // ret는 int범위를넘을수있다.

https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 1. ret의 범위설정 시험장 1,000,000 * 학생수 1,000,000 > 21억 -> long long ret를 써야함 2. 전체코드 #include using namespace std; int n, a[1000000+4], b, c,tot; long long ret; int main() { cin.tie(0); cin >> n; f..

프로그래머스 합승택시요금 c++ // 다익스트라 table완성 후 조회만, 플로이드

https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 다익스트라 table완성 후 조회만 기존 : 각각 go(start~allnode) + go(allnode, a) + go(allnode , b)하면 시간초과가 난다. int d[3][204]; //[0][node] : 시작~해당정점까지 최단거리 //[1][node] : a~해당정점까지 최단거리 //[2][node] : b~해당정점까지 최단거리 //미리 테이블을 완성후, 쿼리에서는 조회만 하도..

프로그래머스 순위검색 c++ // 이분탐색, db설정

https://school.programmers.co.kr/learn/courses/30/lessons/72412 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. db설정 : map m; 카카오 문제는 db설정을 잘해야한다. java back junior pizza 100 일때, 각각각 빈칸인경우와 빈칸아닌경우로 분기하면서 모든경우의 수에 대해(2^4) m[문자열] = { 100, ... } db를 완성한다. 2. 쿼리에서는 단순 조회만하면된다. m[javaback] = {1,2,3,4,4,5} 가있을떄, 4를 찾고있으면 end에서 4의위치(lower..

프로그래머스 메뉴리뉴얼 c++ // 비트마스킹 조합

https://school.programmers.co.kr/learn/courses/30/lessons/72411 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 시행착오 a~y 모든 조합을 돌리고 하는방법 X 결론 : DB설정을 잘해서 저장하자. freq[size][문자열] = 등장횟수 2. 비트 -> 문자열 만드는법 비트가켜져있는경우 해당 문자를 더하면된다. if(subset & (1 A B C F G subset : 1 0 0 0 0 0 1 0 0 0 ... 1 1 0 0 0 ... */ for(auto order : orders){ //ABCF..

백준 1654 랜선자르기 c++ // 이분탐색, parametric search

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 1. parametric search 최적화문제 -> 결정문제로 바꿔서 해결한다. 단, 감소또는 증가함수에서만 사용가능하다. 이경우에는 랜선길이up => 랜선갯수down 이다. ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ N개로만들수있는 랜선의 최대길이 -> 랜선길이가x일때, 랜선갯수가 N개이상인가? 2.의사코드 while (st < en) { ll mid = (st +..

백준 2295 세수의합 c++ // 이분탐색 발상

https://www.acmicpc.net/problem/2295 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 1. 이진탐색 발상 nC2들의 합배열 : two a를 탐색(n^2) * 이진탐색(lgN) 부분합을 구한후, 이진탐색을 하라!!! 2.의사코드 a[i]+a[j]+a[l]=a[k] 인 k 의 최대값 찾기 two(a[i]+a[j])==a[k]-a[l]인 k의 최대값 찾기! 3. 전체코드 #include using namespace std; typedef ..