모각코 3회차 활동 내용 정리

목표 : 백준 알고리즘 푼 문제 블로그에 정리하고, 알고리즘특강 수업 내용 정리 완성하기

https://ethereal-coder.tistory.com/62

백준 [자바 java] 1026 : 보물

https://www.acmicpc.net/problem/1026

1026번: 보물

이 문제는 두 배열이 주어지고 두 배열간의 곱한 값을 더한 값이 최소가 되게 하는 문제이다.

핵심은 곱하는 두 수가 둘 다 큰 수이면 수가 많이 커지니까 이를 적절하게 조합하는 것이다. 가장 큰 수에는 가장 작은수를 곱하는 과정을 하기 위해서 두 배열을 다 정렬한 후 첫번째 배열은 앞에서부터, 두번째 배열은 뒤에서부터 곱해서 더해나가면 답을 구할 수 있다.

 

import java.util.*;
import java.io.*;


class Main{
	
 public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    
    StringBuilder sb = new StringBuilder();
    int n = Integer.parseInt(br.readLine());
    StringTokenizer st = new StringTokenizer(br.readLine());
    int[] arr1 = new int[n];
    int[] arr2 = new int[n];
  
    
    for(int i = 0;i<n;i++) {
    	int a = Integer.parseInt(st.nextToken());
    	arr1[i] = a;
    	

    }
    st = new StringTokenizer(br.readLine());
    
    for(int i = 0;i<n;i++) {
    	int a = Integer.parseInt(st.nextToken());
    	arr2[i] = a;
    	
    }
    
      Arrays.sort(arr1);
      Arrays.sort(arr2);
    
   
    
    int cnt = 0;

   
    
    for(int i = 0;i<n;i++) {
    	    	cnt+= (arr1[i]*arr2[n-i-1]);
    }
   
    System.out.println(cnt);

 }

 }

 

 

https://ethereal-coder.tistory.com/63

백준 [자바 java] 1541 : 잃어버린 괄호

https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

식이 주어지고 해당 식에 괄호를 적절히 쳐서 최종 값을 작아지게 만드는 문제이다.

 

해당 식은 더하기와 빼기만 있다. 이를 최대한 작게 만드려면 최대한 작은 수를 더하고 큰 수를 빼야한다.

따라서 괄호는 -를 제외하고 전부 넣어주면 된다. 

  ex)

  55 - (50 + 40)

  77 - (55 + 30 + 2) - (44) - (41 + 25)

 

나는 식을 입력받으면 -를 기준으로 이를 split하고 String배열에 넣어두었다. 그리고 이 배열을 하나씩 탐색하며 더한 값을 전체에서 빼준다( 첫 값은 더해준다.)

 

풀이코드

import java.io.*;
import java.util.*;

public class Main {
	   
	
	public static void main(String arg[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		  String[] arr = br.readLine().split("\\-");
		  int i;
		  int j;
		  int k;
		  int fin = 0;
		  String[] n;
		  for(i = 0;i<arr.length;i++) {
			  k=0;
			  n = arr[i].split("\\+");
			  for(j = 0;j<n.length;j++) {
				  k+=Integer.parseInt(n[j]);
				  
			  }
			  if(i == 0) {
			  fin +=k;
		  }
			  else {
				  fin-=k;
			  }
				  
	}
		  System.out.printf("%d",fin);
	}
}

 

 

https://ethereal-coder.tistory.com/64

백준 [자바 java] 11399 : ATM

https://www.acmicpc.net/problem/11399

11399번: ATM

이 문제도 예전에 c언어로 풀었어서 java로 다시 한번 풀었다.

사람마다 atm을 이용하는 시간이 주어지고 이를 사용하는 사람들이 기다리는 전체 시간의 최솟값을 출력하는 문제이다. 이때 이용시간이 작은 사람 순서대로 정렬한 후 이 순서대로 atm을 이용하면 되니까, 정렬한 후 여기다가 (전체사람 수 - 해당 수의 배열 순서)를 곱하면 된다. (첫번째 사람이 돈을 뽑을 동안 기다리는 사람들의 수는 전체이고, 두번째 사람이 돈을 뽑을 동안 기다리는 수는 전체-1이니까)

 

코드설명

import java.util.*;
import java.io.*;
import java.math.*;


public class Main {



    public static void main(String[] args) throws IOException {
        BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];


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

        Arrays.sort(arr);

        int ans = 0;

        for(int i = 0;i<n;i++){
            ans += arr[i] * (n-i);
        }

        System.out.println(ans);

    }
}

 

https://ethereal-coder.tistory.com/65

알고리즘 특강 1일차 : dx, dy 테크닉

dx,dy 테크닉은 좌표를 상하좌우로 움직이는 알고리즘을 풀 때 주로 사용하는 방법이다.

사실 이 방식은 문제를 풀고 다른 사람 코드랑 비교하는 과정에서 많이 보았는데, 그냥 편해서 사용하는줄만 알았던 코드가 하나의 알고리즘 개념이었다니 신기했고, 앞으로는 이 방법을 적극적으로 이용해야겠다는 생각이 들었다!

 

0이 입력되면 동쪽으로, 1이 입력되면 남쪽으로, 2가 입력되면 서쪽으로 , 3이 주어지면 북쪽으로 가는 코드를 짜려고 한다. 

 

int nowNum = 0;

int x = 1;
int y = 1;

if(nowNum == 0){
  x++;
  }
  
else if(nowNum = 1){
  y--;
  }
  
else if(nowNum = 2){
  x--;
  }
  
else if(nowNum =3){
  y++;
  }

이러한 방식으로 코드를 짜면 직관적일 수는 있지만, 오류가 발생할 확률이 높고, 현업에서 프로젝트를 할 때 비효율적일 수 있다.

 

따라서 이때 쓰는 방법이 dx,dy테크닉이다.

 

dx dy 배열에는 위와 같이 1과 -1을 엇갈아 넣어준다.

이를 활용하면,

int nowNum = 2;

int x = 1;
int y = 2;

int[] dx = {1,0,-1,0};
int[] dy = {0,-1,0,1};

x += dx[nowNum];
y += dy[nowNum];

이렇게 간단하게 코드를 짤 수 있다.

 

회전문제에 적용하는 방법

 

어떠한 명령이 주어지면 90도로 회전하는 문제 역시 이 테크닉을 이용하여 풀 수 있다.

 

현 위치를 나타내는 변수가 있고, 이 변수가 0이면 동쪽, 1이면 남쪽, 2이면 서쪽, 3이면 북쪽을 나타낸다고 했을 때,시계방향으로 회전하는 문제에서 90도로 돌으라는 명령어를 받으면 현재 위치에 1을 더하면 된다.

이때 3에서 1을 더하면 4가 아니라 0이 되어야 하므로  (현재 변수 +1 ) % 4 를 하면 된다.

 

만약 반시계방향으로 한다면? -1을 할 수도 있지만 처리하기가 더욱 어렵다. 이럴 때에는 반시계방향으로 한번 이동한 값이 시계방향으로 3만큼 이동한 값이랑 같다는 것을 이용하면 된다.

 

인접한 격자 탐색하기

 

위와 같이 dx dy 배열을 만들고, 이를 차례로 더하거나 빼서 인접한 격자를 탐색하면 된다. 이 때 해당 배열을 더하거나 뺐을 때 이 격자가 존재하는지를 알아보는 과정이 꼭 필요하다.

 

int nowNum = 2;

int x = 1;
int y = 2;

int[][] a = { 
            {0, 0, 0, 1, 0},
            {0, 1, 1, 1, 0},
            {0, 0, 0, 0, 1},
            {1, 0, 1, 1, 1},
            {1, 0, 1, 1, 0}
        };

int[] dx = {1,0,-1,0};
int[] dy = {0,-1,0,1};

x += dx[nowNum]; 
y += dy[nowNum];

System.out.println(a[x][y] == 0); // 만약 x가 -1이면 해당 격자는 존재하지 않으므로 에러가 발생한다.

그리고 일정한 범위 안에서 0과 1이 있을 때 1의 갯수를 세고 싶으면 이를 다 더하는 것도 하나의 방법이다.

 

돌면서 숫자 적기

 

1	2	3	4	5
14	15	16	17	6
13	20	19	18	7
12	11	10	9	8

이와 같이 돌면서 숫자를 채워주는 기능을 구현 할 때에도 dx dy 배열을 사용한다. 

위에서 회전문제에서 사용한 방법과 동일한데, 방향을 나타내는 변수를 하나 생성하고, (변수 + 1)%4 을 사용하여 방향을 정해준다. 탐색 중 길이 막혔을 때 회전하는 것을 구현을 잘 하면 된다.

 

import java.io.*;
import java.util.*;
import java.math.*;


public class Main {
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] arr = new int[n][m];

        int num = 1;

        int x = 0;
        int y = 0;
        int d = 0;
        arr[x][y] = 1;

        int[] dy = {1,0,-1,0};
        int[] dx = {0,1,0,-1};


        while(num != n*m){
            if(x + dx[d] < 0 || x + dx[d] >= n || y + dy[d] < 0 || y + dy[d] >= m ||
               arr[x + dx[d]][y + dy[d]] != 0){

                d = (d +1) % 4;
               }
               num++;  

              x += dx[d]; 
              y += dy[d];

               arr[x][y] = num;
               

        }

        for(int i = 0;i<n;i++){
            for(int j = 0;j<m;j++){
                System.out.printf("%d ",arr[i][j]);
            }
            System.out.println();
        }

        


    }
}

위와 같이 현재 방향에서 직진했을 때 array를 벗어난다거나, 값이 0이 아닐 때 (이미 채워져 있을 때)에는 회전하게 한다.

 

느낀점 

알고리즘 공부를 혼자 하다보니까 놓친 부분이 꽤 있는 것 같았고, 앞으로 이를 보완하기 위해 노력해야겠다.