집에가고싶을때마다

•  About
•  Project
•  IT
•  Travel
•  ETC

준비 겸, JAVA Stream에 익숙해지기 위해. 문제 https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 나이 - 이름으로 입력 받았을 때, 나이 순으로 정렬하고, 같은 경우 입력 순서대로 정렬한다. 해설 및 코드 public class 나이순정렬 { public static class User{ int age; String name; User(int a, String n){ this.age = a; this.name = n; } public int..

문제 LIS라는 대표적인 알고리즘 문제 중 하나이다. 가장 긴 증가하는 부분 수열의 길이를 리턴한다. 가장 긴 증가하는 부분수열 11053 문제는 O(n^2)으로 문제를 풀 수 있지만, 해당 문제는 O(nlogn)의 시간으로 코드를 짜야한다. https://jason9319.tistory.com/113 이 블로그에 설명이 잘 나와있지만, 공부하는 마음으로 작성한다. 해설 및 코드 - Lower Bound는 O(logn)의 시간을 소모한다. 이러한 이분탐색의 일종인 Lower Bound를 이용하여 O(nlogn)의 시간으로 해결한다. package BAEKJOON; import java.util.ArrayList; import java.util.Scanner; public class 가장긴증가하는부분수열2..

문제 - 구현의 기본적인 문제 - 반시계방향으로 배열의 각 원소를 하나씩 옮긴다. - R번 회전한다. 해설 및 코드 배열 회전 문제를 구현할 때, 그냥 보이는 대로 푸는 경우가 많다. -> 복잡성이 증가한다. 내가 구현한 배열 회전은 2개의 temp를 임시저장해서 사용했다. 완전히 같은 문제는 아니지만, 배열 돌리는 문제를 부딪치면서 푼 방법이다. int stx = queries[i][0]; int sty = queries[i][1]; int min = Integer.MAX_VALUE; int endx = queries[i][2]; int endy = queries[i][3]; int back = map[stx][endy]; for (int j = endy; j > sty; j--) { min = Mat..

문제 www.acmicpc.net/problem/16469 굉장히 괜찮았던 문제이다. 어려운 문제는 아니었는데, 접근하는 방법을 조금 다르게 생각해봐야하는 좋은 문제였다. - 첫 줄에 주어진 R, C로 만들어진 map - q1, q2, q3 3명이 동시에 한 지점에 도착할 때의 최단 시간을 찾으면 된다. 해설 및 코드 코드 자체는 어렵지 않게 풀어서, 큰 주석을 붙이지는 않았다. BFS로 문제를 풀었는데, Deepening을 사용해서 한 번에 이동이 가능한 size만큼 체크를 해줬다. 어디든 갈 수 있기 때문에, 방문 할 수 있으면 무조건 True로 만들어줬다. 이후, 전체 map을 탐색해서 세 check 배열이 모두 True인 구간이 있으면 개수를 센 후에 종료해줬다. 최단만 찾으면 되니까! packa..

문제 www.acmicpc.net/problem/11404 - N개의 지점과 M개의 간선이 주어진다. - 가중치를 가진 단방향 그래프 - 입/출력의 시작을 1로 봐야한다. 해설 및 코드 - 플로이드와샬 알고리즘으로 쉽게 풀 수 있다. - 개인적으로 골드4 정도는 아닌 듯... - 플로이드와샬 알고리즘을 할 때, 항상 배열의 초기화를 987654321로 한다. Intger. MaxValue를 쓰게 되면 + 계산 시 -가 나와서 최소 값을 제대로 찾지 못하기 때문이다. package 백준; import java.util.Arrays; import java.util.Scanner; public class 플로이드_11404 { public static void main(String[] args) { Scann..

문제 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..

문제 - 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..

문제 - 덱은 push front, push bakc, pop front, pop back이 존재한다. - 앞선 queue와 stack과 같다. 해설 및 코드 - 시간초과로 인해 sys에서 input을 가져왔다. - 리스트로 구현 # stack + queue가 섞인 것 = 덱 import sys # 시간초과 방지 N = int(sys.stdin.readline().rstrip()) arr = [] for _ in range(0, N): cmd = list(sys.stdin.readline().rstrip().split()) if cmd[0] == 'push_front': arr.insert(0, cmd[1]) elif cmd[0] == 'push_back': arr.append(cmd[1]) elif c..