두치의 개발공부

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제풀이 동적 계획법 개념을 적용하여 문제를 풀 수 있습니다. 연속된 수 끼리만 더할 수 있는 조건을 놓치면 안됩니다! 빈 배열(dp)을 하나 만들고, 반복문을 돌면서 입력값을 dp에 먼저 넣은 뒤에 입력값과 dp의 이전값 + 입력값을 비교하여 dp의 이전값 + 입력값이 더 크면 더하여 dp의 해당 index 값을 바꾸면 됩니다. 소스코드 /* 연속된 수 끼리만 더할 수 있다. list 이번값과 dp 이전값..

문제 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제풀이 집을 만날 때 마다(값이 1) 주변에 있는 값을 탐색하여(위, 아래, 오른쪽, 왼쪽) 1이 몇개나 근접 해 있는지 확인 하면 된다. 한번 방문한 집은 또 방문하면 안되기 때문에 방문 여부를 체크하는 이차원 배열도 따로 만들어서 방문여부를 관리한다. 탐색 알고리즘 중 DFS를 사용하여 문제를 풀면 된다. DFS는 재귀용법을 이용하여 풀이를 많이 하므로 본 문제에서도 stack 자료구조를..

문제 https://www.acmicpc.net/problem/1236 1236번: 성 지키기 첫째 줄에 성의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 성의 상태가 주어진다. 성의 상태는 .은 빈칸, X는 경비원이 있는 칸이다 www.acmicpc.net 문제풀이 모든 행과 열 에서 경비원을 다 세울 수 있는 경우의 수를 따져야한다. 처음에 문제를 자세히 안 읽고 행만 따지고 예제를 입력하였는데 다 통과하여 제출하였더니 실패하여 당황하였다... 문제를 처음부터 꼼꼼히 읽도록 하자. 풀이는 행과 열에서의 각각의 경우에서 경비원을 세울 수 있는 수를 카운트 하여, 둘 중에 큰 수를 반환하면 된다. 행과 열중 어디에 놓든간에 큰 수를 선..

문제 https://www.acmicpc.net/problem/1668 1668번: 트로피 진열 민식이는 “오민식”이라는 팀이름으로 수없이 많은 로봇대회를 우승했다. 따라서 민식이의 집에는 트로피가 많다. 민식이는 트로피를 어떤 선반 위에 올려놨다. 이 선반은 민식이의 방문을 열 www.acmicpc.net 문제 풀이 처음에 문제를 보면 무슨 소리인지 잘 모르겠으나 그림을 그려보면 어렵지 않게 이해할 수 있다. 왼쪽에서 봤을 때 보이는 트로피는 1,4,5,7 로 4개이다. 오른쪽에서 봤을 때 보이는 트로피는 1,7 로 2개이다. 본인보다 더 큰 트로피가 있는 경우에만 카운트 해 주면 된다. 왼쪽에서 먼저 체크 후 배열을 reverse한 후 다시 체크 하면 오른쪽에서 본 트로피를 확인할 수 있다. 똑같은 ..

문제 https://www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net 문제풀이 가장 많이 팔린 책이 여러권일 때 사전순이기 때문에 먼저 입력받은 책들을 sort한 후 시작하였다. 먼저 배열의 첫번째 책을 변수로 할당하고 입력받은 책들을 반복문 돌면서 지금 책과 반복문의 책이 같으면 count를 +1 하고, 같지 않으면 count를 1로 바꿔준다. 현재의 count(nowCnt)가 가장 많이 팔린 책의 count(maxCnt)보다 크면 책 이름을 바꿔준다..

문제 https://www.acmicpc.net/problem/1568 1568번: 새 N마리의 새가 나무에 앉아있고, 자연수를 배우기 원한다. 새들은 1부터 모든 자연수를 오름차순으로 노래한다. 어떤 숫자 K를 노래할 때, K마리의 새가 나무에서 하늘을 향해 날아간다. 만약, 현 www.acmicpc.net 문제 풀이 새들이 오름차순으로 증가하는 만큼 나무에서 날아가게 된다. 14마리의 새가 있었을 경우 1,2,3,4,1,2,1 해서 총 7초가 걸린다. 4에서 1이 되는 이유는 나무에 남아있는 새의 수(14 - (1+2+3+4)) 가 4마리 이기 때문에 5마리가 날아갈 수 없으므로 다시 1마리로 바꿔주는 경우이다. 소스코드 const answer = (input) => { let treeBird = N..

문제 https://www.acmicpc.net/problem/1543 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 문제풀이 전체 문자열에서 찾으려는 문자를 찾아야 한다. 전체 문자열에서 index 0부터 시작하여 문자의 길이만큼 잘라서 찾으려는 문자와 같다고 하면 index를 문자의 길이만큼 더하여 오른쪽으로 이동하고, 찾으려는 문자와 같지 않다고 하면 index에 +1을 하여 오른쪽으로 1칸씩 이동하면 된다. 위 과정을 (전체 문자열 - 현재 index > 찾으려는 문자열의 길이) 일 때까지 계속 반복하면 ..

문제 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제풀이 최솟값을 구하는거기 때문에 빼는 값이 최대인 경우를 구하면 총 합의 최솟값을 구할 수 있다. 우선 -로 split하여 - 뒤에 괄호로 묶일 수 있는 + 연산자를 나눈다. ex) "55-50+45-20-10+30" => [55,50+45,20,10+30] 그 후에 +가 섞여있는 문자열을 +로 split한 후 합 연산을 한다. ex) [55,50+45,20,10+30] => [55..

문제 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제풀이 하나의 회의실에 여러개의 회의 일정이 있고 이 일정을 최대로 잡을 수 있도록 한다. 회의를 최대로 할려면 짧은 회의를 많이 잡는게 효율적이다. 등록된 회의를 아래 기준으로 정렬한다. 1. 제일 빠르게 끝나는 회의 순서 2. 끝나는 시간이 같을 시에는 시작 시간이 빠른 순서 이렇게 정렬하여 순서대로 회의를 잡는다. 시작 시간이 이전 종료 시간보다 나중이면 새로운 회의이다. 코드 const answer = ([n, ...arr]) => { const times = arr.map((list) => lis..

문제 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제풀이 매 순간 최적의 방법을 찾아내는 탐욕 알고리즘의 문제이다. 최소의 동전으로 가치의 값을 충족시켜야 하기 때문에 가치를 가장 큰 동전으로 많이 채워야 동전을 적게 쓸 수 있다. 오름차순으로 입력받는 동전을 내림차순으로 정렬하여 앞에서 부터 가치가 동전으로 나누어지는 값이면 몫은 사용된 동전 갯수로, 나머지값은 앞으로 채워..