멍띠프로그래밍

투포인터 

- 배열이나 리스트에서 '두개의 포인터를' 사용하여 '특정 조건을 만족하는 부분 구간'을 효율적으로 탐색하는 알고리즘

- 정렬되어 있는, 배열 또는 리스트의 경우에 사용함

투 포인터 방법

1단계 : 배열 또는 리스트의 시작 위치에서 첫 번째 포인터와 두번째 포인터 설정

2단계 : 두 포인터 사이의 구간을 조사하고 조건 확립

3단계 : 조건 만족할 경우, 종료

4단계 : 조건이 만족하지 않을 경우, 첫번째 또는 두번째 포인터로 이동

5단계 : 2단계로 돌아가 재수행

투 포인터 시간 복잡도

- 투 포인터 알고리즘은 선형시간 복잡도를 가지며, 효율적이다.

- 한번의 반복으로 모든 요소를 처리

- 빅오 표기법으로  O(N), 배열 또는 리스트의 크기에 비례하여 수행시간 증가

투 포인터의 종류

1) 고정 길이 슬라이딩 윈도우

  - 고정된 길이의 윈도우를 사용하여 배열이나 리스트 탐색

  - 아래 이미지는 위도우 사이즈를 3으로 고정한 후 움직이는 모습

  - 배열의 합 또는 평균을 계산하는 문제에 사용됨

2) 가변 길이 슬라이딩 윈도우

  - 가변 길이의 윈도우를 사용하여 배열이나 리스트를 탐색

  - 최소 길이 부분 배열이나, 최대 길이 부분 배열을 찾는 문제에 사용됨

3) 두 포인터의 합과 차

  - 배열이나 리스트에서 두개의 포인터를 사용하여 합이나 차를 계산하는 문제를 해결

  - 두 요소의 합이나 차가 주어진 값과 일치하는지 확인하는 문제에 사용됨

투 포인터 단계별 백준문제

https://www.acmicpc.net/step/59

쉘스크립트로 자동화를 하려고하는데, 아래와 같이 에러가 발생했다.

​

warning: here-document at line 1 delimited by end-of-file (wanted `EOF')

​

쉘 스크립트 자체를 공부하지않고, 필요한 부분만 확인하면서 개발했기에... 해결하는데 너무 오래 걸렸다.

​

해결방법은 너무 간단하다.....

​

원인

EOF 앞 또는 뒤에 공백이나 탭이 있을 경우, 발생한다.

​

​

해결방법

공백이나 탭을 삭제하기

DFS를 이용한 문제였습니다.

package algoridm;

import java.util.*;
public class 섬의개수 {

	private static int w;
	private static int h;
	
	private static int[][] arr;
	private static boolean[][] visited;
	private static int[] dx = {0, 0, 1, 1, -1, -1, 1, -1};
	private static int[] dy = {1,-1, 1, -1, 1, -1, 0, 0};
	
	private static int cnt = 0;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true) {
			cnt = 0;
			w = sc.nextInt();
			h = sc.nextInt();
			if(w==0 &&h==0)break;
			sc.nextLine();
			

			arr = new int[h][w];
			visited = new boolean[h][w];
			
			for(int i=0; i<h;i++) {
				String str = sc.nextLine().replace(" ", "");
				for(int j=0; j<str.length();j++) {
					arr[i][j] = str.charAt(j)-'0';
				}
			}
			
			for(int i=0; i<h;i++) {
				for(int j=0; j<w;j++) {
					if(!visited[i][j] && arr[i][j]==1) {
						dfs(i,j);
						cnt++;
					}
				}
			}
			System.out.println(cnt);
		}
	}
	
	private static void dfs(int x, int y) {
		visited[x][y] = true;
		
		for(int i=0; i<8;i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx>=0 && ny >=0 && nx<h && ny<w) {
				if(!visited[nx][ny] && arr[nx][ny]==1) dfs(nx,ny);
			}
		}
	}

}

1단계 무난히 풀수 있는 문제 였습니다.

​

if문과 for문만 잘 사용한다면 쉽게 풀 수 있을거 같습니다

정렬해서 푸는 방법도 있지만, 저는 정렬을 사용하지 않고 풀었습니다.

나의 풀이

class Solution {
    public int[] solution(int[] lottos, int[] win_nums) {
        int[] answer = new int[2];
        
        for(int i=0; i<lottos.length;i++){
            if(lottos[i]==0){//로또 번호 0인값 체크
                answer[0]++; // 0번째 인덱스에는 최대 많이 맞춘 갯수를 넣기 위해 추가
                continue;
            }
            for(int j=0; j<win_nums.length;j++){
                if(lottos[i]== win_nums[j]){ //로또번호가 맞을 경우
                    answer[0]++;// 0번째 인덱스에는 최대한 많이 맞춘 갯수를 넣기위해 추가
                    answer[1]++;// 1번째 인덱스는 가장 적게 맞춘 갯수를 넣기 위해 일치할때만 증가
                    break;
                }
            }
        }
  
        for(int i=0; i<2;i++){ // 0번째, 1번째 인덱스
             if(answer[i]==6)answer[i]=1; //1등
             else if(answer[i]==5)answer[i]=2;//2등
             else if(answer[i]==4)answer[i]=3;//3등
             else if(answer[i]==3)answer[i]=4;//4등
             else if(answer[i]==2)answer[i]=5;//5등
             else answer[i]=6;//꼴등
        }
        return answer;
    }
}

다른 풀이

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] solution(int[] lottos, int[] win_nums) {
        Map<Integer, Boolean> map = new HashMap<Integer, Boolean>();
        int zeroCount = 0;

        for(int lotto : lottos) {
            if(lotto == 0) {
                zeroCount++;
                continue;
            }
            map.put(lotto, true);
        }


        int sameCount = 0;
        for(int winNum : win_nums) {
            if(map.containsKey(winNum)) sameCount++;
        }

        int maxRank = 7 - (sameCount + zeroCount);
        int minRank = 7 - sameCount;
        if(maxRank > 6) maxRank = 6;
        if(minRank > 6) minRank = 6;

        return new int[] {maxRank, minRank};
    }
}

아직 검색이나 자동완성이 없는 경우

Map, Set 같은 자료구조를 사용하기 힘들어서 시도해보지 못했다.

​

자동완성이 없을 때도 사용 할 수 있게 연습을 계속 해야겠다.

https://programmers.co.kr/learn/courses/30/lessons/77484?language=java#

BFS를 이용한 문제 였습니다.

​

Node 클래스를 만들어 x,y의 값을 저장하여 사용하며,

​

dx,dy 배열를 이용하여 위치를 상,하,좌,우 이동하면서 탐색 할 수 있게 하였습니다.

import java.util.*;

class Node{
	int x;
	int y;
	
	public Node(int x, int y) {
		this.x = x;
		this.y = y;
	}
	
	public int getX() {
		return this.x;
	}
	
	public int getY() {
		return this.y;
	}
	
}

public class 미로탈출 {
	
	static int N,M;
	static int[][] grph = new int[201][201];
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		sc.nextLine(); //Remove buffer
		for(int i=1; i<=N;i++) {
			String str = sc.nextLine();
			for(int j=1; j<=M;j++) {
				grph[i][j]= str.charAt(j-1)-'0';
			}
		}
		
		System.out.println(bfs(1,1));

	}
	
	public static int bfs(int x, int y) {
		
		int dx[] = {1,-1,0,0};
		int dy[] = {0,0,1,-1};
		
		Queue<Node> queue = new LinkedList<>();
		queue.offer(new Node(x,y));
		
		while(!queue.isEmpty()) {
			Node node = queue.poll();
			x = node.getX();
			y = node.getY();
			for(int i=0 ; i<4;i++) {
				int nx = x+dx[i];
				int ny = y+dy[i];
				if(nx<1 || nx>N  || ny<1 || ny>M) continue;
				if(grph[nx][ny]==0)continue;
				if(grph[nx][ny]==1) {
					grph[nx][ny] = grph[x][y]+1;
					queue.offer(new Node(nx,ny));
				}
			}
		}
		
		return grph[N][M];
	}
	
}

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

아직 BFS와 DFS를 사용하여 문제를 풀이하는데

익숙하지 않아,

복습과 여러문제를 풀어서

익숙해 져야할거 같습니다.

​