복습노트 복습노트

문제 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 노드의 갯수 n, 간선의 정보 m개, 시작 노드 v를 입력받아 DFS와 BFS 한 결과를 출려하면 되는 문제이다. 그동안 C++로 알고리즘을 풀다가 처음으로 JAVA로 구현하다 보니 헷갈리는 부분이 많아 정리한다. C++ 에서는 2차원 벡터로 구현하면 된다. 1) 인접 행렬 구현 arr[a][b] = 1 (a에서 b로가는 간선이 있다.) arr[a][b] = 0 (a에서 b로 가는 간선이 없다.) for(int i = ..

https://school.programmers.co.kr/learn/courses/30/lessons/42895 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 아래와 같이 5와 사칙연산만으로 12를 표현할 수 있다. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4 숫자 N과 number가 주어질 때, N과 사칙연산을 통해 N의 사용횟수가 최소가 되도록 number를 만드는 것이다. 처음에는 백트레킹으로..

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 다음과 같이 n개의 제품이 n개의 공장에서 생산비용이 정해져 있다. 최소 비용을 구해라. 위의 예시에서는 1 = C, 2 = A, 3 = B 를 하면 최소비용이 된다. 3

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr String 형식으로 숫자가 최대 1백만 길이가 올 수 있다. 그 중에서 k개의 숫자를 제거해 남은 문자열중 가장 큰 문자열을 출력하면 되는 문제이다. 예를 들어 문자열이 "4177252841" 총 10개의 문자열이고, k = 4라면 최종 6개의 문자열 중에 가장 큰 수를 출력하는 것이다. 정답은 "775841" 이다. 이 문제에서 어려웠던 점은 3가지 이다. 1) 어떻게 최댓값을 구해야 하는가? 2) 문자열의 인덱스가 왔다갔다 하므로 일반화 식이 필요하다. 2) 마지막에 문자열을 출력하는데 String..

문제 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 문자열 S가 주어지면 부분 문자열 P에서 최소 DNA문자{A, C, G, T} 의 각각의 개수를 만족하는 부분문자열의 개수를 구하는 문제입니다. 예를 들어 S = AAACCTGCCAA 이고 P = 4, {A, C, G, T} = {1, 1, 1, 0}이라면 "GCCA" 가 조건을 만족한다. 문자열의 길이가 최대 1000000이므로 완전탐색을 하게 되면 시간초과가 납니다. 따라서 시작 인덱스와 끝 인덱스를 옮기는 "슬라이딩 윈도우" 방법..

문제 2567번: 색종이 - 2 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변 www.acmicpc.net 100 * 100 인 공간에서 길이가 10인 정사각형 색종이 좌표가 n개 주어졌을 때 n개의 색종이의 둘레를 구하는 문제입니다. 단순히 가로와 세로의 길이만 구하면 되는 문제 같지만 왼쪽 그림과 같이 중간에 구멍 둘레도 구해야 하기 떄문에 까다로운 문제입니다. 아이디어만 생각하면 간단한 문제입니다. 100 * 100 이차원 공간에서 색종이로 덮힌 공간은 1로 채우고, 1로 채운 공간을 4방향으로 순회하면서 0인 갯수를 세어주면 둘레가 됩니다. import j..

문제 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net n이 주어지면 1 ~ n 까지의 연속된 수들의 합이 n인 경우의 수를 구하는 것입니다. 예를 들어 n = 15이면 {1, 2, 3, 4, 5}, {456}, {7, 8}, {15} 총 4가지 입니다. 투포인터를 사용했습니다. import java.util.Scanner; public class boj_2018 { public static void main(String[] args) { Scanner sc = new Scanner(Sys..

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 영준이는 학생들의 시험을 위해 N개의 문제를 만들었다. 각 문제의 배점은 문제마다 다를 수 있고, 틀리면 0점 맞으면 배점만큼의 점수를 받게 된다. 학생들이 받을 수 있는 점수로 가능한 경우의 수는 몇 가지가 있을까? 2 3 2 3 5 10 1 1 1 1 1 1 1 1 1 1 예를 들어, 첫 번쨰 Testcase의 경우, 총 문제의 개수는 3개이며 각각의 배점은 2, 3, 5점이다 가능한 시험 점수의 경우의 수를 살펴보면 0, 2, 3, 5, 7, 8, 10의 7가지가 있다. 두 번째 Testcase의 경우, 총 문제의 개수는 10개이며 각각의 배점은 모두 ..