본문 바로가기

알고리즘

 (70)
BOJ 1926 - 그림 www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로�� www.acmicpc.net BFS 문제 풀어봤습니다. 힘들어! import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class boj1926 { static int[][] arr; static boolean[][] visited; static int[] dx = {-1,1,0,0}; static int[] dy = {0,0,-1,1}; st..
BOJ 1912 - 연속합 ( 완전탐색, Prefix Sum, DP) www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 연속합 문제를 3가지 방식으로 풀어보겠습니다. 1. 완전탐색 말 그대로 전체 배열을 돌면서 모든 경우의 수를 탐색합니다. 시간복잡도는 O(n^3)으로 문제를 제출하면 시간초과가 발생합니다. import java.util.Scanner; public class boj1912 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int ..
BOJ 11726 - 2 x N 타일링 www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 풀이 import java.util.Scanner; public class boj11726 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] dp = new int[10001]; int mod = 10007; dp[1] = 1; dp[2] = 2; for(int i=3; i
BOJ 1149 - RGB거리 www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net dp 문제 하나를 더 풀어 봤습니다. 점화식을 세울 때 항상 1차원 배열로만 점화식을 작성했는데 2차원 배열로 작성해서 문제를 해결하는 방법이 있습니다. 이 문제는 dp의 배열을 1차원 배열로 하게 되면 R, G, B 세 가지의 색상을 나타내지 못하므로 2차원 배열을 생성해서 점화식을 작성하고 문제를 풀이합니다. dp[i][1] = R dp[i][2] = G dp[i][3] = B로 만든 ..
BOJ 2294 - 동전2 www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주�� www.acmicpc.net 동적 계획법 문제를 한번도 풀어보지 않아서 오늘은 DP 문제를 골라서 풀어봤습니다. 동적 계획법을 공부하면서 느낀 것은 사전에 공부를 하지 않는다면 실전에서 바로 적용하는 것은 무리가 있다고 판단했습니다. 그래서 미리 미리 사전에 관련 문제를 학습하고 풀이하는 과정이 필요한 것 같습니다. 동적 계획법을 공부하면서 제가 이해한 것은 이미 정해진 해답들 속에서 관련된 규칙을 도출해..
프로그래머스 - 튜플(2019 카카오 개발자 겨울 인턴십)` https://programmers.co.kr/learn/courses/30/lessons/64065 코딩테스트 연습 - 튜플 "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] programmers.co.kr 문제를 풀기 전 정확하게 문제 풀이를 이해하고 푸는 것이 중요하다는 것을 다시 한번 깨달았습니다. 그냥 튜플에 입력된 순서대로 받아서 배열에 입력한 후 리턴하면 되는 줄 알았는데 그게 아니라 배열의 크기가 작은 순부터 탐색해야 했습니다. 틀린 풀이 class Solution { public int[] solut..
프로그래머스 - N개의 최소공배수(유클리드 호제법 알아보기) https://programmers.co.kr/learn/courses/30/lessons/12953 코딩테스트 연습 - N개의 최소공배수 두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배�� programmers.co.kr 이 문제는 유클리드 호제법을 이용해 최대 공약수를 구할수 있다면 보다 쉽게 접근할 수 있는 문제입니다. 저 역시 알고리즘 문제를 풀면서 이전에도 유클리드 호제법을 접해보았는데 다시 문제에 활용하려고 하니 하나도 기억이 안나더라고요. 이 기회에 유클리드 호제법을 정리하려고 이 글을 포스팅합니다~ 추후에 문제에 활용할 ..
프로그래머스 - 다음 큰 숫자 https://programmers.co.kr/learn/courses/30/lessons/12911 코딩테스트 연습 - 다음 큰 숫자 자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다. 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다. 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니 programmers.co.kr 문제 읽고 그대로 구현하면 되는 문제입니다. 2진수로 변환하는 매서드 만드는데 조금 헷갈리더라고요. 스택사용해서 만들면 조금 수월하게 만들 수 있는 것 같습니다! 다른 사람들 풀이도 조금 참고해봐야겠습니다. 문제 풀이 코드 class Solution { public int solution(int n) { int result = o..

티스토리툴바