22년 1월 4주차 회고록 (스터디 자랑)

package week16.적록색약; import java.util.*; public class Main { private static boolean[][] isUsed; private static char[][] drugs; static int[] dX = new int[]{1, 0, -1, 0}; static int[] dY = new int[]{0, 1, 0, -1}; static int n; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); drugs = new char[n + 1][n + 1]; isUsed = new boolean[n + 1][n + 1]; for (int i = 0; i < n; i++) { String s = sc.next(); for (int j = 0; j < n; j++) { drugs[i][j] = s.charAt(j); } } //구역을 확인하기 int answer1 = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (!isUsed[i][j]) { bfs(i, j, drugs[i][j]); answer1++; } } } isUsed = new boolean[n + 1][n + 1]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (!isUsed[i][j]) { if (drugs[i][j] == 'R') drugs[i][j] = 'G'; } } } //구역을 확인하기 int answer2 = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (!isUsed[i][j]) { bfs(i, j, drugs[i][j]); answer2++; } } } System.out.println(answer1 + " " + answer2); } private static void bfs(int x, int y, char target) { Queue<int[]> q = new LinkedList<>(); q.add(new int[]{x, y}); isUsed[x][y] = true; while (!q.isEmpty()) { int[] xy = q.poll(); int currX = xy[0]; int currY = xy[1]; for (int i = 0; i < 4; i++) { int nX = currX + dX[i]; int nY = currY + dY[i]; if (nX < 0 && nX <= n || nY < 0 && nY <= n) continue; //OutOfArraysIndex 체크 if (!isUsed[nX][nY] && drugs[nX][nY] == target) { // 다음이 방문하지 않았고 문자가 같으면 isUsed[nX][nY] = true; q.add(new int[]{nX, nY}); } } } } }

package week16.타겟넘버; import java.util.Stack; public class Solution { static int answer; public int solution(int[] numbers, int target) { dfs(numbers, target, 0, 0); return answer; } private void dfs(int[] numbers, int target, int depth, int sum) { if (depth == numbers.length) { if (sum == target) answer++; } else { dfs(numbers, target, depth + 1, sum + numbers[depth]); dfs(numbers, target, depth + 1, sum - numbers[depth]); } } public static void main(String[] args) { int[] numbers = {1,1,1,1,1}; int target = 3; Solution solution = new Solution(); int solution1 = solution.solution(numbers, target); System.out.println(solution1); } }

import numpy as np def solution(numbers, target): def find_target(x): return x == target bef_cal = [0] for iter in range(len(numbers)): aft_cal = [0]*(2*len(bef_cal)) for bef_num_iter in range(len(bef_cal)): aft_cal[bef_num_iter*2] = bef_cal[bef_num_iter] -numbers[iter] aft_cal[(bef_num_iter*2 +1)] =bef_cal[bef_num_iter] + numbers[iter] bef_cal = aft_cal # print(bef_cal) # print(np.where(np.array(bef_cal) == target)[0]) return len(np.where(np.array(bef_cal) == target)[0])

from collections import deque dx = [0,1,0,-1] dy = [1,0,-1,0] def num_regions(i, j, N, grid, visited): queue = deque() group_color = grid[i][j] queue.append((i,j)) visited[i][j] = 1 while queue: x, y = queue.popleft() for i in range(len(dx)): tmp_x = x + dx[i] tmp_y = y + dy[i] if tmp_x < 0 or tmp_x >= N or tmp_y < 0 or tmp_y >= N: continue if visited[tmp_x][tmp_y] or grid[tmp_x][tmp_y] != group_color: continue visited[tmp_x][tmp_y] = 1 queue.append((tmp_x, tmp_y)) return 1 N = int(input()) grid = [input() for _ in range(N)] # 보통 사람 visited = [[0] * N for _ in range(N)] general_count = 0 for i in range(N): for j in range(N): if not visited[i][j]: general_count += num_regions(i, j, N, grid, visited) # 적록 색맹인 사람 for i in range(N): grid[i]=grid[i].replace("G","R") visited = [[0] * N for _ in range(N)] daltonism_count = 0 for i in range(N): for j in range(N): if not visited[i][j]: daltonism_count += num_regions(i, j, N, grid, visited) print(general_count, daltonism_count)

answer=0 def solution(numbers, target): def dfs(sum_,indx): global answer if(indx==len(numbers)): if(sum_==target): answer = answer+ 1 return dfs(sum_+numbers[indx],indx+1) dfs(sum_-numbers[indx],indx+1) dfs(0,0) return answer

import sys sys.setrecursionlimit(int(1e6)) def dfs(x,y,mode=0): if mode == 0: col = graph[x][y] visited[x][y] = True for i in range(4): nx = x +dx[i] ny = y +dy[i] if nx < 0 or nx >=n or ny < 0 or ny >= n: continue if visited[nx][ny] or graph[nx][ny]!=col: continue dfs(nx,ny,mode) # 적록 색약인 경우 else: col = graph[x][y] visited2[x][y] = True for i in range(4): nx = x +dx[i] ny = y +dy[i] if nx < 0 or nx >= n or ny < 0 or ny >= n: continue if visited2[nx][ny]: continue if col == 'R' or col == 'G': if graph[nx][ny] == 'R' or graph[nx][ny] == 'G': dfs(nx,ny,mode) else: if graph[nx][ny] != col: continue dfs(nx,ny,mode) n = int(input()) graph = [] for _ in range(n): graph.append(list(input())) visited = [ [False for _ in range(n)] for _ in range(n)] visited2 = [ [False for _ in range(n)] for _ in range(n)] count1, count2 = 0, 0 dx, dy = [0,0,-1,1], [-1,1,0,0] for i in range(n): for j in range(n): if not visited[i][j]: dfs(i,j) count1+=1 if not visited2[i][j]: dfs(i,j,1) count2+=1 print(count1,count2)

DFS와 BFS 모두 언제 사용해야할지 이제 감이 잡힌거 같습니다. 하지만 문제의 조건마다 사용하는 법을 적용시키기가 아직 어려웠던거 같습니다. 그래서 더 정확히 DFS와 BFS의 작동원리를 알아봐야겠다고 생각했습니다

적록 색약의 경우 pccp 시험에서 접한 적이 있는 문제와 유사해서 꼭 풀어보고 싶었는데 (인접한 색깔의 경우 같은 구역으로 간주해서 색깔을 칠하면 최종으로 몇개의 구역으로 나뉘는지) 같은 색깔이지만 다른 위치에 있는 경우 어떻게 처리해야하는지 까다로워서 풀지 못했다. DFS를 이용하면 된다고 하니 그 방법을 이용해서 다시 풀어봐야겠다.

파이썬에 대한 이해가 부족하다는 생각이 든 것이, 어떤 변수의 값을 변경하고 싶을 때 함수에 매개변수로 넘겨줘야 하는 지, 그렇게 하지 않아도 호출해서 변경이 될 수 있는지가 늘 헷갈린다. 함수 밖의 변수는 함수 내에서 호출이 안된다고 알고 있었는데 그렇지 않은 경우도 있는 것 같다. 중요한 문제이니 공부를 좀 해봐야겠다.

bfs / dfs 로 접근해서 풀어야겠다는 생각이 들었는데 정작 둘 중 어떤 방식으로 풀어야 조금 더 좋은 방법인지 아직 잘 모르겠습니다.

DFS와 BFS는 공식이 있는것 같으니 구조를 외워놓고 사용하면 좋겠다고 생각했습니다. 다만 사용할때 문제마다 적용하는방법이 다를 수 있으니 내부구조를 잘 파악해두어야 한다고 생각했습니다.

이번주는 꿀팁은 없는 것 같다. 그냥 습관적으로 시간 복잡도를 계산하는 것이 반복문을 바로 돌릴지 다른 방법을 생각할지에 도움을 주는 것이 아닌가 싶은 생각은 든다.

물론 최종적으로 사용하진 않았지만 PriorityQueue를 사용하는 연습을 해보았다.

조금 구글링을 해보니 파이썬으로 푼 대부분의 사람들이 deque라는 collections의 라이브러리를 이용해서 푸는데 collections를 잘 활용해봐야겠습니다.

이제 문제를 보면 어떻게 접근해야할지 아는정도는 된거같으니 좀 더 꾸준히 연습해서 더 효율적으로 깔끔하게 짜는 방법을 연구해 보아야 할 것 같습니다.

저번 주처럼 BFS나 DFS를 이용해서 더더 많은 문제를 풀어봐야할 것 같다는 생각을 했다.

알고리즘에 시간을 더 투자해야 할 것 같다. 요즘 프로젝트에 정신이 팔려서 알고리즘을 조금 대충 했던 것 같은데 그럴 때가 아닌 것 같다.

일주일에 두 문제를 풀기로 약속했는데 항상 한문제 밖에 못 푸는 것 같다 시간을 조금 더 투자해야겠습니다 ... ㅠ