본문 바로가기

Algorithm

 (140)
백준 - 탑 with JAVA 해당 문제는 간단하지만 사소한 모든 요소가 메모리 초과, 시간 초과에 영향을 끼칠 수 있어서 기록해두려고 한다. 1. 기본적으로 입력은 BufferedReader로 받고 빈칸을 두고 입력을 받는다면, StringTokenizer를 사용하자 2. Stack을 사용한다면 stack.isEmpty()를 통해 비어있는지 여부를 체크하자. 만약 size()>0을 한다면 비효율적이다. 3. Stack을 사용한다면 pop(), push()를 통해 넣었다 빼기를 반복하지말고 peek()를 무조건 쓰자 4. printf보단 print가 메모리 초과가 발생하지 않는다. 로직 - 새로운 입력을 받을 때, Stack의 후입선출 구조를 통해 현재 타워보다 높이가 큰 수가 나올때까지 확인한다. - 확인 후 새로운 타워를 Stac..
백준 - 비슷한 단어 with JAVA 문자열 A와 B가 있다. 이 때, 문자 하나를 수정, 삭제, 변경해서 같은 문자열을 만든다. 예를 들어, ABC, ABCD 가 있다고 가정하자. [A, B, C, D]에서 [A, B, C]를 빼주면 [D] 만 남는다. 즉 1개만 바꿔주면 된다. 하지만, [A, B, C]에서 [A, B, C, D]를 빼주면 [] 가 되어 변경을 안해줘도 된다고 판단한다. 따라서 이를 주의해서 로직을 작성해야 한다. import java.util.*; // 비슷한 단어 public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); String value = sc.next();..
LCS 알고리즘 LCS 알고리즘 - 최장 공통 부분 수열 또는 최장 공통 문자열을 의미한다. - 최장 공통 부분 수열 : (ABCDEF, GBCDFE) -> BCDF, BCDE - 최장 공통 문자열 : (ABCDEF, GBCDFE) -> BCD 1. 최장 공통 문자열 특징 - 연속해서 같아야 한다. 점화식 - 만약 문자가 같다면 현재 각각의 문자열의 인덱스-1 위치의 값(그 전에 일치했는지 여부)에 + 1 을 해주면 된다. 시간복잡도 - O(NM) 예시 - 문자열1 : ABCDEF 문자열2 : GBCDFE - 두번째 인덱스에서 B가 같은데, 문자열1, 문자열2의 해당 인덱스에서 한칸씩 앞에서도 같은지 확인하고 더해주는 원리이다. A B C D E F 0 0 0 0 0 0 0 G 0 0 0 0 0 0 0 B 0 0 1 0..
백준 - 내리막길 DFS + DP 기본적으로 맵의 가로, 세로 최대는 500이다. 만약, (0, 0)에서 (499, 499)까지 간다고 가정하자 해당 경우의 수는 굉장히 커진다. 예를 들어, (0, 0)에서 (200, 200)으로 가는 경로가 10000이고 (200, 200)에서 (499, 499)까지 간다고 가정했을 때, 경로가 10000이라면 약, 10억가지의 경우의 수가 나온다. 밑의 두가지 코드의 차이점은 아래와 같다. 1번 코드 : (200, 200) 방문시 DP를 통해 (499, 499)까지 도달 가능하다고 판단하고 돌아간다. 2번 코드 : 항상 끝까지 방문한다. 위의 차이점으로 DP를 통해 시간복잡도를 낮출 수 있다. 추가사항 - 노드1에서 노드2까지 가는 경우의 수를 구하라 - 백준 점프 문제와 유사하다. ..
이코테 - 청소년 상어 with JAVA 이 문제는 로직은 간단하다. 데이터의 수가 적고 범위가 한정적이라 완전탐색으로 가능하다. 하지만 조건이 많아 실수가 발생해서 기록을 해두려고 한다. 세가지를 주의하자. 문제의 조건을 분리해두자. 설계를 하고 코딩을 하자. int[][] 는 복사시 반복문을 통해 항상 따로 해주자. 코드 import java.util.*; // 청소년 상어 public class Q2 { public static int[][] size_map = new int[4][4]; public static int[][] dir_map= new int[4][4]; public static List fish_size = new ArrayList(); // 상어 정보 public static int[] pos = {0, 0}; publi..
이코테 - 최종 순위 with JAVA 문제 작년 순위가 주어지고 높고 낮음이 뒤바뀐 사람들이 주어진다. 이때, 순위를 정확히 알 수 없다면, ?, 데이터에 문제가 있다면 Impossible, 그렇지 않다면 순위를 출력하라 로직 순위를 정확히 알 수 있는가에 대한 질문으로 위상정렬이 기본적으로 떠오른다. Base가 되는 구성으로 순위가 낮을 수록 진입 차수가 높아지며 사람들 간 관계를 표현하는 방법으로 graph를 통해 graph[a][b]가 true 이면 a가 b보다 순위가 높음을 표현할 수 있다. 위의 방법으로 위상정렬을 구현하면 진입차수가 0인 사람을 꺼내면 그 사람이 우선적으로 1등이 되고 그 사람과 연결된 사람들 즉, 그 사람보다 순위가 뒤에 있던 사람들의 진입차수를 1씩 뺐을 때, 0이 되면 더이상 그 사람 위에는 사람이 없음 즉,..
이코테 - 행성 터널 with JAVA 문제 최대 100000개의 행성이 있고 각 행성의 3차원 좌표가 주어진다. 이때, 행성 간 연결 비용은 행성 간 x값의 차이에 대한절대값, y값의 차이에 대한절대값, z값의 차이에 대한절대값 중 가장 작은값으로 측정된다. 최소한의 연결 비용을 통해 모든 행성을 연결하라. 로직 기본적으로는 크루스칼 알고리즘을 사용해야함이 읽힌다. '최소한의 비용을 통해 모든 노드를 연결하는 문제' 이기 때문이다. 하지만, 문제는 행성간 도로 설치 비용을 구하는 것이다. 만약 100000개의 행성들간 설치 비용을 모두 구한다면 문제가 발생한다. (n)(n-1)/2를 해보면 수가 너무 커짐을 알 수 있다. 따라서 행성간 도로 설치 비용을 구하는 방식을 설정해야 한다. 문제에서 나온 도로 설치 비용을 자세히 보면 간단한 방법을..
이코테 - 탑승구 with JAVA 해당 문제가 다른 문제들과 다른 점은 union연산에서 부모를 던진다는 점이다. 왜 부모를 던지는 것일까? 해당 문제의 로직을 살펴보면 만약 1~4 탑승구 중 하나에 착륙이 가능한 비행기가 들어온다면 탑승구 4와 탑승구 3를 union 한다. 이렇게 반복을 하다 부모의 값이 0이라면 착륙이 불가능하게 처리한다. 0을 만들기 위해서는 부모를 던져야 한다. 예를 들어, 2, 2 비행기가 들어왔다고 가정하자 초기 부모는 다음과 같다 [0, 1, 2, 3] 2 비행기 착륙 : 0, 1, 1, 3 2 비행기 착륙 : 0, 0, 1, 3 과 같이 된다. (부모를 던졌다는 가정하에) 따라서, 이 후, 추가적으로 2이하의 수가 들어오면 0을 반환하고 종료된다. 코드 package JAVA.TCT.GraphTheory;..

티스토리툴바