목록Algorithm/배열 (14)
Mini
[배열] 프로그래머스 행렬의 곱셉
https://school.programmers.co.kr/learn/courses/30/lessons/12949?language=java 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr * 풀이answer 배열의 1칸씩 계산한다.k가 핵심!ex) 15 = 1*3 + 4*3 =answer[0][0] = arr1[0][0] * arr2[0][0] + arr1[0][1] * arr2[1][0]answer[i][j] = for(k=0 to c1) arr[i][k] * arr2[k][j] class Solution { public int[][] solution(int[][] arr1, int[][] arr2) { ..
리트코드 169 다수원소 // 배열, 투표알고리즘
https://leetcode.com/problems/majority-element/description/ * 풀이1절반이상인 원소가 반드시 존재함을이용정렬 -> 중간지점의 원소가 다수원소임class Solution { public int majorityElement(int[] nums) { Arrays.sort(nums); return nums[nums.length/2]; }}O(nlgn) * 풀이2투표 알고리즘 이용 O(n)class Solution { public int majorityElement(int[] nums) { int king=nums[0]; int cnt=1; for(var num : nums){ ..
[맞음] 프로그래머스 서버증설횟수 // 배열, 구현
https://school.programmers.co.kr/learn/courses/30/lessons/389479 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr* 풀이필요할때마다 증설하는게 최적인가? 그런듯.귀류법 증명) ... class Solution { static int[] need = new int[25]; static int[] server = new int[25]; public int solution(int[] players, int m, int k) { int answer = 0; int n = players.length; ..
[틀림] 프로그래머스 자물쇠와 열쇠 // 배열회전, 배열좌표
https://school.programmers.co.kr/learn/courses/30/lessons/60059 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr시도1lock 의 y,x에 좌물쇠를 대보면서 전부 1인지 체크하는 방법오답포인트 : 자물쇠, 열쇠 둘다 (0,0)에서 시작한다고 가정반례 : 열쇠가 좌물쇠 좌측위에 있는경우도 가능함.#include using namespace std;vector> key, loc, origin;vector> rot(vector> origin){ vector> ret(24, vector(24, 0)); // int ret[24][24]; for(i..
[틀림 hard] 프로그래머스 외벽점검 // 원형배열, 순열, 비트마스킹
https://school.programmers.co.kr/learn/courses/30/lessons/60062 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr* 풀이n이 작음 (15) -> 비트마스킹? -> 내부에서 순서도 중요하네? -> 그냥 순열?idx가 사람의수이면서 && dist의 index 역할j는 weakArr(weak를 시작점에따라 바꾼것) 의 index임dist를 앞부터 weakArr에 집어 넣어보는 완전탐색 방법.원형배열 구현 , 거리가 중요한경우결론 : startIdx기준으로 뒤넣고, 앞넣을때 배열 size만큼 더해주면된다.vector make(int startIdx, vector&..
[알고리즘] 리트코드 238. Product of Array Except Self c++ // 배열, 누적곱, rbegin, partial_sum
https://leetcode.com/problems/product-of-array-except-self/description/* 풀이1(케이스 분류)경우의수를 나누고구현i) 0의갯수가 0개인경우ii) 0의갯수가 1개인경우iii) 0의갯수가 2개이상인경우class Solution {public: vector productExceptSelf(vector& nums) { vector ret; int zero_count=0; int total_product=1; for(auto num : nums){ if(num==0) zero_count++; else total_product*=num; } ..
리트코드 자기를 제외한 배열의 곱 c++ // 누적곱 해결방법 : 누적곱 테이블을 정의하라
https://leetcode.com/problems/product-of-array-except-self/description/1. 기존코드0을 제외한 총 곱을 구하고0이 몇개인지에 따라서 분기함.. 너무 복잡함typedef long long ll;class Solution {public: vector productExceptSelf(vector& nums) { vector v,zero; int ret=1, iszero=0,isallzero=1; //0을제외한 총곱 , 0이있는지, 모두0인지 for(auto num:nums){ if(num==0) { iszero=1; zero.push_ba..
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..