어흥

문제 링크: https://www.acmicpc.net/problem/2800 2800번: 괄호 제거 첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개 www.acmicpc.net 1. 주의할 점 - 출력 결과로 서로 다른 문자열을 사전순으로 출력해야 한다 2. 구현 - Stack을 통해 개구간과 폐구간을 계산하여 쌍을 이룰 경우 각각 Open, Close 벡터에 인덱스 번호를 추가한다 - DFS() 함수를 통해 최대 2^10-1의 경우를 계산하며, 일부 괄호를 제거한 문자열의 경우 Set에 추가하여 중복을 제거한다 - C++에서..

문제 링크: https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 1. 주의할 점 - Set + DFS/BFS로 시도시 메모리 초과 발생 가능 2. 구현 (1) Set + BFS : 메모리 초과 - 현재 Queue의 Front에 담긴 문자열을 기준으로 뒤에 'A' 추가 or 뒤집기 + 'B' 추가 시도하며, 해당 문자열이 이미 셋에 존재한다면 큐에 넣지 않는다 - BFS는 First==Second 혹은 First..

문제 링크: https://www.acmicpc.net/problem/17265 17265번: 나의 인생에는 수학과 함께 세현이의 인생의 목표는 1분 1초 모든 순간 수학과 함께 살아가는 것이다. 그렇기 때문에 매일 수학을 생각하면서 살아가고 있다. 세현이는 밥을 먹을 때도 쌀알의 수를 계산하여 칼로리를 바로 www.acmicpc.net 1. 주의할 점 - 이동 가능한 방법으로는 하하, 하우, 우하, 우우 총 4가지의 방법이 존재한다 2. 구현 - Check[][][] 배열을 통해 각 지점까지 이동할 때 얻을 수 있는 최대 및 최소값을 저장한다 - BFS() 함수를 2번 수행하여 한 번은 최대를, 다른 한번은 최소를 구하도록 한다 - BFS 탐색을 수행하기전, Check[][] 배열을 초기화하고 시작한다..

문제 링크: https://www.acmicpc.net/problem/22116 22116번: 창영이와 퇴근 A1,1에서 AN,N까지, 경로상의 최대 경사의 최솟값을 출력한다. www.acmicpc.net 1. 주의할 점 - 여러가지 푸는 방식이 존재하지만, 1씩 증가시키면서 10억까지 테스트 → TLE 발생 2. 구현 - BFS+이분탐색을 통해 차이가 Mid이하라면 전진이 가능하다고 판단 - L=0, R=10억, Result = R-L로 초기화 하고 이분탐색을 시작한다 - Mid = L+(R-L)/2를 통해 Mid값을 갱신하고, BFS()가 가능하면 Result의 값도 갱신한다 import java.util.*; import java.lang.*; import java.io.*; class Main {..

문제 링크: https://www.acmicpc.net/problem/1662 1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net 1. 주의할 점 - 괄호에 대한 처리 - 문자열을 복원 v.s 길이만 구하기 2. 구현 - 문자열을 복원하지 않고 길이만 구해도 되므로, 길이만 구하여 메모리 또한 아낄 수 있도록 한다. 다만, 구현이 좀 더 복잡 할 수 있다 - Stack 2개를 이용하여 해결한다 #예시 234(10) - Len 스택에는 '(' 괄호가 나오기 전의 숫자를 제외하고 계산된 길이. 위의 예시에선 '..

문제 링크: https://www.acmicpc.net/problem/17616 17616번: 등수 찾기 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 세 정수 N, M, X가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 105, 1 ≤ M ≤ min(N(N-1)/2, 5×105), 1 ≤ X ≤ N) . 다음 M 줄에는 각각 두 정수 A, B가 주어 www.acmicpc.net 1. 주의할 점 - N≤10^5이므로 간선들의 정보를 나타내는 2차원 배열을 사용하지 않는다 2. 구현 - 가장 높은 등수는 1+ (해당 학생보다 잘 본 학생 수) - 가장 낮은 등수는 전체 학생수 - (해당 학생보다 못 본 학생 수) - Check[][2] 배열을 통해 각 Node를 방문했는지 검사한다([][0]: 정방..

문제 링크: https://www.acmicpc.net/problem/2637 2637번: 장난감조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 1. 주의할 점 - 위상정렬로 접근한다 - 필요한 물품의 개수를 List 형태로 담지 않는다 → 메모리 초과 회피 2. 구현 - Info 형태의 구조체를 이용하여 A의 물건을 만들기 위해 Idx번째 물건이 Val만큼 필요하다는 것을 나타낸다 - Need[] 배열을 통해 필요한 총 물건의 수를 저장한다 - Conn[] 배열을 통해 연결된 상위부품의 수를 나타낸다..

문제 링크: https://www.acmicpc.net/problem/11562 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 1. 주의할 점 - 매 쿼리마다 통행을 바꿔야하는 횟수를 구하지 않는다 2. 구현 - Arr[][] 배열을 통해 간선에 대한 정보를 받으며, Arr[a][b]는 a->b로 가기 위해 바꿔야 하는 도로의 수를 저장한다 - Arr[][] 배열을 초기화하고, 입력받을 때 단방향인 경우에는 0,1을 저장하고 양방향인 경우에는 0,0을 저장한다 - 플로이드 와샬 알고리즘을 통해 Arr[][]..