개행문자 때문에 scanner.next() 받고 나서는 항상 scanner.nextLine()을 해줘야한다.
sc.hasNextInt(...) 같이 자료형을 체크하는 기능도 제공한다.
객체지향 이모저모
- Static vs Singleton
느낀 점
금방 끝날 줄 알았던 팀 프로젝트가 테스트, 스펙에 대한 합의, 병합 과정 등등에서 꽤 오랜 시간이 걸리고 있다. 아직 협업이 익숙치 않아서 그런지 모든 프로그램을 이해해야하기도 하고 나나 팀원분들이나 다른 사람의 작업을 기다리는 경우도 많이 생겨서 협업이 쉽지 않구나라는 생각이 든다.
그래도 다들 잘하시는 분이라 배울 점이 많다는 것은 참 다행이고. 내일은 꼭 마무리 지어서 알고리즘 문제 + 편안한 주말을 맞이하길..
오늘 오전에 설계 다 끝내기로 했는데 내가 또 git 오류가 나서 다시 git 공부에 들어가고 팀원분이 특강도 해주셨다.
내가 헷갈린 부분은 local과 origin(forked된 repository)의 branch를 동일하게 여겼다는 것이다.
내가 작업중인 branch로 원본 repo에 올라가있는 코드를 받아오기 위해서는
git fetch upstream(원본 repo의 별칭으로 내가 지정해둔 이름이다) 명령어를 통해 업데이트된 내용이 있는지 확인한다. 그 후
git merge upstream/dev(가져오고 싶은 branch 명) 으로 병합하면 된다.
내 작업물을 push하고 싶을 때는 add commit 후 git push origin jdh(branch명) 하면 내 forked repo에 올라가고 그러면 github 웹페이지 내에 pull request가 뜬다. wkdehdgk159/jdh에서 원본 repo/원하는 branch 인지 꼭 확인할 것.
객체지향 이모저모
- 객체지향 설계의 느낌적인 느낌
우리 호텔 예약 프로그램의 큰 설계는 이런 구조이다. 호텔(완전 주인님) - Handler(로직을 수행하는 직원들) - dao(데이터를 조회, 전달만 해주는 노예느낌). 그리고 나머지 객체들이다. 패키지로 구분하자면 domain(수동적으로 정보만 가진 친구들), handler, dao 로 구성되어 있다. 느낌적인 느낌?
느낀 점
걸출한 디자인 패턴 들에 비해서는 보잘 것 없지만 그래도 각자의 역할 + 역할의 무게에 따라 구분해놓으니 뭔가 있어보이는 느낌적인 느낌?? 좋다.
- There is no default constructor available in 'parent class' 에러 해결. 부모 클래스에 생성자가 있다면 본인 생성자를 호출하기 전 부모 클래스 생성자를 호출해주어야 한다. 아래 super(name, description)이 필수.
public class Menu {
private String name;
private String description;
public Menu(String name, String description) {
this.name = name;
this.description = description;
}
}
public class Product extends Menu{
String name;
String description;
int price;
public Product(String name, String description, int price) {
// this.name = name;
// this.description = description;
//이렇게 하면 에러.
super(name, description);
this.price = price;
}
}
객체지향 4대 원칙 공부
- 추상화, 상속, 다형성, 캡슐화 : 과제를 구현은 했으나 객체 지향적으로 했는지 모르겠다고 하니 고수 팀원 분이 블로그 글을 추천해주셨다.
느낀 점
과제를 완성하긴 했는데 Menu, Product 클래스는 거의 구조체(struct)나 다름없고 주요 로직은 한 클래스에 몰아둬서 자바스크립트와 다름이 없다. 튜터님께도 여쭤봤는데 아직 감이 안 잡힌다
수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.
즉, Ai+ ... + Aj(i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.
(1 ≤ N ≤ 10^6, 2 ≤ M ≤ 10^3, 0 ≤ Ai≤ 10^9)
2. 풀이
구간합이 M으로 나누어 떨어지는 경우의 수를 구하는 문제입니다.
가장 그리디한 풀이는 sum[i][j]라는 배열을 선언하고 모든 구간합을 구한 후 sum[i][j] % M = 0이 되는 경우의 수를 구하는 것일텐데요
골드 3 문제답게 10^6이라는 통 큰 N을 주면서 O(n^2)의 시간복잡도를 방지하였습니다.(prefix sum으로 1차원 배열을 하더라도 시간복잡도는 똑같겠네요).
핵심은 '모듈러 연산'이 0이 되는 경우의 수를 구하는 것입니다.
일단 prefix sum으로 sumarr[j] - sumarr[i-1]이 구간합이 되게끔 누적합을 모두 구해줍니다.
우리가 궁금한 것은 (sumarr[j] - sumarr[i-1]) % M = 0 이 되는 것인데
모듈러 연산은
(A + B) % C = (A % C + B % C) % C
(A - B) % C = (A % C - B % C) % C
가 성립합니다
따라서 (sumarr[j] - sumarr[i-1]) % M = 0 인 경우라면
(sumarr[j] % M - sum[i-1] % M) % M = 0이 될 것이고
저희는 sumarr[j] % M = sum[i-1] % M 인 경우의 수를 찾으면 되는 것입니다.
추가로 sumarr[j] % M = sum[i-1] % M 인 경우의 수는 서로 다른 두 누적합의 나머지가 같은 경우만 고려한 것이고
Ai 원소 하나로 M으로 나누어 떨어지는 경우의 수도 있으니 이 또한 추가로 더해줍니다.
3. 코드
//https://www.acmicpc.net/problem/10986
//10986. 나머지 합(Gold 3, 누적합)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define endl "\n"
#define INT_INF 2147483647
#define LL_INF 9223372036854775807
#define ll long long
using namespace std;
ll N, M, ans = 0;
ll sumarr[1000000];
//sumarr의 나머지를 세는 배열
ll marr[1000];
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
freopen("input.txt", "r", stdin);
//INPUT
cin >> N >> M;
//SOLVE
//누적합 계산
ll sum = 0;
ll A;
int cnt = 0;
for(int i = 0; i < N; i++) {
cin >> A;
if(A % M == 0) cnt++;
sum += A;
sumarr[i] = sum;
}
//구간합 (sumarr[j] - sumarr[i-1]) & M = 0 이라면
//(sumarr[j] % M) - (sumarr[i-1] % M) = 0 이므로
//(sumarr[j] % M) = (sumarr[i-1] % M)) 인 경우의 수를 찾자.
for(int i = 0; i < N; i++) {
marr[sumarr[i] % M]++;
}
for(int i = 0; i < M; i++) {
//후보들 중 2개를 순서상관없이 고르는 경우의 수
ans += marr[i] * (marr[i] - 1) / 2;
}
//marr[0]에 들어갔던 구간합은 자기 자신만으로도 해당되기 때문에 따로 더해줌
ans += marr[0];
//OUTPUT
cout << ans;
}
4. 이모저모
개인적으로 여러번 실수했던 부분이 있습니다.
바로 나머지를 세주는 marr의 자료형을 int로 선언하여 오버플로우가 계속 발생한 것입니다.
marr를 int로 선언한 배경은 marr의 원소가 한곳에 몰려서 아무리 커봤자 N의 최대값인 10^6을 넘지 못하기 때문에
int로도 충분하다고 생각하였습니다.
하지만 ans += marr[i] * (marr[i] - 1) / 2; 이 계산에서 int 범위를 넘기기 때문에 오버플로우가 발생한다는 사실을 백준 질문게시판을 통해 알게되었고 굳이 int를 쓰고 싶다면 저 계산식에서만
1LL * 을 더해주거나 int64_t(marr[i]) 등의 형 변환을 해주어야 한다는 것도 배웠습니다.
누적합 + 모듈러 연산의 성질 + 자료형 등등 많은 것을 배울 수 있는 문제였습니다.오늘 하루도 화이팅 하십쇼~~!!
