presentLee

https://www.acmicpc.net/problem/30805수열 둘의 최대길이가 100자리다. 시간제한이 1초인 문제이기에 수열을 하나하나 확인하고 있으면 시간초과가 난다.100자리 수열의 부분수열을 모두 구하려면 2^100회나 비교해보아야 하기 때문에 불가능.백트래킹으로 했었다가 시간 초과로 틀렸다. 아래는 틀렸던 코드.import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.util.StringTokenizer;import java.util.*;public class Main { static int ..

baekjoon 2024. 11. 2. 18:19

https://www.acmicpc.net/problem/1890 현재 칸에 쓰여진 수만큼 우측이나 하단으로 점프해가며 종착점까지 가는 경우의 수를 센다.우측이나 하단으로 가므로 원래 위치로 돌아올 일은 없고, 총 경우의 수를 세기 때문에 visited 관리는 필요 X(좌우상하 다 움직일 수 있었다면 어떻게 해야 했을까?)1. bfs로 발 닿은 곳마다 방문 횟수를 늘려서 종착점 밟은 수를 모두 세 보자.2. bfs하면서 나아간 곳의 방문횟수를 이번칸 방문횟수로 업데이트해보자. -> 이럼 종착점에 도달 못한 경우의 수도 합해서 세버리는 경우가 될 듯 한? 메모리초과로 틀린코드import java.io.BufferedReader;import java.io.InputStreamReader;import java..

baekjoon 2024. 10. 31. 13:17

신경쓸부분 몇개 있는 구현문제확산시 주의사항.확산은 모두 동시에 일어난다. 순차적으로 하면 다른곳에서 확산이 일어나기전에 영향을 주기 때문에확산을 위해 같은 크기의 배열에 복사해서 해당 배열에 업데이트를 하고 붙여넣는 식으로 해주어야 함. 공청기구현일단 화살표 방향 따라서 구현해보려고 하니 한칸씩 밀고 방향꺾고 생각하다 너무 복잡하게 해버렸다.. 공청기에서 바람이 나오는 첫 다음칸으로 이동하고 현재칸이 0인지, 값이있는지 구분하고전 칸에서 밀려왔는지 오지않았는지 여부에 따라 구분해 각 분기점에따라이번칸을 0으로 업데이트할지, 이전칸에서 저장한 값을 넣을지 결정하며 다음칸이 공청기칸인지 매번 확인한다. 다른분들의 코드를 살펴보니 반대방향으로 생각해서 화살표 역방향으로 공청기 빨아들이는 바로 앞 칸부터 시작..

카테고리 없음 2024. 10. 28. 08:08

1. 다익스트라.음수인 비용이 있으면 사용 불가능.우선순위 큐를 사용해 출발점을 우선순위큐에 넣고 그리디하게 가장 거리가 짧은 타 정점으로 이동해서해당 정점까지의 거리가 갱신된다면 우선순위큐에 추가.방문한 정점은 다시 방문하지 않는다. 2. 벨만포드V-1번 사이클을 돌면서 모든 정점에서 연결된 간선으로 근처 정점의 거리를 업데이트 한다.V번째 사이클을 돌아 업데이트 되는 거리가 있다면 음수 사이클이 검출되는 것을 확인할 수 있다. 3. 플로이드모든 정점간의 거리관계를 파악하는데에 가장 빠르다. 음수사이클은 검출불가.간선을 입력받을 때, 이차원배열의 i에서 j까지의 거리를 모두 기록해둔다.그후 3중 for문 돌면서. n번째 정점을 거치면  i에서 j까지의 거리가 더 짧아지는가를 확인하자.i->j랑 i->n..

알고리즘 2024. 10. 27. 00:35

백트래킹을 통해 스타트 팀의 인원을 N/2만큼 조합해서 골라주고, 나머지인원은 링크팀으로 할당한다.전체 인원을 다 기록한 것을 인자를 통해 확인되면 차이가 몇 나는지 확인해준다. import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;import java.util.*;public class Main { /* 짝수인원수 받아서 반갈라서 하는거니까,절반 뽑아서 스타트 팀에 박고 나머지 링크에 넣고 쭉 돌면서 최소 찾아내자. 더하다가 전 최소값을 넘기면 가지치기? */ static int n; static int[][] arr; static int resu..

baekjoon 2024. 10. 26. 10:17

ArrayList에 직접 만든 클래스를 정렬하거나우선순위큐에 집어넣을 때, 클래스 내에 여러개의 필드가 있기에 정렬 기준을 설정해야 한다.클래스 자체에 설정하는 방식과.sort() 메서드나 자료구조 생성 시에 설정해주는 방식이 있다. 1. 클래스에 설정.static class edge implements Comparable{ public int weight; public int to; public edge(int weight,int to){ this.weight=weight;this.to=to; } @Override public int compareTo(edge e){ int com = In..

java 2024. 10. 20. 01:01

SELECT ID, LENGTH FROMFISH_INFOORDER BY LENGTH DESC,IDLIMIT 10;간단하게 가능.하지만 길이에 null이 있을 때 상황에 따라 다르게 처리해야 할 경우가 있음.SQL 종류에 따라 null이 오름차순일때 맨위일지 내림차순일때 맨 위일때가 다르다.MYSQL이 아닌 다른 SQL일 경우 내림차순 정렬일 때 null이 먼저올 수 있기에SELECT ID, LENGTH FROMFISH_INFOORDER BY length is null,LENGTH ASC,ID이렇게 처리해준다면 첫번째 정렬 기준이 length is null 이 되므로null인 것은 1, 아닌것은 0이 되어 기본 값인 오름차순 정렬됐을 때 null이 가장 아래로 가게 된다.

카테고리 없음 2024. 10. 4. 05:22