presentLee

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/14891구현문제특정 톱니를 선택해서 시계방향이나 반시계방향으로 한칸 돌린다.톱니가 돌아갈때 인접 톱니도 돌지만 맞물리는 부분이 같은 극성이면 돌지않는다.위에서 1번톱니를 돌릴때 2번톱니는 돌지만2번톱니가 돌면서 3번톱니가 돌지는 않는다.(2번과 3번 맞물리는게 둘다 S로 같은 극성이다) 헷갈릴 수 있는 부분이 있는데 틀렸던 코드를 첨부한다,import java.util.*;import java.io.*;public class Main { static int[][] wheels = new int[4][10]; // 4개에 10칸 할거야. 필요칸은 8칸인데, 0은 반시계시 끝에, 9는 시계시 처음으로 붙이기 static int n; ..

카테고리 없음 2024. 11. 4. 19:51

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

신경쓸부분 몇개 있는 구현문제확산시 주의사항.확산은 모두 동시에 일어난다. 순차적으로 하면 다른곳에서 확산이 일어나기전에 영향을 주기 때문에확산을 위해 같은 크기의 배열에 복사해서 해당 배열에 업데이트를 하고 붙여넣는 식으로 해주어야 함. 공청기구현일단 화살표 방향 따라서 구현해보려고 하니 한칸씩 밀고 방향꺾고 생각하다 너무 복잡하게 해버렸다.. 공청기에서 바람이 나오는 첫 다음칸으로 이동하고 현재칸이 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