알고리즘,PS

https://www.acmicpc.net/problem/16198 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net 📝문제 📝풀이 DFS 완전 탐색 문제이다. 1 2 3 4 가 주어질 때 (3) 번을 고를 경우 => energy += 2*4 가 되고 1 2 4 가 남는다. 1 4 는 고를 수 없기 때문에 남은 2번을 고르면 energy += 1*4 를 하면 최종적으로 12가 나온다. List 하나 선언해서 DFS를 돌리고 해당 위치 x 를 remove 한 뒤 백트래킹을해서 다시 x 를 넣어 주는 식으로 하..

https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 📝문제 📝풀이 시간제한을 보면 매우 빡빡한 것을 알 수 있다. 실패한 원인은 처음에 LinkedList 를 썼으나 결국엔 조건을 만족하기 위해서 index를 타야 했기 때문 입력이 매우 길기 때문에 index를 탈 생각을 하면 안된다 ( StringBuilder.insert 연산도 마찬가지) 따라서 2개의 스택만으로 모든 걸 해결해야 하는 문제이다 package baekjoon; import sta..

https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 📝문제 📝풀이 괄호 짝이 맞는 지 검사하는 작업에 더해서 괄호에 따른 연산을 추가로 하는 문제이다. 1. 열린 괄호인 경우 : - stack 에 push 한 뒤 임시 변수에 곱 연산을 한다. 2. 닫힌 괄호인 경우 : 2.1 이전 괄호가 짝이 맞는 열린 괄호인 경우 - 더 이상 곱 연산이 적용 되지 않는 원소이므로 최종 결과 값에 더해준다 2.2 stack의 맨 위 원소와 짝이 맞지 않거나 st..

https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 📝문제 📝풀이 단순 완전 탐색 + 구현 문제이다 주어진 map 좌표에서 높이의 범위를 받은다음 범위 내 높이를 기준 h 에서 평평해지는 조건을 전부 찾아 time과 inventory 조건을 만족할 때 마다 갱신을 시켜주면 된다. import static java.util.Arrays.*; import java.io.*; public class Main { static int[][] map; st..

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 📝문제 📝풀이 완전탐색 문제이다 목표채널 target 까지 0~999999 사이까지 모두 탐색해서 만약 고장난 버튼이 없이 갈 수 있다면 그 채널에서 target 차이와 자릿수를 합한 결과를 반환하면 된다 import static java.util.Arrays.*; import static java.util.stream.Collectors.*; import java.util.*; ..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 📝문제 📝풀이 테트리스 블록을 암거나 하나 놓았을 때 그 블록이 위치한 격자 점수 합의 최대값을 구하는 문제이다. 어느 한 점 x,y 에서 시작해서 깊이 우선탐색 DFS를 돌리면 블록 모양이 나온다. 그런데 T 블록은 DFS로 구할 수 없으니 , 그 구간만 BFS로 구해야한다. BFS를 진행할 때 만약 4방향 모두 진행 할 수 있다면 중심좌표 x,y 의 값 + (4방향 좌표의 합) = sum 이라..

https://www.acmicpc.net/problem/1800 1800번: 인터넷 설치 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차 www.acmicpc.net 📝문제 📝풀이 처음 풀어보는 유형의 문제다. 아이디어를 못 떠올려서 도움을 받았다.. 만약 1-3-2-5 이런식으로 연결 된다고 치면 각각 edge들에 대하여 가중치들은 4, 3, 9 원이다. 여기서 k=1, 회선 하나는 공짜로 준다고 했으니 제일 비싼 9원을 빼면 남은건 4, 3 인데 이들 중 제일 비싼 회선 값만 return 하므로 ans=4 이 답이다..

https://www.acmicpc.net/problem/1032 1032번: 명령 프롬프트 첫째 줄에 파일 이름의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 파일 이름이 주어진다. N은 50보다 작거나 같은 자연수이고 파일 이름의 길이는 모두 같고 길이는 최대 50이다. 파일이름은 www.acmicpc.net 📝문제 📝풀이 명령어 길이는 같으니 맨 위의 명령어를 대표로 잡고 세로로 비교 만약 다른 문자가 있으면 '?' 으로 치환, 그렇지 않으면 그 문자 그대로 쓰기 import static java.util.Arrays.*; import static java.util.stream.Collectors.*; import java.util.*; import java.io.*; import java.ut..