2nd Meet - 코독하구만

Daily Object

    - 분할정복법 예제를 풀어보고, 지난 주 학습했던 시간복잡도를 예제에 적용해서 구해본다.

 

    - 웹크롤링 코드를 따라쳐보며 어떤 식으로 동작하는 지 알아본다.

Review

    - 알고리즘 예제를 풀며 시간과 메모리 비용을 줄이기 위해 메모리 할당 방법, 조건문 설정 등을

      생각하며 했더니 효율성이 훨씬 좋아졌다.  

 

    - 시간이 부족해 네이버 홈페이지를 크롤링하는 데에서 멈추었다. 

      다음 모각코엔 크롤링한 데이터를 분석하는 시간을 가져야겠다.

 

 

Divide And Conquer

     문제의 크기가 작다면 풀이가 쉽다. + 문제의 크기를 최소한으로 줄여 최소 크기의 문제를 풀어 나아간다.

 

           -> 작은 서브 문제를 만들고 이를 큰 문제에 적용함으로써 문제를 해결한다.

 

이번 시간에 풀어본 예제

1074번: Z

처음 생각한 풀이방법 

 

  1 ) 입력 N에 맞는 2^N x 2^N 크기의 정수배열을 생성한다.

  2 ) 칸 수 4 로 4등분이 가능하다면 분할한다. 이 때 Z모양을 생각하며 분할 순서를 정한다.

  3 ) 4등분이 불가능해진다면 Z모양대로 num ( 전역변수 )을 넣고 num +=1을 해준다.

  4 ) 모든 칸이 채워지면 해당 입력 r,c의 배열 값을 불러와 출력한다.

 

  -> 출력은 정답과 같음. 하지만 메모리 초과가 발생함

      Why?

          0 < N <16 인데 N = 15가 들어오면 생성되는 정수배열 Matrix[15][15]의 배열 1개당 1Byte라고 쳐도

          1GB가 된다. 

      Solution

          배열을 생성하지않고 찾아야할 r,c 좌표의 위치만을 생각하며 분할정복을 한다. 

 

다시 생각한 풀이방법

 

  1 ) 4등분을 할 때 좌표가 해당하는 사분면을 분할한다. num은 1, 2, 3, 4분면에 따라 다르게 가산된다. 

                                         ( 1사분면 A * 0/4  |  2사분면 A * 1/4  |  3사분면 A * 2/4  |  4사분면 A * 3/4 )

  2 ) 4등분이 불가능할 때 Z모양 중 ( r , c )좌표의 위치에 따라 num을 1~3을 가산하고, 리턴하여 종료한다.  

 

  -> 시간초과가 있지만 메모리초과는 일어나지 않았다.  

      ( 시간복잡도를 줄이는 방법은 더 생각해봐야겠다. )

 

백준 1074 - Z 코드

import java.util.Scanner;

public class Main {
	static int num = 0;
	static int result  = 0;

	public static void dac(int size, int row, int col, int r, int c) {
		if (size == 2) {

			if (((row <= r) && (r <= row + 1)) && ((col <= c) && (c <= col + 1))) {
				if ((row == r) && (col + 1 == c)) {
					num += 1;
				} else if ((row + 1 == r) && (col == c)) {
					num += 2;
				} else if ((row + 1 == r) && (col + 1 == c)) {
					num += 3;
				}
				result = num;
				return;
			} else {
				num += 4;
			}
		} else {
			if((r < row+size/2) && (c < col+size/2)){ 
				dac(size / 2, row, col, r, c);} // 1
			else if ((r < row+size /2 )&&( c >= col+size/2)){ // 2
				num += size*size/4;
				dac(size / 2, row, col+(size / 2), r, c);
			}
			else if ((r >= row+size/2 )&&( c < col+size/2)){ // 3
				num += size*size*2/4;
				dac(size / 2, row +(size / 2), col, r, c);
			}
			else{ // 4				
				num += size*size*3/4;
				dac(size / 2, row+(size / 2), col+(size / 2), r, c);
			}
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = (int) Math.pow(2, sc.nextInt());
		int r = sc.nextInt();
		int c = sc.nextInt();
		dac(N, 0, 0, r, c);
		System.out.println(result);
	}
}

 

 

 

 

웹 크롤링 

  간단한 웹크롤링 코드를 따라쳐보며 Naver 홈페이지의 Text 데이터와 Html을 크롤링했다. 

 

네이버 홈페이지 텍스트 크롤링

 

 

네이버 홈페이지 Html 크롤링