Algorithm Study
[코트드리/Java] 최적의 십자 모양 폭발
풀이🛫 import java.util.Scanner; public class Main { public static final int DIR_NUM = 4; public static final int MAX_N = 50; public static final int[] dx = new int[]{-1,0,1,0}; public static final int[] dy = new int[]{0,1,0,-1}; public static int n, ans; public static int[][] orgGrid = new int[MAX_N][MAX_N]; public static int[][] grid = new int[MAX_N][MAX_N]; public static int[][] temp = new int[M..
[코드트리/Java] 금 채굴하기
풀이🛫 import java.util.Scanner; public class Main { public static final int MAX_N = 20; public static final int MAX_M = 10; public static int n, m; public static int[][] grid = new int[MAX_N][MAX_N]; // 채굴에 들어가는 비용 public static int getArea(int k) { return k*k + (k+1)*(k+1); } // 주어진 k에 대해 채굴 가능한 금의 개수 public static int getNumOfGold(int x, int y, int k) { int numOfGold = 0; for (int i=0; i
프로세스와 쓰레드 (by 얄코)
링크 : https://www.youtube.com/watch?v=iks_Xb9DtTM 용어 설명 프로그램 : 🏪 식당 → 배를 채우는 서비스 제공 윈도우에서 .exe라는 이름이 붙은 파일 프로세스 : 👨🏻🍳 요리사 → 조리하는 기능 프로그램이 실행되서 돌아가고 있는 상태 컴퓨터가 일을 하고 있는 상태 운영체제가 여러개의 프로세스를 돌리기 때문에 컴퓨터로 멀티태스킹이 가능 동시적(Concurrentcy), 병렬적(Parallelism) 작업의 혼합으로 이루어짐 컴퓨터의 자원을 분할해서 사용 → 하나의 프로세스는 다른 프로세스에 접근하지 못함 쓰레드 : 🍜 조리 공간 → 조리를 위한 작업 한 프로세스 내부에서 여러 갈래의 작업이 이루어짐 프로세스에서 주어지는 자원을 모든 쓰레드가 공유 cf. 속도와 효율..
자바에서 static 변수의 사용
static 변수를 사용할 때 myStaticVariable 변수는 클래스를 이용하는 전역에서 공유 myStaticVariable을 obj1을 통해 정의했지만, obj2에서도 동일한 myStaticVairable 메모리를 가리키고 있음 public class MyClass { static int myStaticVariable; // 정적 변수 public static void main(String[] args) { MyClass obj1 = new MyClass(); MyClass obj2 = new MyClass(); obj1.myStaticVariable = 10; // obj1의 인스턴스에서 정적 변수에 값을 할당 System.out.println(obj2.myStaticVariable); // 1..
[백준 파이썬] #11003. 최솟값 찾기
풀기 전 생각해보기😮 정렬을 사용할 수 없음 : 최대범위 값이 너무 크다 슬라이딩 윈도우, 덱 자료구조를 이용해서 O(n) 시간복잡도로 풀기 풀이🛫 from collections import deque N, L = map(int, input().split()) arr = list(map(int, input().split())) myDeque = deque() # ([인덱스][값]) 형태로 myDeque에 데이터 관리 for i in range(N): # 새로운 값이 기존의 값보다 클 때까지 기존의 값 (끝에서부터) 제거 while myDeque and myDeque[-1][0] > arr[i]: myDeque.pop() myDeque.append((arr[i], i)) # 새로운 값 입력 # 슬라이딩 윈..
[BOJ JAVA] #2750 수 정렬하기
풀이🛫 import java.io.IOException; import java.io.InputStreamReader; import java.io.BufferedReader; import java.util.Arrays; 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()); // 입력되는 수를 arr에 기록 int[] arr = new int[n]; for (int i = 0;..
[백준 파이썬] #11725. 트리의 부모 찾기
풀기 전 생각해보기😮 가급적 pypy3로 채점할 것을 추천한다 - python3로 채점이 정말 오래 걸렸다 트리 구조를 그리고, 각 노드의 부모를 찾는 문제 DFS로 풀 경우 recursionlimit을 10**6까지는 열어둬야 한다 풀이🛫 BFS 풀이 from collections import deque def bfs(node): queue = deque() queue.append(node) while queue: n = queue.popleft() for i in graph[n]: if parent[i] == -1: parent[i] = n queue.append(i) N = int(input()) graph = [[] for _ in range(N+1)] parent = [-1 for _ in ra..
[백준 파이썬] #1967. 트리의 지름
풀기 전 생각해보기😮 루트노드로부터 가장 먼 지점을 찾고, 해당 지점을 다시 루트 노드로하는 가장 먼 지점을 찾으면 트리의 지름을 구할 수 있다 recursionError가 발생하면 setrecursionlimit을 먼저 적용해보자 풀이🛫 구글링 참고 # 루트노드로부터 가장 먼 지점(가중치의 합)이 가장 큰 지점을 찾는 과정을 두번 반복 # visited를 음수값으로 설정하고 확인할 때마다 값을 바꿔준다면 방문 여부의 확인과 함께 거리를 나타낼 수 있다 import sys sys.setrecursionlimit(10**6) # 최대 재귀 깊이를 늘려주는 코드 def dfs(node, weight): for n, w in graph[node]: if visited[n] == -1: # 확인한 적이 없는 노..
[백준 파이썬] #2644. 촌수계산
풀기 전 생각해보기😮 트리 그래프 그리기, 방문 여부를 체크해주는 것으로 풀이가 가능 양방향 간선 vs 단방향 간선 연결관계 중 어떤 것을 선택해야 할까 BFS 풀이로 접근해보자 풀이🛫 구글링 참고 # 트리 구조를 그리고 visited 여부 체크 # 시작하는 노드로부터 부모, 자식에 관계없이 촌수를 체크할 수 있다 -> visited는 비교 노드간 거리가 됨 from collections import deque def bfs(node): queue = deque() # 덱 생성 queue.append(node) # 덱에 노드 정보 입력 while queue: # 큐가 살아있는 동안 node = queue.popleft() # 노트에서 하나의 요소를 빼서 for i in graph[node]: # 연결된 ..
[백준 파이썬] #2206. 벽 부수고 이동하기
풀기 전 생각해보기😮 일반적인 브루트 포스 방식으로 접근했을 때 시간초과가 발생했다. 모든 벽을 부셔서 최단 거리를 구해보는 알고리즘으로 풀 수 없다? → 시간초과 발생 : BFS 기본 시간 * 부술 수 있는 벽의 수 : 문제에서 1000*1000으로 시간제한에 걸린다 참고: https://www.acmicpc.net/board/view/84960 벽을 단 한번만 부실 수 있다는 조건을 이용해서 3차원으로 푸는 것이 일반적인 해답인 듯 하다. 풀이🛫 구글링을 참고 # 구글링 : 3차원 풀이 방식 사용 # 벽을 단 한번만 부술수 있기 때문에 벽을 부쉈는지의 여부를 하나의 차원에 나타내서 풀 수 있다 # 3차원방식 도입 풀이 from collections import deque dcol = [-1, 0, 1..