본문 바로가기

장원익 기술블로그

💻 Computer Science/- Data Structure, Algorithm147

[알고리즘-PS] 백준 1325번 효율적인 해킹 자바 문제풀이 (시간 초과 해결) 문제 해당 포스팅은 백준의 1325번 효율적인 해킹 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 문제 접근 이 문제는 간단한 dfs/bfs 로 해결할 수 있는 문제이다. 총 입력이 1만개가 최악의 경우 들어오고 각각의 노드의 dfs 결과를 탐색해야 하니 조금 간당간당하게 시간 복잡도에 걸릴 수 있다. 그래서 이 문제는 일반적인 dfs로 해결하면 시간 초과가 날 수 있는 문제이다. 해결법 이 문제는 재귀 dfs, 스택 dfs 등 여러 방법을 통해서 구현을 해보았지민 결과를 조금 더 빨리 낼 수 있는 bfs 로 해결하였다. 해킹할 수 있는 노드의 수를 표현하기 위해.. 2021. 7. 27.

[알고리즘-PS] 백준 1092번 배 자바 문제풀이 문제 해당 포스팅은 백준의 1092번 배 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 문제 접근 이 문제는 그리디 알고리즘을 이용해서 풀 수 있는 문제이다. 해결법 이 문제를 보고 캐치해야할 가장 중요한 단서는 바로 어떤 기준으로 정렬을 할 것인지이다. 이번 문제같은 경우는 박스의 무게와 크레인의 내림차.. 2021. 7. 21.

[알고리즘-PS] 백준 1263 시간 관리 자바 문제풀이 문제 해당 포스팅은 백준의 1263 시간 관리 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 문제 접근 이번 문제는 간단한 그리디와 정렬을 이용한다면 쉽게 해결할 수 있는 개념을 묻는 문제인 것 같다 해결법 이러한 입력이 들어오고 가장 늦게 일어날 수 있는 시간은 모든 과제가 마지막으로 끝나는 시간을 기준으로 하나씩 과제를 해결하면 된다 정답 코드 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new.. 2021. 7. 20.

[알고리즘-PS] 백준 1343번 폴리오미노 자바 문제풀이 문제 해당 포스팅은 백준의 1343번 폴리오미노 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 1343번: 폴리오미노 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. www.acmicpc.net 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 문제 접근 이 문제는 전형적인 그리디 알고리즘을 이용해서 해결할 수 있는 그리디 기초 문제이다. 해결법 입력이 들어올 때, AAAA 를 먼저 채우는 것이 사전순 앞으로 오는 정답이 되기 때문에 AAAA 가 먼저 채워지는지 검사하고, 그 다음으로 BB 를 검사하는 방식으로 문자열을 마지막까지 iteration 하면 된다. 정답 코드 .. 2021. 7. 14.

[알고리즘-PS] 백준 1105번 팔 자바 문제풀이 문제 해당 포스팅은 백준의 문제 이름 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 1105번: 팔 첫째 줄에 L과 R이 주어진다. L은 2,000,000,000보다 작거나 같은 자연수이고, R은 L보다 크거나 같고, 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 문제 접근 이번 문제는 그리디 알고리즘으로 풀어볼 수 있다. 숫자 a와 b가 입력으로 주어지게 된다면, a와 b 사이에 8이 최소로 들어가는 수가 8을 포함하는 수를 출력하는 것이다. 핵심은 다음과 같다. a와 b가 자리수가 다르다면 무조건 0 a와 b가 자리수가 같다.. 2021. 7. 13.

[알고리즘-PS] 백준 1080번 행렬 자바 문제풀이 문제 해당 포스팅은 백준의 1080번 행렬 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 문제 접근 이번 문제는 그리디 알고리즘을 적용하면 해결할 수 있는 문제이다. 문제에서는 시작 행렬과 타깃 행렬을 입력으로 주어진다. 3 by 3의 부분 행렬 을 비트 반전 시켰을 때, 최소 몇 번의 반전을 시켜야 타깃 행렬과 동일하게 되는지 최소 회수를 구하는 문제이다. 해결법 n by m 행렬이 있다면 배열 원소 하나씩 iteration 하면서 start 행렬과 target 행렬의 원소가 동일하다면 넘어가고 동일하지 않다면 flip 하면 된다. 정답 코드 public cla.. 2021. 7. 13.

이전 1 2 3 4 5 6 7 ··· 25 다음

티스토리툴바