3주차 스터디

[jjsyeon]

Hashing & DnC

2월 26일 코테 스터디

[MirrorPI]

문제 : 색종이 만들기
질문 : for문 한 번만 탈출하는 이유? && 여러개의 한 번에 탈출할 수 있는 방법

반복문 한번에 탈출

outer:
for(int i=1; i<=N; i++) {
	for(int j=1; j<=N; j++) {
		if(paper[x][y] != paper[x+i-1][y+j-1]) {
			isSameColor = false;
			break outer;
		}
	}
}

[dradra0905]

문제 : 색종이 만들기
질문 : 시간 복잡도 계산하는 방법?

• 이 문제에서 => Nlog_4(N)??
  • 점화식 => T(N) = 4T(N/2) + O(N^2)
• 일반적인 재귀에서 => 상태의 수(= 모든 노드의 수) * 내부 시간복잡도

[dradra0905]

문제 : 색종이 만들기
질문 : 함수로 만들어서 쓰면 속도가 느려지나?

• 재귀를 안 하는 함수의 경우 JVM이 인라인 함수로 처리해서 속도 차이 얼마 안 날 수 있음
• 매개변수와 리턴 값을 전달하는 경우 더 느려질 수 있음

[dradra0905]

문제 : 곱셈
질문 : 모듈러 연산을 반복적으로 쓸 때 문제가 없나?

• 나눗셈을 제외하고는 전부 분배법칙이 적용된다.
• 결론적으로, 나머지 연산 또한 분배법칙이 적용되기 때문에 반복 사용에 문제가 없다.

[dradra0905]

질문 : 수학적 지식이 필요한 문제가 코테에 나오나?

• 웬만해서는 나오지 않는다.
• 나온다면 지문에서 알려주지 않을까?

[dradra0905]

문제 : 최대 합 순서쌍의 개수
질문 : 누적합 배열을 입력 받으면서 하는 방법

• 요런 느낌?

for (int i = 0; i < N; i++) {
	arr[i] = Integer.parseInt(st.nextToken());
	prefix[i + 1] = prefix[i] + arr[i];
}

[dradra0905]

문제 : 구간 성분
질문 : 해싱 하는 방법..?

• 설명을 잘 이해하지 못했습니다.. 죄송합니다..
• 자연어 처리..?
• 세연님의 정리