집에가고싶을때마다

•  About
•  Project
•  IT
•  Travel
•  ETC

문제 www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net - DFS/BFS 문제이다. - 바이러스가 최소 개수가 될 수 있도록 벽 3개를 반드시 세워야 한다. - 시간제한이 2초로 꽤나 넉넉한 문제이다. 해설 및 코드 - 시간초과가 날까봐 쉽게 접근하지 못했던 문제이다. - 시간은 꽤 넉넉하니, 모든 경우의 수를 세면 됐었다. - 백트레킹으로 벽을 세울때/세우지 않을 때를 나눠서 3개를 세우면 바이러스를 퍼트린다. import java.util.ArrayList; impor..

문제 - 백준 문제인 '특정 거리의 도시 찾기_18352'를 이코테에서 문제로 나왔다. - 거리가 1인 N개의 도시 - M개의 간선 - 최단거리 K인 모든 도시 번호 출력, 없으면 -1 - X부터 시작 해설 및 코드 - 거리가 1이므로 BFS로 간단하게 풀 수 있는 문제이다. - 만약 거리가 1이 아니라면, 다익스트라로 접근하면 된다. import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class BOJ특정거리의도시찾기_18352 { private static int K; private static ArrayList[] al; public static v..

문제 - N개의 도시, M개의 간선, 시작도시 C가 주어진다. - X, Y, Z로 간선 정보(X -> Y, Z는 무게)가 주어진다. - 시작도시 C에서 갈 수 있는 모든 도시의 개수와 최대 걸리는 시간 해설 및 코드 import java.util.Arrays; import java.util.Scanner; public class 전보 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); int C = sc.nextInt(); int[][] arr = new int[N+1][N+1]; int[] D = new int[N+1]; Arrays...

문제 - 1번부터 N번까지의 회사 존재 - 1번 회사를 시작으로 K번 회사를 무조건 방문 후 X번 회사에 도달 - 최단거리 해설 및 코드 - 해당 문제는 플로이드 와샬로 간단하게 풀 수 있다. import java.util.Arrays; import java.util.Scanner; public class 미래도시 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); int[][] map = new int[N + 1][N + 1]; for (int i = 0; i < map.length; i++) { Arrays.fill(map[i], 9..

문제 - N의 길이 만큼 숫자 배열 - M만큼 숫자 배열의 숫자를 더함 - 숫자는 반복 할 수 있으나, K만큼 연속적으로 반복 가능 - 가장 큰 수 찾기 예시) N=5, M=8, K=3 list = [2, 4, 5, 4, 6] 일 때, 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5를 더해 가장 큰 수인 46을 만들 수 있음 K = 3이므로 가장 큰 수인 6이 3번 반복 후 그 다음 큰 수인 5가 한 번 나옴 -> 다시 가장 큰 수인 6을 K만큼 더해줌 해설 및 코드 - 그리디로 가능 - 반복문을 통해서도 가능 - 식을 세워서 문제를 풀 수 있다. N, M, K = map(int, input().split()) arr = list(map(int, input().split())) arr.sort(re..

문제 - 총 N권의 책을 최대 몇 명에게 나눠 줄 수 있는지 찾는 문제 - 학생들은 a에서 b까지 책 번호 내에서 책을 받는다. 해설 및 코드 참고 블로그: steady-coding.tistory.com/230 [BOJ] 백준 9576번 : 책 나눠주기 (JAVA) 문제 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까 steady-coding.tistory.com - 해당 문제는 그리디로 해결이 가능하다. - b로 정렬 후 a로 정렬한다. - 그 이유는 해당 블로그에 잘 나와있다. # 그리디 T = int(input()) for _ in range(T): N, M = ..

문제 - x랑 y를 따로따로 정렬하면 된다. - 간단한 문제 해설 및 코드 - 간단하지만 python 초보는 열심히 틀렸다. - 아무래도 띄어쓰기 문제인듯... 백준 문제가 좀 아리까리했다. N = int(input()) points = [] for _ in range(0,N): [x, y] = map(int, input().split()) points.append( [x, y] ) points = sorted(points) for i in range(N): print(points[i][0], points[i][1]) Python 문법 정리 - 원하는 변수를 list로 담기 [x, y] = map(int, input().split())

문제 - 입력받은 문자들을 1. 크기 2. 알파벳 순서로 정렬하는 것이다. 해설 및 코드 - java로 생각했을 땐, priorityQueue를 커스텀하여 이용했을 것이다. 첫 번째로 길이를 비교하고, 같은 경우에는 알파벳으로 비교 - Python의 prioirtyQueue를 검색해보니 heapq를 사용하긴 했지만, 내가 원하는 custom을 하는 것이 불편하였다. - 결국 문제를 검색해서 답을 보고 해버렸다ㅠㅠ 문법이나 열심히 알아야겠다. import heapq N = int(input()) arr = [] # 단어의 길이와 단어 담기 for _ in range(0, N): word = str(input()) arr.append((len(word), word)) # 중복 제거 arr = list(set..

문제 - A배열과 B배열을 곱했을 때, 가장 작은 S를 찾으면 된다. - 각 배열에 담긴 것은 한 번씩만 사용하면 된다. - A는 재배열이 가능하지만, B는 재배열이 불가능하다. 해설 및 코드 - 조건으로 B는 재배열이 불가능하다고 나와있지만, 사실상 가장 작은 S를 찾으면 되기 때문에 큰 상관이 없다. - 가장 큰 숫자와 가장 작은 숫자를 곱해주면 된다. - A는 오름차순으로, B는 내림차순으로 정렬 후 두 배열을 곱한 숫자를 S에 더해주면 된다. N = int(input()) A = list(map(int, input().split())) B = list(map(int, input().split())) # 배열 정렬 A.sort() B.sort(reverse=True) S = 0 for i in ra..

문제 - 입력받은 문자열을 명령어를 통해 수정하는 문제이다. - 커서 _ a _ b _ c _ d _ 문자열의 길이(L) + 1의 위치 개수를 가진다. - 커서이동: L(왼쪽), D(오른쪽) - 문자: B(커서 왼쪽 삭제), P x('x' 문자를 커서 왼쪽에 삽입) 해설 및 코드 - 처음에는 list의 insert, pop을 이용해서 문자열의 in/out을 실행했다. - 시간초과 발생 list의 insert(N), pop(N)의 시간복잡도는 O(n)을 가진다. 해결방법 - stack, pop의 경우 in/out의 시간복잡도는 O(1)이다. - 내가 원하는 위치(N)에 숫자를 넣기 위해서는 커서를 기준으로 left / right로 stack을 나눈다. - python의 경우 stack이든 queue든 li..