알고리즘/백준 (89) 썸네일형 리스트형 [백준 10815] - 숫자 카드 - JAVA(HashMap사용) 안녕하세요 놀이방사장입니다. 이번 포스팅은 백준 10815 "숫자카드" 포스팅입니다. 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제설명) 조건을 보면 두 숫자에 중복된 숫자가 주어진 경우는 없다고 되어있습니다. 그리고 두번째 줄 기준으로 첫번째 줄에 있는 숫자가 있으면 1을 출력하고 없을 경우 0을 출력해주면 됩니다. 저는 HashMap을 사용했습니다. package me.joyeonggyu; import java.io.BufferedReader; import java.io.. [백준 15650] - N과 M (2) - JAVA [DFS] 안녕하세요 놀이방 사장입니다. 이번 포스팅은 백준 15650 "N과 M(2)" 문제입니다. 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 포스팅을 보시기 전에 16549번 N과M(1) 포스팅을 보고 오시면 좋을 거 같습니다. 그 코드에서 예외처리만 조금해주면 풀리는 문제이기 떄문입니다. 출력을 보면 아시겠지만 뒤에 출력되는 숫자들이 앞에 숫자보다 커져야합니다. N과M(1) 코드에서 저 예외처리만 해주면 됩니다. import java.io.BufferedReader; import java.io.Buffer.. [백준 9461] 파도반 수열 - JAVA [DP] 안녕하세요 놀이방 사장입니다. 이번 포스팅은 백준 9461번 "파도반 수열" 포스팅입니다. 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net dp에 해당하는 문제이고 점화식을 찾아주면 됩니다. 밑줄 친 부분을 보고 점화식을 찾을 수 있습니다. 점화식 dp [n] = dp[n-2] + dp[n-3]임을 알 수 있습니다. 4번쨰 숫자부터 그 식을 사용하면 값이 맞다는 걸 알 수 있습니다. 저걸 보고 풀어서 사실 공식은 잘 모르겠어요 하핫 -> 공식이 있다면... package me.joyeonggyu; import ja.. [백준 2579] - 계단오르기 - JAVA [DP] 안녕하세요 놀이방 사장입니다. 이번 포스팅은 백준 2579 "계단오르기" 입니다. 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net DP문제입니다. 점화식을 구해야하는데 점화식은 이 조건을 보고 만들어야 합니다. 포스팅을 참조하다가 점화식을 제대로 설명해주는 그림이 있어 가지고 와봤습니다. (밑에 블로그에서 가지고 왔습니다.) [백준] 2579번 : 계단 오르기 - JAVA [자바] www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도.. [백준 11726] 2*n 타일링 - JAVA [DP] 안녕하세요 놀이방사장입니다. 이번 포스팅은 백준 11726 "2*n 타일링" 입니다. 이번 문제도 DP문제입니다. 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 일단 DP이기 떄문에 값을 저장해줄 배열을 선언합니다. n의 크기가 최대 1000이기 떄문에 static int[] dp = new int[1001]; 위와 같이 배열을 선언해줍니다. 이제 점화식을 찾아야합니다 혹시 한 번 그려보면 n = 1 -> 1개 n = 2 -> 2개 n = 3 -> 3개 n = 4 -> 5개 이렇게 정답이 나옵니다. 여기서 찾을 수 있는 점화식은 .. [백준 1003] 피보나치 함수 - JAVA - [DP] 안녕하세요 놀이방 사장입니다. 이번 포스팅은 백준 1003 "피보나치 함수"입니다. 피보나치의 수는 이미 많은 분들이 알고 계세요 이번 문제는 시간조건이 빡세기 때문에 기본적으로 알고있는 방식으로 풀면 시간초과가 뜹니다. 저는 그래서 시간 초과가 떴죠 못 풀어서 다른 분의 풀이를 보았습니다... 풀이가 2가지가 있더라구요 1. for문을 이용한 풀이 점화식을 찾으면 표와 같습니다. fibonacci(N)[0] = fibonacci(N-1)[1] fibonacci(N)[1] = fibonacci(N-1)[0] + fibonacci(N-1)[1] 입니다. 그 방식을 그대로 코드로 짜주면 됩니다. /* * 1003 피보나치 함수 * for문 이용 * */ import java.io.BufferedReader;.. [백준 2606] 바이러스 - JAVA - [DFS] 안녕하세요 놀이방 사장입니다. 이번 포스팅은 백준 2606 "바이러스" 문제 풀이 포스팅입니다. 기본적인 DFS 문제 같습니다. 근데 양방향으로 해주어야 합니다. 처음에 단방향으로 풀었다고 계속 틀렸다고 해서 혹시나 양방향으로 그래프를 그리니깐 바로 정답처리되더라구요.. 이번 문제는 1번 컴퓨터를 기준으로 바이러스가 전염되는 컴퓨터의 갯수를 구하는 문제입니다. dfs나 bfs 둘 중에 하나로 풀면 될 거 같네요 저는 dfs로 풀었습니다. 그래프는 ArrayList를 이용해서 만들어주었습니다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamRead.. [백준 1463] 1로만들기 - JAVA - [DP] 안녕하세요 놀이방사장입니다. 이번 포스팅은 백준 1463번 1로 만들기 문제입니다. DP문제입니다. 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 이번 문제는 무작정 큰 수부터 나누면 안되는 문제입니다. DP문제이기 때문에 값을 저장할 배열을 생성합니다. 그리고 나눌 수 있는 수는 3,2,1이 있는데 여기서 3,2,1 최소공배수 6도 같이 추가해서 풀어줘야합니다. -> 재귀함수를 사용해서 가장 연산횟수가 가장값을 DP[N]배열에 저장해주면서 최솟값을 찾으면 됩니다. -> 여기서 계산을 할 때 테이블에 값이 없을 떄 연산을 해줘야함 값이 있을 경우 RETURN으로 값을 불러와주면 됨 /* * 백준 1463 DP * 이모이제.. [백준 2217] 로프 - JAVA 안녕하세요 놀이방사장입니다. 이번 포스팅은 백준 2217 "로프" 문제 풀이입니다. 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 문제설명 K의 개의 로프가 주어줍니다. 각 로프의 사양은 주어집니다. 로프를 이용해 들 수 있는 최대 무게를 구하는 문제입니다. 모두 고르게 중량이 걸린다고 적혀있습니다. 이 뜻은 위에 예제로 예시를 들면 10,15 두개를 같이 사용하면 저기서 제일 낮은 수의 10 * (로프의개수) 가 최대중량입니다. 15를 혼자 쓸 경우 15가 최대 중량이라는 뜻입니다. 그래서 무조건.. [백준 1620] 나는야 포켓몬 마스터 이다솜 - JAVA [HashMap 사용] 안녕하세요 놀이방 사장입니다. 이번 포스팅은 백준 "나는야 포켓몬 마스터 이다솜" 풀이입니다. 상당히 문제가 깁니다. 사실 앞에 대화들은 필요가 없어요.. 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 문제설명 입력이 되게 길죠? 첫번째 줄에 26개의 포켓몬이 포켓몬 도감에 들어갑니다. 5는 5번개를 출력하면 된다는 뜻입니다 무엇을 출력해야하는가? 먼저 포켓몬이름이 나오면 해당하는 포켓몬의 순서를 출력합니다 포켓몬 순서는 저기 차례대로 1~26번입니다. 숫자가 나온다? 해당하는 .. 이전 1 2 3 4 ··· 9 다음
