presentLee

https://www.acmicpc.net/problem/15681그래프가 주어지고. 특정 노드를 루트로 삼아서 트리처럼 관리해야한다.시간제한이 1초인데 10만개의 정점과 쿼리가 주어질 수 있기에 최악의 상황(트리가 1자로 쭉 이어짐)에서 매번 트리를 탐색하며 갯수를 세면 시간초과가 될 수 밖에 없다. 처음구현했던 단순한 방법1과 좀더 가다듬은 방법2 를 기술한다. 방법1.인접리스트를 저장한 그래프를 만들고, 입력된 루트를 기반으로 그래프를 트리로 재구성한 뒤루트에서부터 트리를 재귀호출로 탐색하며 서브트리의 크기를 갱신한다.import java.lang.reflect.Array;import java.util.*;import java.io.*;import java.lang.*;public class Mai..

baekjoon 2024. 12. 1. 23:27

https://www.acmicpc.net/problem/2206예제 입력의 경우는 벽을 무조건 부숴야 목적지에 도착할 수 있는 형태로 나와있다. 문제 조건은 벽을 한번까지 부술 수 있다는 것이고 무조건 벽을 부숴야 하는 상황은 아니기에벽을 부수고가는 경로와 벽을 부수지 않고 가는 경로를 모두 확인해서 비교해볼 필요가 있다. 처음에는 일반적인 bfs의 큐에 들어가는 각 항목에 해당지점까지 가면서 벽을 깼는지 안깼는지를 위한 필드를 추가해서 관리해주면서 최대 1번까지 벽을 깰 수 있도록 구현했는데 이렇게 처리하게 된다면 벽을 깨지 않고 a 지점을 거쳤을 때 결론적으론 가장 짧은 루트더라도벽을 깨지 않았을 때 보다 벽을 깼을 때 a지점에 빠르게 도착한다면, a지점이 visited 처리 되어 벽을 깨지 않고 ..

baekjoon 2024. 11. 29. 19:47

https://www.acmicpc.net/problem/2580 9*9 판에 숫자들을 입력받고 빈칸(0이 입력된 칸)에 스도쿠 규칙에 맞게 채워야 하는 문제.일단 빈칸들을 돌면서 가능한 값을 넣어보고 그렇게 해나가다가 어떻게해도 안되는 칸이 생기면앞에 한 것으로 돌아와서 다른 값을 넣어보는 방식으로 구현하기로 했다.백트래킹 방식. 아래는 구현한 코드.처음 제출시에는 solve 끝쪽에 return;을 생략했다가 틀렸다.백트래킹 방식을 채택했기에, 1~9 다 넣어보는 모든 수를 다 해봐도 뭔가 해결이 되지 않으면 앞으로 돌아가보아야 하는데return을 생략해서 그냥 아무것도 하지 않고 다음으로 넘어가는 흐름이 되어버렸었다.import java.util.*;import java.io.*;class Main{..

baekjoon 2024. 11. 10. 20:53

https://www.acmicpc.net/problem/11660표는 2^10까지 커지고 결과를 10만번까지 구해야 할 수도 있다.합계를 구하기 위해 제시된 공간을 매번 2중 for문으로 훑어 합을 구하게 되면최악의 상황에는 1024 * 100000 번 연산을 해야한다. 1억번이 넘는 연산이기에 1초 시간제한을 맞추기 어렵다. 효율적으로 계산하기위해 메모이제이션을 도입한다.처음에는 위와 같은 표가 있으면 더한 값을 계속 누적해나가며 이전 행의 누적값에 이어서 누적하여위 예시와 같은 상황에서1 3 6 1012 15 19 24....과 같은 형식으로 구현하려 했다. 하지만 이런식으로 구현한다면 2행2열에서부터 3행3열까지 합한다고 할 때3행 3열의 누적값에서 시작지점의 한칸 전 누적합을 빼고 시작행부터 끝..

baekjoon 2024. 11. 3. 08:58

https://www.acmicpc.net/problem/1629모듈로 분배법칙과 거듭제곱 분할정복을 함께 사용해야 하는 문제.10을 11번 곱하면 곱하기를 11번 해야 하지만. 분할정복을 통해 해결하면 log2(11)번으로 해결할 수 있다. 재귀 풀이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 long a,b,c; static long result=0; static l..

baekjoon 2024. 11. 2. 21:04

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

백트래킹을 통해 스타트 팀의 인원을 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