'Algorithm' 카테고리의 글 목록 (2 Page)

본문 바로가기

Algorithm

[Algorithm/Java][백준] 1806번 부분합 [BOJ] 1806번 부분합 https://www.acmicpc.net/problem/1806 문제 접근 투 포인터를 이용해서 문제를 풀었다. deque와 이분 탐색을 이용해서도 풀 수 있다고 하는데 분류가 투 포인터라서 투 포인터를 사용해서 풀었다. start와 end인 두 개의 인덱스를 사용하고 sum이 t(목표 값)보다 작거나 같으면 end를 +1해서 한개를 더 더하도록 하고, sum이 t(목표 값)보다 크면 start를 +1 해서 합에서 한개를 빼서 목표 값에 접근하도록 한다. 투 포인터를 사용하게 되면 O(N)으로 문제를 해결할 수 있게 되는 장점이 있다. Code import java.io.BufferedReader; import java.io.IOException; import java.io.. 더보기

[Algorithm/Java][백준] 1700번 멀티탭 스케줄링 [BOJ] 1700번 멀티탭 스케줄링 https://www.acmicpc.net/problem/1700 문제 접근 예전에 운영체제 시간에 배웠던 페이지 교체 알고리즘과 비슷해서 쉽게 풀 수 있었다. 멀티탭에 자리가 있거나, 이미 꽂혀있을 때는 고려할 것 없이 그냥 꽂거나 넘어가면 되지만 자리가 없을때 고려해야 될 경우의 수가 있다. 경우의 수를 정리해 보면 다음과 같다. 멀티탭에 자리가 있는 경우 이미 멀티탭에 꽂혀 있는 경우 멀티탭에 자리가 없는 경우 3.1. 사용하지 않을 전자기기가 꽂혀 있는 경우 3.2. 모든 전자기기가 다시 사용할 전자기기인 경우 사용하지 않을 전자기기가 꽂혀 있으면 그 전자기기를 제거하고 새로운 전자기기를 꽂으면 해결된다. 모든 전자기기가 다시 사용할 전자기기인 경우 우선순위를.. 더보기

[Algorithm/Java][백준] 1062번 가르침 [BOJ] 1062번 가르침 https://www.acmicpc.net/problem/1062 문제 접근 백트래킹을 이용해서 모든 경우의 수를 탐색해보는 문제였다. 시간 복잡도를 줄이기 위해서 모든 단어가 포함하는 anta, tica 에 포함된 5개의 단어를 필수 단어로 포함시키고, 공백으로 바꿔주어서 탐색해야 하는 단어의 길이를 줄였고, 배울 수 있는 단어가 5개 보다 적을때 0, 26개 일 때 모든 단어를 배울 수 있으므로 n을 출력했다. 백트래킹을 할 때도 a~z까지 순차적으로 학습하기 때문에 시작 인덱스를 매개변수로 추가해서 이미 지나간 곳은 탐색하지 않도록 했다. Code import java.io.BufferedReader; import java.io.IOException; import jav.. 더보기

[Algorithm/Java][백준] 2504번 괄호의 값 [BOJ] 2504번 괄호의 값 https://www.acmicpc.net/problem/2504 문제 접근 Stack을 이용해서 열린 괄호를 저장하고, 괄호가 닫힐 때 X값을 다시 스택에 저장한다. 괄호 속에 숫자가 있으면 그 숫자들을 다 더해서 해당 괄호 값을 곱해주었다. 그리고 스택을 Character 자료형으로 하면 괄호와 숫자를 구분하지 못하기 때문에, String으로 해서 이 경우를 해결했다. 코드가 너무 복잡하고 올바른 괄호가 아닌것을 검사하기가 까다로웠다... Code import java.util.Scanner; import java.util.Stack; public class BOJ2504 { public static void main(String[] args) { Scanner sc .. 더보기

[Algorithm/Java][백준] 1987번 알파벳 [BOJ] 1987번 알파벳 https://www.acmicpc.net/problem/1987 문제 접근 가로 R, 세로 C로 된 보드에 대문자 알파벳이 적혀있고, 가장 왼쪽 위부터 알파벳 당 한번씩만 방문해서 가장 멀리 갈 수 있는 길이를 구하는 문제이다. 처음에는 아무생각 없이 bfs로 했다가 생각해보니까 dfs가 더 맞는 것 같아서 방향을 틀었다. 처음에는 보드에 방문 여부를 저장하는 isVisited와 알파벳 방문 여부를 저장하는 alphabetVisited를 사용하려 했는데, 생각해보니까 한번 방문한 알파벳은 방문하지 못하니까 보드에 방문여부를 저장할 필요가 없고, 경로를 String으로 계속 추가해가면서 하면 알파벳 방문 여부도 따로 저장하지 않아도 될 것 같아서 dfs에 가려는 x,y와 지금.. 더보기

[Algorithm/Java][백준] 2467번 용액 [BOJ] 2467번 용액 https://www.acmicpc.net/problem/2467 문제 접근 용액의 값들이 정렬이 되어있어서 left와 right를 이용해서 이분 탐색 방식으로 접근했다. 절대값을 이용해서 절대값이 낮은 경우를 저장해놓고, sum이 0일 때 break하고, sum이 0보다 작을 때는 left 인덱스를 +1 해주고, sum이 0보다 크면 right 인덱스를 -1해서 0에 가까운 값을 찾았다. Code import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ2467 { public s.. 더보기

[Algorithm/Java][백준] 12852번 1로 만들기 2 [BOJ] 12852번 1로 만들기 2 https://www.acmicpc.net/problem/12852 접근 방법 처음에는 dfs 방법으로 재귀 함수를 이용해서 접근을 했는데 시간 초과가 나서 dp 방식으로 접근 방법을 바꾸었다. dp[i]를 우선 dp[i-1] +1로 하고, 2로 나누어질 때와, 3으로 나누어질 때 dp[i/2] + 1과 dp[i/3] + 1을 비교해서 가장 작은 값을 dp[i]로 결정하였다. i는 2부터 n까지 반복해서 dp[n]일 때 최솟값을 구하였고 만드는 절차를 출력하기 위해서 위에 했던 방식을 거꾸로 해서 출력해주었다. Code import java.util.Scanner; public class BOJ12852 { public static void main(String[].. 더보기

[Algorithm/Java][프로그래머스] 단체사진 찍기 [프로그래머스] 단체사진 찍기 https://programmers.co.kr/learn/courses/30/lessons/1835 접근 방법 처음에 어떻게 접근하는지 모르겠어서 카카오 기술 블로그에 들어가서 해설을 봤는데 모든 경우를 다 세워보고 그 중에 조건을 만족하는지를 검사하는 방법이였다. dfs를 이용해서 모든 경우의 줄을 세워보고 check 함수를 이용해서 조건을 만족하는지 검사해서 경우의 수를 셌다. Code import java.util.HashMap; class Solution { public int answer = 0; public boolean[] visited = new boolean[8]; String[] friends = {"A", "C", "F", "J", "M", "N", "R.. 더보기

이전 1 2 3 4 5 ··· 9 다음

티스토리툴바