본문 바로가기
728x90
반응형

java230

[프로그래머스/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] 조합을 구하는 코드 공식 콤비네이션을 구하는 코드이다. int[] combi 배열을 만들고, for문으로 순회하면서 combi 배열을 채우고, 조합해야할 개수의 수만큼 도달했을 때 조합되어지는 수들의 경우를 출력한다. package _08_dfsBfs._009_getCombi; /** * 입력 4 2 출력 1 2 1 3 1 4 2 3 2 4 3 4 */ import java.util.Scanner; public class Main { static int[] combi; static int n, m; public static void dfs(int L, int s) { if(L == m) { for(int x : combi) System.out.print(x + " "); System.out.println(); } else { f.. 2021. 11. 30.
[백준/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.
[백준/java] 1697번 : 숨바꼭질 - BFS 이번 문제는 2차원배열 위주로 풀던 BFS 문제를 폭넓은 시각으로 바라볼 수 있게 해주는 문제 같다. https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 입력값을 5 17 로 입력하면 출력값이 4로 나와야 한다. 출발값인 5를 제외한 17까지의 나머지 숫자 카운트가 4번이어야 한다. 문제의 조건대로 3가지의 조건. 수빈의 위치 + 1, 수빈의 위치 -1, 수빈의 위치 * 2 연산을 수행해야 한다. public static.. 2021. 11. 14.
728x90
반응형

티스토리툴바