본문 바로가기

알고리즘

 (70)
[삼성 sw 기출] - 마법사 상어와 파이어볼 www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 문제를 풀면서 많이 헤매었는데, 주의해야 할 것을 위주로 작성해봐야겠다. 문제 풀이 방식 문제 풀이 방식은 사실 특별할 것은 없는데, 아래의 문제 설명처럼 파이어볼을 이동하고 나누는 과정을 그대로 구현하면 된다. 주의할 점 이 문제를 쉽게 접근하기 위해서는 ArrayList를 2차원 배열로 선언하는 것이 중요하다는 것을 인지했으면 더 빨리 풀 수 있었을 것 같다. 2차원의..
[boj 3273] 두 수의 합 - 투 포인터 문제 풀이 방식 정렬 후 투 포인터 활용, 다른 사람들의 풀이를 보니 right를 n-1 부터 시작하던데 참고해봐야겠다... 주의할 점 코드 상에 아래와 같은 조건을 넣어주지 않으면 탐색을 전체적으로 하지 않아 예외 케이스가 발생했다. if(right == n && left < n-1){ left++; right = left + 1; } 소스코드
[boj 1300] K번째 수 - 이분 탐색 문제 풀이 방식 이분 탐색 주의할 점 2차원 배열을 1차원 배열로 만드는 것이 가장 쉬운 방법이지만 이렇게 할 경우 배열의 크기가 너무 크므로 메모리 초과가 발생한다. 그러므로 특정 방식을 통해 이분 탐색으로 풀이했다. 만약 n = 3일 때, 2차원 배열은 아래와 같이 만들어진다. 1 2 3 - - - - - > Math.min( 4 / 1 , 3) -> 3 2 4 6 - - - - - > Math.min( 4 / 2 , 3) -> 2 3 6 9 - - - - - > Math.min( 4 / 3 , 3) -> 1 여기서 만약 7번째 수를 찾는다면 7번째 수보다 낮은 6개의 숫자를 찾으면 되는데, 이때 이분 탐색의 mid를 특정 숫자로 하여 아래와 같은 방법을 통해 찾아낼 수 있다. 위의 이차원 배열은 하..
이분 탐색 코드로 구현하기 - 자바 이분 탐색을 통해 특정 숫자를 찾을 때는 일반적인 이분 탐색을 구현하여 풀이하면 된다. 그러나 만약 특정 수의 개수를 카운팅 하고 싶은 상황에서는 어떻게 해야 할까? 아래와 같이 일반적으로 구현하게 된다면 찾고자 하는 숫자의 index를 찾을 수는 있겠지만 몇 개가 존재하는지 세는 것은 추가적인 연산이 필요할 것이다. 일반적인 이분 탐색 구현 private static boolean find(int num, int[] arr) { int l = 0; int r = arr.length-1; while(l num){ r = mid-1; } else { l = mid+1; } } return false; } 그래서 아래와 같은 코드로 왼쪽과 오른쪽을 스캔하는 코드를 구현해보았다. 찾은 index를 기준으로 왼..
버블 정렬 코드로 구현 하기 - 자바 버블 정렬( - 整列, 영어: bubble sort, sinking sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 {\displaystyle O(n^{2})} 로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다. 양방향으로 번갈아 수행하면 칵테일 정렬이 된다. 위키백과에서는 버블 정렬을 위와 같이 설명하며, 좋은 예제와 수도 코드를 보여준다. www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중..
프로그래머스 - 카카오프렌즈 컬러링북 programmers.co.kr/learn/courses/30/lessons/1829 코딩테스트 연습 - 카카오프렌즈 컬러링북 6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5] programmers.co.kr 오랜만에 프로그래머스 문제를 풀어보았습니다. 이 문제 유형은 많이 풀어봐서 쉽게 접근 방법을 알 수 있었습니다. 문제 풀이 방식 BFS 소스코드
프로그래머스 - 소수찾기(완전탐색, 에라토네스의 체) programmers.co.kr/learn/courses/30/lessons/42839#qna 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 � programmers.co.kr 요즘 코딩테스트 시즌이라 알고리즘 관련된 포스팅만 올리는 것 같습니다. 이 문제는 소수찾기 문제인데 이걸 백트래킹으로 풀어야할지 아니면 다른 방식으로 풀어야할지 많이 고민하다가 방법을 찾은것 같아서 그 방식대로 풀어봤는데 자바로 문자열 다루는게 쉽지 않았고 특히 deep copy때문에 고생했습니다... 문제 한자리 숫자가 적힌 종이 조각이 흩어져있습니..
BOJ 2178 - 미로 탐색(BFS) www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 미로탐색 문제는 (1,1) ~ (N,M)까지의 최소 거리를 구하는 문제입니다. 이런 연결되어 있는 배열을 탐색해 나가야 하는 상황에서는 BFS를 사용하고 첫번 째 칸에 1을 대입하고 나머지 칸에 +1을 해나가면서 거리를 확장시켜 나가면서 풀어야 합니다. 코드 import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; ..

티스토리툴바