매일 성장하자!!

문제 https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 풀이 산술평균 더해서 나누면 되는데, -1.8인 경우 반올림하면 -1이아닌 -2가 되어야함. 이 부분을 처리하기 위해 나는 나눈 값 절대값으로 바꾼 뒤, Math.round를 이용 오랜만에 자바를 해서 그런지 나눌때 auto casting되는걸 까먹었당. int / int => int가 된다. 그래서 피연산자 둘중 하나를 명시적으로 double로 casting 후 나눠야한다. 중앙값 ArrayList를 이..

문제 https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 풀이 처음에는 21 length를가진 boolean 배열을 이용했는데, 그냥 집합 자료구조를 이용하면 쉽다. 집합은 중복이 되지 않고, 집합의 특정 값에 접근할때, 값을 해쉬하여, 특정 버킷에 바로바로 접근가능하여 빠르다. 집합은 순서 X, 정렬 X, 중복 X 코드 배열 이용 package baekjoon.구현; import java.io.*; import java.util.Arrays; import java.util.Stri..

문제 https://www.acmicpc.net/problem/3980 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net 풀이 11개의 포지션에 11명의 선수를 넣어주면 된다. 모든 경우의수를 돌며 최대 값을 뽑으면된다. 단, 해당 포지션의 성능이 0이면 해당 포지션에 선수를 배치하지 못하는 가지치기 조건을 이용해 경우의 수를 대폭 줄이면 된다. 즉, 백트래킹을 통해 가지치기로 시간적 이득을 봐야만 맞을수 있는 문제이다. 너무간단한데, 테스트 횟수가 있으므로 static 변수를 사용한다면 초기화를 계속 해줘야한다. (이거 놓쳐서 2번 틀림..

문제 https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 풀이 1 2 3 밖에 존재하지 못하는 수열중, 가장 작은 좋은 수열을 구하면 된다. 즉, 나쁜수열이면 안된다.. 가장 작은 숫자를 구하라 하였는데, 1 -> 2 -> 3 으로 탐색을 하면 자연스럽게 가장 작은 숫자가 나온다. 백트래킹 문제로 나쁜 수열이면 가지치기를 해서 경우를 많이 줄여 주면 간단하게 풀수있다. 즉, 재귀함수로 돌리다가 조건에 맞지않으면 그뒤의 가지들은 잘라버리고 다음 가지로 넘어간다...

문제 https://www.acmicpc.net/problem/1174 1174번: 줄어드는 숫자 음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 숫자라고 한다. 예를 들어, 321와 950은 줄어드는 숫자이고, 322와 958은 아니다. N번째로 작은 줄어 www.acmicpc.net 풀이 문제는 너무 단순한데 보자마자 쉽게 어떻게 풀지 떠오르지가 않았습니다. 구래서, 일단 제일 작은수부터 나열해보았습니다. 0 1 2 0 1 2 3 4 5 6 7 8 9 10 20 21 30 31 32 40 41 42 43 50 51 52 53 54 60 61 62 63 64 65 70 71 72 73 74 75 76 80 81 82 83 84 ., 97 98 (세자리) 2..

문제 https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 풀이 백트래킹 문제이다. 적절하게 재귀함수를 이용해서 계란을 칠수있는 모든 경우의 수를 파악해야한다. 어떻게 하면 달걀을 집어서 칠 대상 달걀을 고르는 경우를 생각할수있을까? 일단 어떤식으로 할수있는지 간단하게 생각하자. 달걀 a, b, c, d, e 다섯개가 있다고하자. a 를 들고 b를 칠수있다. 그다음은 한칸 오른쪽 달걀을 들어야한다. 치는 대상은 아무거나 하나를 칠수있으..

문제 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 풀이 백트래킹 문제이다. 재귀함수를 통해서 탐색하되, 가지치기를 통해 경우의 수를 줄여야한다. 재귀함수에대한 이해가 부족하면 풀기어렵다.(백트래킹 기본 N, M문제를 많이 풀어봐야한다 생각함!!) 2차원 배열로 어떠한 도시에서 어떠한 도시로가는 비용이 적혀있다. 외판원이 어떠한 도시에서 출발하여 모든 도시를 돌고 다시 시작한 어떠한 도시로 돌아오는..

문제 풀이 재귀함수로 풀면된다. 재귀함수로 풀다가, 뽑고자하는 M개를 뽑으면 경우를 만들고, return해서 재귀 끝내주고 다시 그 다음 경우를 계속해서 보면된다. 수열은 중복이 되면 안된다는 것에 유의하자. 나는 두가지 방법으로 풀었다. 1) stack을 이용한 풀이 방문한 숫자의 순서를 기록해야 하므로 먼저 방문한 녀석을 순서대로 스택에 담는 형태로 풀었다. 방문한 숫자를 스택에 넣고, 스택의 크기가 M과 같으면 stack에 들어간 순서대로 출력하고, 다시 스택에서 빼고.. (스택에 해당 수가 있으면 다음 숫자 탐색) 를 반복해서 풀었따. 2) visited boolean 배열과, 결과를 담을 result int 배열 중복에 대한 처리는 visited boolean 배열을 통해 하였다. 그리고 탐색한..

문제 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 풀이 제일 작은 수가 되려면 -가 나오고 뒤에 +들이 나오면 -(a + b + c + d +...)만 고려하면 된다. 처음에 나는 split이 생각나지않아, 결과 스택과 버퍼 스택을 만들어서, -가 나온다음 뒤에 +들이 나오면 버퍼 스택에 다 넣고 다시 - 가나오면 버퍼스택의 값들 다 더해서 - 붙인 값을 결과 스택에 넣고.. 이런 복잡한 방법으로 풀려 노력했다. 그냥 문자열 split..

문제 https://www.acmicpc.net/problem/11052 풀이 민규는 N개의 카드를 사는데 최대 가격을 지불해야한다. 최초 시도할때 나의 생각은 N개의 카드를 산다하면 1개가든 팩 N개, 1개가 든 팩 N - 1개 + 2개가 든 팩 1개, 1개가든 팩 N - 2개 + 2개가 든 팩 2개, ... 이런식으로 경우의수를 모두 구해서 최대값을 구해야하나? 즉 브루트포스로 풀어야하나란 생각을 했다. 이렇게 생각하니 어떻게 풀어야할지도 모르겠고 막막했다. 그래서, dp를 통해서 풀자! 라는 생각을 했다. i개의 카드를 사기위해 최대 가격을 지불해야한다. 이미 dp테이블에 1부터 i - 1까지 카드를 살때 최대 가격이 적혀져있다고 가정하자. 그렇다면, i개를 사기 위해 따져봐야하는 경우는 dp[1]..