본문 바로가기
728x90
반응형

코딩테스트190

[프로그래머스/java] 멀쩡한 사각형 - 유클리드 호제법 사용 https://programmers.co.kr/learn/courses/30/lessons/62048 코딩테스트 연습 - 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 programmers.co.kr 이 문제는 유클리드 호제법 공식을 써야한다. 유클리드 호제법 공식 1 int gcd(int a, int b) { int c; while(b) { c = a % b; a = b; b = c; } return a; } 유클리드 호제법 공식 2 public static int gcd(int p, int q) { if (q == 0) retu.. 2022. 2. 25.
[프로그래머스/java] 최소 직사각형 https://programmers.co.kr/learn/courses/30/lessons/86491 코딩테스트 연습 - 최소직사각형 [[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]] 120 [[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]] 133 programmers.co.kr 이번 문제는 Min, Max만 잘 써도 쉽게 풀리는 문제이다 문제 설명 중에 "가장 긴 가로 길이와 세로 길이가 각각 80, 70이기 때문에 80(가로) x 70(세로) 크기의 지갑을 만들면 모든 명함들을 수납할 수 있습니다. 하지만 2번 명함을 가로로 눕혀 수납한다면 80(가로) x 50(세로) 크기의 지갑으로 모든 명함들을 수납할 수 있습니다. 이때의 지갑 크기.. 2022. 2. 23.
[프로그래머스/java] 타겟 넘버 - BFS 이용 https://programmers.co.kr/learn/courses/30/lessons/43165?language=java 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 이번 포스팅은 타겟 넘버입니다. DFS나 BFS를 이용하여 푸는 문제입니다. 저는 BFS를 이용하여 풀었는데 처음에는 백트래킹(완전탐색)을 이용하여 테스트케이스를 풀었으나, 제출 시 시간초과가 4개의 케이스에서 발생했습니다. BFS를 이용해서 풀면 시간초과가 나지 않고 풀 수 있습니다.. 2022. 1. 6.
[백준/java] 15686번: 치킨 배달 - 삼성 SW 역량테스트 기출(조합문제) https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다. 쉬운 말로, 집 A가 있고, 치킨집 B, C ,D가 있다 가정하면, 집 A부터 B까지의 거리, A부터 C까지의 거리, A부터 D까지의 거리를 누적하면 도시의 치킨 거리의 합이 구해진다. 이 과정을 모든 집 마다의 치킨 거리를 구하여 가장 적은 값을 .. 2021. 11. 30.
[백준/java] 2573번: 빙산 - dfs https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제 풀이 과정 1. 먼저 연결되어있는 빙산이 조사 2. 다 순회 후 빙산 녹이기 3. 빙산이 2개이상 나뉜게 없으면 0 출력, 2개 이상이면 녹인 햇수 출력 4. 1번부터 3번까지 계속 반복 입력 값 : 5 7 0 0 0 0 0 0 0 0 2 4 5 3 0 0 0 3 0 2 5 2 0 0 7 6 2 4 0 0 0 0 0 0 0 0 0 종합적인 코드는 아래와 같다. package dfsAnd.. 2021. 11. 26.
[백준/java] 2644번: 촌수계산 - 인접행렬을 이용한 DFS https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 이번 문제는 인접행렬을 이용하여 촌수를 계산하는 문제이다. 입력이 다음과 같이 주어진다. 9 7 3 7 1 2 1 3 2 7 2 8 2 9 4 5 4 6 처음 9는 전체 사람의 수 n이고, 두번째 줄에 주어지는 수로 촌수를 구하면 된다. 즉, 7번과 3번의 촌수를 구하면 된다. 세번째 줄의 7은 부모와 자식의 관계를 나타낸다. 1번은 2번의 부모 1번은 3번의 부모 인접행렬로 .. 2021. 11. 15.
728x90
반응형

티스토리툴바