codejcd 기술 블로그

문제

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

분석/설계

전형적인 그래프를 탐색하는 DFS/BFS 유형의 문제이고

그래프 상 노드(컴퓨터)가 100대 이하이므로 완전 탐색으로 접근 가능한 문제로 파악했고

DFS로 구현했습니다.

구현 코드

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	
	static boolean[] visted;
	static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
	
	public static void dfs(int V) {
		visted[V] = true;

		for(int i=0; i<graph.get(V).size(); i++) {
			int W = graph.get(V).get(i);
			if(!visted[W]) dfs(W);	
		}
	}
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int N = scanner.nextInt(); // 컴퓨터 수
		int M = scanner.nextInt(); // 연결된 컴퓨터 쌍의 수
		
		for(int i=0; i<=N; i++) { // 인접 배열 리스트 초기화
			graph.add(new ArrayList<Integer>());
		}
		
		visted = new boolean[N+1]; // 방문 여부 판단할 배열
		
		scanner.nextLine();
		for(int i=0; i<M; i++) { // 인접 배열 리스트 값 세팅 
			int v1 = scanner.nextInt();
			int v2 = scanner.nextInt();
			graph.get(v1).add(v2); 
			graph.get(v2).add(v1);
		}
		
		dfs(1);
		
		int cnt = 0;
		for(int i=0; i<visted.length; i++) {
			if(visted[i]) cnt++;
		}
		System.out.println(cnt-1);
		scanner.close();
	}
}

정리

문제를 읽어보면 1번 컴퓨터부터 시작한다는 조건이 있고 

1번 컴퓨터를 통해 바이러스에 걸리는 컴퓨터 수를 구해야하므로

1번 컴퓨터까지 카운트된 숫자는 제외해줍니다.

참고

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

Git Flow 전략

• master : 제품으로 출시될 수 있는 브랜치
• develop : 다음 출시 버전을 개발하는 브랜치
• feature : 기능을 개발하는 브랜치
• release : 이번 출시 버전을 준비하는 브랜치
• hotfix : 출시 버전에서 발생한 버그를 수정하는 브랜치

실무에서는 SVN과 Git 으로 형상 관리 툴로 사용하고 있습니다.

제가 속한 파트는 아쉽게도 SVN으로 아직 형상 관리 중 입니다.

개인적으로 Github에 필요한 소스 정리를 하면서 Git을 맛 보고 있기는 하지만

Git의 다양한 브랜치 전략을 써보기에는 한계가 있어 업계의 다른 분들은

어떤 전략을 실무에서 적용하는지 한번 살펴보겠습니다.

레퍼런스를 찾아보다가 잘 정리된 우아한 형제들 기술 블로그의 글을 확인하고 공유해봅니다.

https://techblog.woowahan.com/2553/

이슈

일부 서비스에서 페이지 이동이 안되고 Proxy Error(502)가 발생.

과정 및 해결

1차 - 에러 로그로 원인 및 해결 방법 찾기

Apache와 Tomcat 로그 부터 확인. 

Tomcat에서는 별다른 로그를 찾을수 없었고 Apache 로그에서 Timeout 로그를 확인 가능했음.

따라서 처리과정이 길어지면서 Apache나 Tomcat에 Timeout 설정을 초과하면서

발생하는 에러로 추정하고 상용 서버가 아닌 테스트 서버에서도 동일하게 발생하는지 확인.

테스트 서버도 재현이 가능했고 테스트 서버 Timeout 설정을 수정하면서 테스트했으나

Timeout 설정을 길게 늘려줘도 해당 시간만큼 대기하다가 똑같은 proxy Error가 발생.

2차 - 범위를 좁혀가며 원인 및 해결 찾기

1차 과정에서 단순 처리 시간이 길어져서 발생하는 것이 아닌 것으로 추정하고

방향을 바꿔 서버 로그를 세세하게 살펴보다가 의심가는 구간에 서버 로그를 더 추가함.

특정 통신 모듈 전까지만 로그가 출력되고 이후에는 로그가 출력되지 않는 것을 확인.

3차 - 통신 모듈 테스트

2차에서 통신 모듈에서 무엇인가 문제가 발생하는 것을 인지.

통신 모듈을 주석 처리 하고 테스트. 그러자 통신 모듈 이후 로그가 출력.

통신 모듈을 세세하게 들여다보니 2가지 문제점이 확인됨.

하나는 HTTPS 통신을 하는데 SSL Context 설정이 보이지 않음.

다른 하나는 헤더에 쿠키 세팅을 확인.

쿠키 값을 까보니 자사의 쿠키를 전송. 

원격지 서버를 관리하는 담당자에게 쿠키의 용도를 확인.

원격지는 사용하지 않는다고 답신 받고 쿠키 제거 후 테스트 하니 정상 동작.

원인

POST Method로 쿠키를 다른 도메인간 전송하여 발생하는 문제.

SameSite Cookie 정책에 영향을 받는다.

통신 모듈에서 잘못된 쿠키 사용으로 지연이 되면서 Timeout 시간이 초과되자 Proxy Error 페이지를 노출.

자세한 정책 내용은 아래를 확인하면 된다.

https://web.dev/i18n/ko/samesite-cookies-explained/

문제

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

분석/설계

DFS와 BFS로 완전 탐색하여 접근하는 방향으로 가닥을 잡고

인접한 상하좌우를 탐색하는 것이므로 BFS가 구현이 쉬울 것 같아 선택했다.

다른 문제들과 달리 한칸씩 띄워서 입력 받지 않기때문에 이런 부분이 조금 달랐던 것 같고

결국 입력 값을 받아 초기화하고 BFS로 어떻게 기준을 잡고 탐색하는지가 중요했던 문제입니다.

구현 코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Dot{ // X,Y 좌표를 저장하는 클래스
	int x;
	int y;
	
	public Dot(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}
	
	public int getX() {
		return x;
	}
	public void setX(int x) {
		this.x = x;
	}
	public int getY() {
		return y;
	}
	public void setY(int y) {
		this.y = y;
	}				
}

public class Main {
	static ArrayList<Integer> count = new ArrayList<>();
	 // 상, 하, 좌, 우를 탐색하기 위한 배열
	static int dx[] = {1,-1,0,0};
    static int dy[] = {0,0,1,-1};
	
	public static void bfs(int arr[][], boolean visited[][], Dot dot) {
		Queue<Dot> q = new LinkedList<Dot>();
		q.offer(dot);
		visited[dot.getX()][dot.getY()] = true;
		int cnt = 0; // 주변에 존재하는 집의 수를 저장
		
		while(!q.isEmpty()) {
			Dot temp = q.poll();
			int x = temp.getX();
			int y = temp.getY();
			cnt++;
			
			for(int i=0; i<4; i++) { // 상하좌우 탐색
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				// 맵의 범위를 벗어나는 좌표는 무시
				if(nx>=arr.length || nx<0 || ny>=arr[nx].length || ny < 0) continue;
				
				// 이미 방문한 경우도 무시
				if(visited[nx][ny]) continue;
				
				if(arr[nx][ny] == 1) {
					visited[nx][ny] = true;
					q.offer(new Dot(nx, ny));
				}
			}
		}
		count.add(cnt);
	}
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt(); // 맵의 크기 N
		int arr[][] = new int[N][N]; // N x N map
		boolean visited[][] = new boolean[N][N]; // N x N 크기의 방문여부 배열
		
		scanner.nextLine();
		for(int i=0; i<arr.length; i++) { // 맵 입력 받은 값으로 초기화
			String[] temp = scanner.nextLine().split("");
			for(int j=0; j<arr[i].length; j++) {
				arr[i][j] = Integer.parseInt(temp[j]);
			}
		}
		Dot dot;
		
		for(int i=0; i<arr.length; i++) {
			for(int j=0; j<arr[i].length; j++) {
				if(arr[i][j] == 1 && visited[i][j] == false) { // 맵을 탐색하면서 아파트이면서 방문하지 않은경우
					dot = new Dot(i, j);
					bfs(arr, visited, dot);
				}
			}
		}
			
		System.out.println(count.size());
		Collections.sort(count);
		for(int i=0; i<count.size(); i++) {
			System.out.println(count.get(i));
		}
		
		
		scanner.close();
	}
}

정리

좌표에 대해서 어떻게 코드로 구현할지

BFS를 구현할 때 큐에 넣고 큐에서 꺼내는 기준을 무엇으로 할지가 핵심이고

답을 구하기 위해서 어떤 값이 필요할지 처음에 잘 정의한다면 그렇게 어려운 문제는 아닙니다.

FS나 DFS를 어떻게 응용할지 많이 문제를 접해봐야할 것 같습니다.

참고

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

이번 문제는 백준 알고리즘 사이트에 문제입니다.

DFS와 BFS 관련 문제로 기본/핵심 적인 문제입니다.

문제

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

분석/설계

제목 부터과 DFS/BFS 이여서 당연히 DFS/BFS로 접근하였습니다.

기본적인 DFS/BFS 구현과 유사하지만 두 정점 사이에 여러개의 간선과 양방향 이라는 점에서 주의해야합니다.

처음에 양방향을 생각하지 않고 풀이 했을대, 예제 1번은 답이 나왔지만 2,3 번은 모두 오답이 었습니다. 

구현 코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class DFSBFS {

	static boolean[] visted;
	static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
	
	public static void dfs(int V) {
		visted[V] = true;
		System.out.print(V + " ");
		
		for(int i=0; i<graph.get(V).size(); i++) {
			int W = graph.get(V).get(i);
			if(!visted[W]) dfs(W);	
		}
	}
	
	public static void bfs(int V) {
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(V);
		
		visted[V] = true;
		
		while(!queue.isEmpty()) {
			int x = queue.poll();
			System.out.print(x + " ");
			for(int i=0; i<graph.get(x).size(); i++) {
				int W = graph.get(x).get(i);
				if(!visted[W]) {
					queue.offer(W);
					visted[W] = true;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int N = scanner.nextInt(); // 정점의 개수
		int M = scanner.nextInt(); // 간선 열결하는 두 정점의5 번호
		int V = scanner.nextInt(); // 시작할 정점 번호
		
		for(int i=0; i<=N; i++) { // 인접 배열 리스트 초기화
			graph.add(new ArrayList<Integer>());
		}
		
		visted = new boolean[N+1]; // 방문 여부 판단할 배열
		
		scanner.nextLine();
		for(int i=0; i<M; i++) { // 인접 배열 리스트 값 세팅 
			int v1 = scanner.nextInt();
			int v2 = scanner.nextInt();
			graph.get(v1).add(v2); 
			graph.get(v2).add(v1);
		}
		
		for(int i=1;i<=N;i++) { // 이동 간선의 이동 경우가 다수 존재할 경우 작은 정점부터 이동해야하므로 오름차순 정렬
			Collections.sort(graph.get(i));
		}
		
		dfs(V);
		visted = new boolean[N+1]; // dfs 수행 후 방문 여부 판단할 배열 초기화
		System.out.println();
		bfs(V);
		scanner.close();
	}
}

정리

DFS 재귀 함수로 BFS는 Queue를 이용해서 구현했다.

기본적인 그래프에 대한 DFS/BFS 를 구현하는 문제였고 사소한 구현 사항을 놓치지 않으면

쉽게 풀수 있는 문제입니다. 

참고

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

이번 문제는 프로그래머스 사이트에 공개된 문제입니다.

문제

https://programmers.co.kr/learn/courses/30/lessons/12913

분석/설계

땅따먹기 특수 규칙에 의해 주어진 land 2차 배열을 나올수 있는 경우의 수를 전부 탐색해서

최대값을 얻어야겠다고 생각했고, 바로 DFS를 떠올렸습니다.

하지만 DFS 사용 시 행의 개수가 100,000 이기 때문에 효율성 걸려서 코드 제출을 통과할수 없습니다.

구현 코드

// DFS 버전
public class Solution {

  static boolean[][] visited;
  static int res = 0;

    static int solution(int[][] land) {
        int answer = 0;
        visited = new boolean[land.length][4];
        pick(0,0,land);	
        answer = res;
        return answer;
    }
    
    static void pick(int row, int sum, int[][] land ) {
    	if(row == land.length) {
    		res = Math.max(res, sum);
    		return;
    	}
    	
    	for(int i=0; i<4; i++) {
    		if(!visited[row][i]) {
    			sum += land[row][i];
    			if(row < land.length-1) visited[row+1][i] = true;
    			pick(row+1, sum, land);
    			if(row < land.length-1) visited[row+1][i] = false;
    			sum -= land[row][i];
    			
    		}
    	}
    }
}

정답 코드(다른 사람의 코드와 비교)

class Solution {
    int solution(int[][] land) {
        int answer = 0;
     
        for(int i=1; i< land.length; i++) {
        	land[i][0] += Math.max(land[i-1][1], Math.max(land[i-1][2], land[i-1][3]));
        	land[i][1] += Math.max(land[i-1][0], Math.max(land[i-1][2], land[i-1][3]));
        	land[i][2] += Math.max(land[i-1][0], Math.max(land[i-1][1], land[i-1][3]));
        	land[i][3] += Math.max(land[i-1][0], Math.max(land[i-1][1], land[i-1][2]));
        }
        
        for(int i=0; i<4; i++) {
        	answer = Math.max(answer, land[land.length-1][i]);
        }
        
        return answer;
    }
}

비교/정리

DFS 사용 시 모든 경우의 수를 반복해서 계산하기 때문에 효율성이 떨어져 코드 제출 시 시간 초과가 발생합니다.

다이나믹 프로그래밍을 사용하면 효율성을 개선하고 비교적 쉽게 풀수 있는 문제입니다.

참고

https://programmers.co.kr/learn/courses/30/lessons/12913