알고리즘

[BJ] 백준 11463 1로 만들기(JAVA)

문제 https://www.acmicpc.net/problem/1463 풀이 방법 문제는 간단하다. 1. x가 3으로 나누어떨어지면, 3으로 나누기 2. x가 2로 나우어 떨어지면, 2로 나누기 3. 1를 빼기 위 세개의 연산을 적절히 사용해서 1을 만드는데 연산을 사용하는 횟수의 최소값을 구하는 문제이다. 이 문제는 dp를 사용해서 풀면 된다. dp[N]에는 N이 1이 될때까지의 최소 연산 횟수를 가지고 있다. 우선 N이 2또는 3으로 나누어떨어지는지 확인한다. 만약 나누어 떨어진다면 2로 나눴을 때와 3으로 나눴을때 어떤 수가 더 최소연산 횟수를 가지는지 비교해서 더 작은 값을 dp에 넣는다. 그리고 항상 -1를 했을 경우의 연산의 최소값을 구해서 기존의 dp값과 비교 후, 더 작은 값을 dp에 넣어..

[SWEA] D4 1251 하나로 (JAVA)

문제 저작권 문제로 인해 링크만 첨부합니다. https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD&categoryId=AV15StKqAQkCFAYD&categoryType=CODE&problemTitle=1251&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 풀이 방법 프림 알고리즘에 대한 개념을 배우고 풀어본 문제다. 우선 입력값을 이요해서 인접 행렬을 만들어주고, 만들면서 각 섬 사이의 거리 값도 저장해줬다. 그 후 이제 프림 알고리즘을 수행했다. 아직 방문하지 않은 섬들중에서 가장 최소 거리..

[BJ] 백준 1753 최단경로(JAVA)

문제 https://www.acmicpc.net/problem/1753 풀이 방법 이 문제는 다익스트라를 이용하는 문제였던걸로 기억한다. 시작 위치에서부터 가장 최소인 경로를 출력하면 된다. 나는 우선 정점과 가중치를 저장하기 위한 클래스를 하나 선언해줬고, 우선 순위큐를 사용했다. 우선순위 큐에는 현재 시작점으로 부터 가장 가중치가 작은걸 우선으로 정렬하도록 선언했다. 우선순위 큐에서 하나씩 꺼내면서 꺼낸걸 방문 체크해주고, 꺼낸걸 기준으로 꺼낸 점접의 인접 점들을 보면서 꺼낸 것을 경유지로 간다면 더 작은 경로인 경우들만 경로를 업데이트 해주고, 우선순위 큐에다가 넣어주는 식으로 구현했다. 제출 코드 import java.io.*; import java.util.*; import sun.securit..

[SWEA] D4 3289 서로소 집합 (JAVA)

문제 저작권 문제로 인해 링크만 첨부합니다. https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBJKA6qr2oDFAWr&categoryId=AWBJKA6qr2oDFAWr&categoryType=CODE&problemTitle=3289&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 풀이 방법 문제를 간단하게 정리하면 각 원소가 초기에 자기자신만 가지고 있는 집합을 가지고 있고, 입력에 따라서 합집합과 같은 집합인지 확인하는 계산을 수행한다. 첫번째 원소가 0이면 합집합을 수행하고, 1이면 같은 집합인지 확인하는 연산을 ..

[BJ] 백준 10158 개미(JAVA)

문제 https://www.acmicpc.net/problem/10158 풀이 방법 문제를 간단하게 이해하면 t초후 개미의 위치를 구하면 되는 문제다. 이동은 45도로 이동을 하기 때문에 물론 이동 방향을 사용해서 하면 어려운 문제는 아니다. 하지만 이 문제에서 그런식으로 문제를 푼다면 시간초과가 난다. 시간을 단축시킬 수 있는 다른 방법을 찾아야한다. 나도 처음엔 위와 같은 방식으로 문제를 풀었는데 시간초과가 났고, 어떤 식으로 풀어야할 지 계속해서 고민을 한 것 같다. 몇시간을 고민하면서 시도를 했었는데 도저히 풀리지가 않아서 힌트를 조금 얻어서 풀었다. 내가 본 힌트는 x와 y좌표를 따로 구해보라 였다. 그래서 어떻게 따로 구하지 생각을 하다가 x좌표만 가지고 보니 좌표가 열 길이의 2배만큼 이동을..

[SWEA] D4 1238 Contact (JAVA)

문제 저작권 문제로 인해 링크만 첨부합니다. https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15B1cKAKwCFAYD&categoryId=AV15B1cKAKwCFAYD&categoryType=CODE&problemTitle=1238&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 풀이 방법 이 문제는 인접배열을 사용해서 풀었다. 우선 입력값을 활용해서 인접 배열을 만들고, 나장 나중에 연락을 받는 사람 중에서 가장 큰 번호를 가진 사람을 찾아야하기 때문에 BFS를 사용했다. 시작원소를 queue에 넣고 while문을 ..

[BJ] 백준 10163 색종이(JAVA)

문제 https://www.acmicpc.net/problem/10163 풀이 방법 이 문제는 서브태스크로 채점이되는 문제이다. 서브태스크 문제는 약간 예외를 생각하기 좋은 것 같다. 문제를 간단하게 설명하자면 여러장의 색종이를 순서대로 놓는데 겹쳐서 놓을 수가 있다. 출력값으로 색종이를 다 놓았을 때 각각의 색종이가 보이는 면적을 출력해야한다. (https://yoon990.tistory.com/33 이 문제가 생각이 났다.) 그래서 위에서 언급한 문제를 응용해서 이번에는 무조건 1로만 채우는 것이 아니라 색종이의 번호를 넣어주는 식으로 생각을 했다. 첫번째 색종이 면적은 1로, 2번째면 2로 .. 이런식으로 N번째 색종이까지 다 채운 후, 마지막에 1부터 N까지 map에 자신에 해당하는 번호가 몇 개..

[BJ] 백준 2628 종이자르기 (JAVA)

문제 https://www.acmicpc.net/problem/2628 풀이 방법 우선 행과 열의 크기에 맞게 1차원 배열을 선언해줬다. 그리고 그 배열에는 입력에 따라서 자른 점선 번호이면 1로 배열 값을 수정해줬다. 문제와 같은 예시로 설명을 하자면 num 1 2 3 4 5 6 7 8 9 cutM 0 0 0 1 0 0 0 0 0 num 1 2 3 4 5 6 7 cutN 0 1 1 0 0 0 0 이런식으로 값이 들어가게 된다. 그 후 이제 각각 배열을 돌면서 temp 길이를 1을 하나씩 추가하다가 1을 만나면(잘려진 선을 만났으므로) 최대 길이와 비교해서 필요시 최대길이를 업데이트해주고 temp는 다시 0으로 설정해준다. (새로운 길이 시작) 열과 행을 같은 방법으로 구현 후, 각각의 max값을 곱해주..

[SWEA] D4 7465 창용 마을 무리의 개수 (JAVA)

문제 저작권 문제로 인해 링크만 첨부합니다 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU&categoryId=AWngfZVa9XwDFAQU&categoryType=CODE&problemTitle=7465&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 방법 서로소 집합에 대해서 공부한 뒤 풀어본 문제였다. 사람 사이의 관계를 입력받아서 총 무리가..