알고리즘182 [백준 7543] 합이 0인 네 정수 / 자바 / 투포인터 #문제 레벨: G2알고리즘: 투포인터풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/7453 #문제 풀이 ✔ 풀이법4개의 배열을 각각 조회하면 시간초과가 발생하므로 A와 B 원소의 합이 C와 D 원소의 합이 부호만 다르고 절대값이 같은 경우를 찾으면된다.여기서 의아한 사람들이 있을 거다. 엥 a+b = - (c+d) 조합만 고려하면 모든 경우의 수를 찾지 못하지 않나? a+c = -(b+d)라던지 a+d = -(c+b) 의 조합을 고려해야지 않나?아니다. 한 가지의 조합만 고려해도 모든 경우의 수를 알 수 있다. 예시를 들어보겠다.위와 같은 배열이 있을 때 a+b = - (c+d)의 경우의 수만 구해보겠다. a+b가 (1+4=5.. 2024. 9. 9. [백준 2623] 음악프로그램 / 자바 / 위상정렬 #문제 레벨: G3알고리즘: 위상정렬 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/2623 #문제 풀이 위상정렬이란 순서가 정혀져 있는 작업을 순서를 정해주는 작업을 뜻한다.코드는 큐로 구현된다. 방향성이 있는 선들을 하나 씩 끊어주는 느낌으로 구현하면된다. 그리고 선이 다 끊어진 노드들은 결과에 포함시킨다. 글보다는 코드로 보는 것이 이해가 더 쉬울 것이다. 아래를 참조바란다.#풀이 코드 import java.util.*;import java.io.*;public class Main { static ArrayList[] graph; static int[] inDegree; static int N, M.. 2024. 9. 6. [백준 2239] 스도쿠 / 자바 / dfs(백트래킹) #문제 레벨: G4 알고리즘: dfs(백트래킹)풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/2239#문제 풀이 해당 자리에 숫자를 놓으려면 해당 열, 해당 행, 해당 박스 안에 같은 숫자가 있으면 안된다. 이것들을 검사하는 코드를 구현하고 백트래킹을 통해서 숫자를 채워넣으면 된다.dfs 코드는 아래와 같이 방문한다. -------------------------> 1 번째 행-------------------------> 2 번째 행 -------------------------> 3 번째 행 -------------------------> 4 번째 행 -------------------.. 2024. 9. 1. [백준 2166] 다각형의 면적 / 자바 / 수학(신발끈 공식) #문제 레벨: G5알고리즘: 수학(신발끈 공식)풀이시간: 10분힌트 참조 유무: 유https://www.acmicpc.net/problem/2166#문제 풀이 신발끈 공식고등학생 때 배웠던 것 같은데 까먹었다. 아닌가 중학교 때 배웟나. 어찌 됐든 도형의 넒이 구하는 공식은 기억하는게 좋을 것 같아 따로 남겨놓는다.신발끈 공식은 간단하다. 빨간색으로 이어진 숫자끼리 곱하고 다른 빨간색선들이랑 더해준다. 파란색도 마찬가지로 파란색끼리 합쳐준다. 그리고 Math.abs(빨간색 총합 - 파란색 총합) /2 해주면 도형의 넓이가 나온다. #풀이 코드 import java.io.*;import java.util.*;public class Main { public sta.. 2024. 9. 1. [백준 7579] 앱 / 자바 / dp(기초) #문제 레벨: G4알고리즘: dp(기초)풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/7579 #문제 풀이 dp에 담기는 것은 i의 비용으로 비활성화하는 앱들의 비용 합계를 나타낸다.M으로 dp배열을 만들면 메모리 초과가 날 것을 직관적으로 알 수 있다. dp 배열을 cost로 잡는다. 이 dp는 이차원배열 풀이와 일차원 배열 풀이가 있다.이차원 배열 풀이dp[i][j] 에서 i는 1~i 앱까지 탐색했는지 나타내고 j는 cost를 나타낸다. 즉, dp 배열은 1 ~ i번까지 탐색하여 cost j를 이용하여 최대한 비울 수 있는 메모리를 나타낸다. 일차원 배열 풀이dp[i]에서 i는 i의 cost가 주어졌을 때 최대한 비울 수 있는 .. 2024. 8. 30. [백준 1197] 최소 스패닝 트리 / 자바 / 자료구조(크루스칼 알고리즘/유니온 파인드) #문제 레벨: G4알고리즘: 자료구조(최소 스패닝 트리)풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/1197#문제 풀이 MST란 n개의 정점을 최소한의 간선(n-1)으로 이은 트리(싸이클x)이다. MST는 크루스칼 알고리즘과, 프릴 알고리즘을 사용해 풀 수 있다. 크루스칼 알고리즘은 유니온 파인드 자료구조를 사용한다. 프림 알고리즘은 다익스트라 비슷하게 풀이한다. 크루스칼 vs 프림 크루스칼 알고리즘프림 알고리즘탐색 방법간선 위주정점 위주탐색 과정시작점 따로 지정없이 최소 비용의 간선을 차례대로 대입하면서 사이클이 이루어지기 전까지 탐색시작점을 지정한 후 가까운 정점을 선택하면서 모든 정점을 탐색사용간선의 개수가 적은 경우 크루스칼 알고.. 2024. 8. 30. [백준 1780] 종이의 개수 / 자바 / 분할정복(기본) #문제 레벨: S2알고리즘: 분할정복(기본)풀이시간: 20분힌트 참조 유무: 무https://www.acmicpc.net/problem/1780#문제 풀이 이 문제는 피보나치 문제(easy)와 마찬가지로 분할정복의 기초 문제이다. (개인적인 생각으로는 그렇다.)분할정복 문제를 풀게 된다면 반드시 이 문제는 풀어보고 갔으면 좋겠다.분할정복 말은 거창하지만 가장 작은 문제로 쪼갤 수 있을 때까지 쪼갠 후 작은 문제들을 풀이하는 것이다. 이 문제에서는 풀어주세요 ~ 라고 말하는 것처럼 문제를 쪼개는게 직접적으로 나와있다. 큰 정사각형을 모든 수가 같을 때까지 9등분으로 나누면 되는 것이다. 쉽지 않은가. 나머지는 코드 참고 바란다. #풀이 코드 import java.ut.. 2024. 8. 29. [백준 2261] 가장 가까운 두 점 / 자바 / 분할정복 or 라인스위핑 #문제 레벨: P2알고리즘: 분할정복, 라인스위핑풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/2261#문제 풀이 이 문제는 디게 어렵다. 이분의 블로그를 보고 풀이를 이해했다. 이 분의 글을 보기 전에 이것만 기억해라. 아이디어는 간단하다(라인 스위핑 풀이에 관한). 직사각형을 생각하자. 우린 그 직사각형을 오른쪽으로 밀며 직사각형 안에 있는 점들끼리 비교할 것이다. 그러나 더 좋은 효율을 내기 위해 그 직사각형을 가로 혹은 세로를 점점 줄이면서 탐색하는 것이다. https://st-lab.tistory.com/256 [백준] 2261번 : 가장 가까운 두 점 - JAVA [자바]https://www.acmicpc.net/pr.. 2024. 8. 29. [백준 13334] 철로 / 자바 / 라인스위핑 ** #문제 레벨: G2알고리즘: 라인 스위핑 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/13334#문제 풀이 라인 스위핑 을 직역하면 싹스리 하는 이라는 뜻이다. 한 마디로 한 쪽 방향으로 정렬된 직선을 스캔하며 정해진 기준에 따라 답을 업데이트 하는 것이다. 그리드 알고리즘의 종류라고 생각하면 된다.이 문제는 끝점을 기준으로 오름차순 정렬한다. 놓아야 하는 직선 L을 정렬된 끝점에 맞추어 계속해서 대보는 것이다. 기준에 부합하면 시작점을 큐에 넣고 L보다 튀어나온 큐에 있는 시작점들은 Poll 해준다. 간단하지 않은가? +라인스위핑 문제느 변수를 사용해서 답을 관리하는 것보다 우선순위 큐의 사이즈로 관리하는 것이 용이하다.!!!!.. 2024. 8. 28. 이전 1 2 3 4 5 6 ··· 21 다음
