분류 전체보기

백준 2805 나무자르기 c++ // 이분탐색, 매개변수탐색, 정답후보를 for문 돌려라

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 1. 의사코드 1. 적어도 n이상.. 문제 -> 결정문제로 바꿔서 푼다 2. 정답후보 : 0~20억에 대해 st, en으로 이분탐색 3. 이분탐색 공식은 암기토록 하자. 2. 전체코드 #include using namespace std; typedef long long ll; ll n,m, a[1000000 + 4]; //길이가 x일때, 가질나무가m개 이상인..

백준 2573 빙산 c++ // dfs, 구현, year에 대해 반복문 만들기

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 1. 의사코드 일단 분할정복으로 문제를 나눈다 1. 뺄셈할 값을 계산하기 2. 원본배열에 더하기 3. 구역세기 위 1,2,3을 year에 대해 반복하기! 2. 시행착오 1. 매year(tc)마다 vis, b배열을 초기화 해주어야 한다! 2. 구역세는 코드는 외울것. 3. 전체코드 #include using namespace std; int n,m,cy,cx; int dy[] = { 1,0,-..

백준 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..