분류 전체보기318

• ★ 백준/1912 연속합 / 다이나믹 프로그래밍,메모이제이션 연속합 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 (추가 시간 없음) 128 MB 114189 40905 28810 34.544% 문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. 입력 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 출력 첫째 줄에 답을 출력.. 자바/알고리즘 문제 풀이 2022. 12. 19.

• 

  백준/9461 파도반 수열 / 다이나믹프로그래밍 + 제출전 최악의경우 체크해보기 파도반 수열 성공다국어 한국어 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 128 MB 76537 33556 27488 42.495% 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이.. 자바/알고리즘 문제 풀이 2022. 12. 16.

• 백준/1904 01타일 / 다이나믹 프로그래밍 + 제출전 최악의경우값들 넣어보기 + dp배열의 크기는 나올수있는 최대값으로 잡기 01타일 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 0.75 초 (추가 시간 없음) 256 MB 75477 24571 19491 31.851% 문제 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다. 그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, .. 자바/알고리즘 문제 풀이 2022. 12. 16.

• 

  백준/14889 스타트와 링크 / 조합 = dfs + 백트래킹 스타트와 링크 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 512 MB 72451 35877 21057 46.362% 문제 오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은.. 자바/알고리즘 문제 풀이 2022. 12. 16.

• 

  ★★10) 스프링으로 전환하기, ApplicationContext ,@Configuration,@Bean , 스프링 컨테이너, 스프링 빈 , 스프링컨테이너 생성과정 AppConfig.java 수정 @Configuration을 클래스 앞에 붙여서 앱의 구성정보,설정정보 파일임을 명시해준다. @Bean 어노테이션을 각 메서드에 붙여준다. -> 각 객체들이 스프링컨테이너에 등록된다. @Configuration public class AppConfig { //프로젝트의 객체 생성,구성,주입 환경설정을 하는 중요 역할 @Bean public MemberService memberService() { return new MemberServiceImpl(MemberRepository()); } @Bean public MemberRepository MemberRepository() { return new MemoryMemberRepository(); } @Bean public Or.. 인프런/스프링핵심원리(기본) 2022. 12. 15.

• 

  백준/14888 연산자 끼워넣기 /dfs + 백트래킹 / 완전탐색(브루트포스) 연산자 끼워넣기 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 512 MB 74842 39010 24835 49.319% 문제 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다. 예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같.. 자바/알고리즘 문제 풀이 2022. 12. 15.

• 

  백준/15651 N과 M (3) // 중복 순열 N과 M (3) 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 512 MB 46848 31120 23601 66.711% 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 예제 입력 1 복사 3 1 예제 출력 1 복사 1 2 3 예제 입력 2 복사 4 2 예제 출력 2 복사 1 .. 자바/알고리즘 문제 풀이 2022. 12. 15.

• 

  백준/15649 N과 M(1) // 순열 N과 M (1) 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 512 MB 72866 45638 30107 61.833% 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 예제 입력 1 복사 3 1 예제 출력 1 복사 1 2 3 예제 입력 2 복사 4 2 예제 출력 2 복사 1 2 1 3 1 4 2 1.. 자바/알고리즘 문제 풀이 2022. 12. 15.

• 

  백준/1676 팩토리얼 0의 개수 // BigInteger , 0의개수 규칙 팩토리얼 0의 개수 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 128 MB 52448 25204 20824 47.857% 문제 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500) 출력 첫째 줄에 구한 0의 개수를 출력한다. 예제 입력 1 복사 10 예제 출력 1 복사 2 예제 입력 2 복사 3 예제 출력 2 복사 0 풀이 //팩토리얼 문제 , 팩토리얼은 상당히 큰수를 만들게된다. //여기서는 n이 최대 500이다. 500!는 상상도 못할 큰수일것이다. 팩토리얼 계산사이트에 500!를 입력해보니 너무큰숫자이다. //이 숫자는 int이든 long이든 담을 수 없다. //그럴때 사용하는것이 .. 자바/알고리즘 문제 풀이 2022. 12. 15.

• 

  백준/9375 패션왕 신해빈 // 조합 , 경우의 수 패션왕 신해빈 성공다국어 한국어 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 128 MB 24592 13453 11559 54.863% 문제 해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까? 입력 첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다. 각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다. 다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되.. 자바/알고리즘 문제 풀이 2022. 12. 15.

• 

  백준/1010 다리놓기 // 파스칼 삼각형 + 다이나믹프로그래밍 다리 놓기 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 0.5 초 (추가 시간 없음) 128 MB 64625 29963 24502 48.438% 문제 재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M) 재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원.. 자바/알고리즘 문제 풀이 2022. 12. 15.

• 

  [Java] 동적프로그래밍 , Dynamic Programming 동적프로그래밍 DP, 동적프로그래밍은 하나의 큰 문제를 여러개의 작은 문제로 나눠서 그 결과를 저장하고 다시 큰 문제를 해결할 때 사용하는것으로 특정한 알고리즘이 아닌 하나의 문제해결법이라고 볼 수 있다. 큰 문제를 작은 문제로 쪼개서 , 작은 문제의 답을 저장하고 저장한 답을 이용하여 점점 큰 문제를 해결하면서 저장 한다. 그렇게 원하는 값까지 도달한다. (기억하며 풀기라고 불리기도 한다.) DP를 쓰는이유 일반적인 재귀방식 또한 DP와 유사하다. 하지만 일반적인 재귀는 똑같은 작은 문제들을 여러번 계산하게 되서 비효율적이라는것이다. 예를 들어 피보나치 수열을 구하는 재귀의 동작방식을 살펴보자. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ... 처럼 진행되는 피보나치를 .. 자바/알고리즘 2022. 12. 14.