Algorithm Cinema

10809번: 알파벳 찾기 (acmicpc.net) 10809번: 알파벳 찾기 각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다. 만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출 www.acmicpc.net 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다. 만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출력한다. 단어의 첫 번째 글자는 0번째 위치이고, 두 번째 글자는 1번째 위치이다. 알파벳이 나타남에 따라 문자열 내에서 처음 등장하는 위치(인덱스)를 a b c d e f .. 순으로 표기하는 알고리즘이다. ..

1918번: 후위 표기식 (acmicpc.net) 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 1. 여러분의 마음을 읽어보자. A+B*C-D/E ABC*+DE/-​ 여기는 문자 뭉탱이 연산자 뭉탱이 문자 뭉탱이 연산자 뭉탱이 순으로 뭉탱이들이 다채로운 case. 아마 까다로워할 포인트는 A*(B+C) ABC+* 처럼 문자 한 뭉탱이가 나오고 연산자 뭉탱이가 나오는 case. 이 두 case가 달라서 구현을 어떻게 접근해야할지 조차 모르는 분들이 많을 것이다. 2. 문자는 그대로? 일단 문자의 순서는 변..

1935번: 후위 표기식2 (acmicpc.net) 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net 후위표기식 관련 문제이다. 후위표기식은 한마디로 연산자가 뒤로 가는거다. ab+ 는 a+b abc*+de/- > (b*c)+a - (d/e) 뭐 이런느낌이다. 계산순서를 보면 알 수 있듯, 일단 스택을 활용하는게 상당히 적절해보인다. 일단 만약 알파벳이 5개의 종류대로 숫자가 순서대로 input된다는 점은 상당히 편하다. 5 ABC*+DE/- 1 2 3 4 5 이 예제를 들어 생각해보자. 1. 소수 ..

17299번: 오등큰수 (acmicpc.net) 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미. 1. 카운팅 배열 일단 빈도수체크를 해야하는 점. 여기서 카운팅 배열을 하나 만들어 아이디어를 떠오르는 게 좋겠다. (수의 max range가 100만이니 100만+1짜를 만든다.) 그래서 input을 받고나면 정수 값마다의 인덱스에 자신들의 빈도수가 체크가 되겠다. 2. 스택 스택을 쓰는 근거는 최신 업데이트를 필..

17298번: 오큰수 (acmicpc.net) 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다. 예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4,..

10799번: 쇠막대기 (acmicpc.net) 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 닫는 괄호와 여는 괄호를 중심으로 문제를 해결해야하는 문제. - 이 괄호 꺾쇠를 보면 이젠 습관적으로 스택을 떠올리게 된다. 이 문제 역시 스택으로 풀었어야했다. 난 처음에 어느 괄호를 기준으로 잡아야할지 감이 안와서 잘 못 풀었었다. 뭐 크게 경우는 두가지 이지만, 연속될 경우를 잘봐야 한다. 접근. 1. (( / () / )) / )( / 총 4가지의 연속경우가 있으니 이를 잘 참고해야겠다. ()인 경우 레이저를 표시하기에..

17413번: 단어 뒤집기 2 (acmicpc.net) 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 있다. 문자열의 시작과 끝은 공백이 아니다. ''가 문자열에 있는 경우 번갈아가면서 등장하며, ''일때 닫는 꺾쇠이기에, tag type > false & >도 ..

1158번: 요세푸스 문제 (acmicpc.net) 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)- 요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램. 1. 원을 이루면서 앉..

단편영화 _공생 (youtube.com) 첫 단편영화를 제작해보았다. 대학교 영화제작 팀이 있어서 팀원들과 협업하여 영화를 제작했다. 제작기간은 한 4개월정도 걸렸다. 운이 좋게도 나의 시나리오가 좋게 평가받아서 내가 총감독을 맡게 되었다. 1. 시나리오 작성 시나리오는 쓰는데 진짜 얼마 안걸렸다. 저번에 봉준호 감독의 인터뷰가 있었는데, 영화 기생충이었나 자신은 시나리오를 카페에서 많이 쓰고는 하는데 한 영화 시나리오쓰는데 2시간정도 걸린다 했던 인터뷰가 기억에 남는데, 나도 막상 시나리오를 써보니 1시간도 안 걸린거 같았다. 물론 단편영화라 짧게 걸리지 않았나 싶다. 쓱쓱 썼던것 같다. 2. 주제 내가 생각했던 메인주제는 이중인격이었다. 이중인격은 대개 하나의 인물이 두개의 인격으로 행동하는 것이지만..

1406번: 에디터 (acmicpc.net) 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 명령어 4가지를 통해 문자열을 control해보는 문제. 커서를 활용하는 특이한 문제다. 특이한 점은 시간제한이 빡세다 0.3초.. 첫번째 접근. 그냥 stringBuilder와 인덱싱 활용해서 풀기, - 답은 맞게나오나, 성능이 o(n)으로 낫배드나, 0.3초라 시간제한에 걸렸다 두번째 접근 커서 활용 >> LinkedList의 ListIterator로 문제 해결하기. 얘는 시간제한에 안걸리고 풀었다 iterator의..