분류 전체보기

문제소개 1918번: 후위 표기식첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net우리가 주로 사용하는 중위표기식을 후위표기식으로 바꾸는 문제이다. 문제 풀이후위표기식 규칙과 stack을 통해 후위 표기식을 만들 수 있다.후위표기식 규칙1. 연산자가 아닌 경우 postfix에 추가한다. 2. 스택이 비어있는 경우 연산자를 스택에 넣어준다. 3. 스택이 비어있지 않은 경우 스택의 마지막 연산자가 "(" 이거나 우선순위가 낮을 때까지 스택의 마지막 요소를 postfix에 추가한다. 4. ")" 가 나왔을 경우 "(" 가 나올 때까지 스택..

문제 소개 17299번: 오등큰수첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.www.acmicpc.netAi가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다. 설명하기가 좀 복잡해서 아래 문제 캡처를 첨부한다. 문제 풀이처음 등장한 횟수를 어떻게 저장할까 고민했는데, 가장 효율적으로 접근이 가능한 데이터 구조는 딕셔너리 구조라고 생각했다. 따라서 아래와 같이 딕셔너리에 반복되는 횟수를 저장해 줬다.l..

문제 소개 10799번: 쇠막대기여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저www.acmicpc.net아래와 같이 ()로 이루어진 문자열이 주어졌을 때, 막대기는 몇조각으로 나뉠수 있는지를 물어보는 문제이다. 문제 풀이텍스트 대치 활용레이저를 "-" 로 바꿔준다음 "(" 가 나오게 된다면 막대기의 갯수를 더해주고, ")" 가 나오게 된다면 막대기의 갯수를 빼주고 count에 1을 더해주면 된다. 그리고 "-" 레이저가 나왔을때에는 총 조각의 count에 현재 막대기의 갯수를 더해준다. replacingOccurrences라는 것을 활용하면 쉽게 풀 수 있다.import..

알고리즘의 기본이라고 할 수 있는 정렬. 개념은 알고 있었으나 한 번씩 구현해보고 싶었다. 우선 가장 쉬운 정렬 알고리즘부터 시작해 보려 한다. 버블 정렬 물론 시간복잡도가 O(n^2)으로 정렬 중에 가장 정직하고 비효율적인 알고리즘이다. 계속 바로뒤의 값과 비교하면서 크기를 비교하면서 위치를 바꿔주면 된다. 아래의 gif가 가장 쉽게 표현한 것 같아서 가져왔다. 버블 정렬 구현하기 맨 마지막으로 가는 숫자는 가장 큰 숫자가 되므로 제외하고 다음 정렬을 수행한다. func bubbleSort(_ array: [Int]) -> [Int] { var array = array for i in 0.. [Int] { var array = array for i in 0.. [Int] { var array = arr..

정지문제 (Halting problem) 정지문제는 처음으로 증명된 판정불가능한 문제가 되었다고 한다. 정지문제를 간단하게 요약해보면 아래와 같다. 프로그램과 입력값이 주어졌을 때, 프로그램에 입력값을 넣고 실행한다면 프로그램이 계산을 끝내고 멈출지, 무한으로 계산할지 판정할수 있는가? 1936년에 앨런 튜링은 모든 입력값에 대해 정지문제를 풀 수 있는 일반적인 알고리즘은 존재하지 않는다는 것을 증명했다. 간단한 증명 귀류법을 사용하면 간단한데, 프로그램 a와 문자열 i입력으로 실행이 끝나면 true, 실행이 멈추지 않고 영원히 계산된다면 false가 결과값으로 나오는 halt(a, i)라는 알고리즘이 있다고 해보자. 이러한 완벽한 알고리즘을 가지고 아래의 함수를 구현했다고 한다면, 만약 trouble(..

이진탐색 알고리즘을 풀다보면 특정 조건을 만족하는 해를 찾아야 하는 경우가 있는데 이 경우 유용한 알고리즘이 이진탐색이다. 물론 데이터가 오름차순, 내림차순으로 정렬되어있는 경우, 어떠한 기준에 의하여 순서가 정해져 있는 경우에만 사용이 가능하다. 원리를 아주 간단하게 요약하자면 계속 반토막 내면서 탐색범위를 줄여나가는 것이라고 생각하면 쉽다. 그리고 확인하는 것은 탐색범위의 중간값이다. 따라서 시간복잡도는 아래의 식에 의해서 O(logN)이다. (log2 상수는 무시된다) 이진탐색 과정 이진탐색은 다음과 같은 과정을 거친다. 인덱스를 기준으로 low를 왼쪽의 맨 끝, high를 오른쪽의 맨 끝으로 정하고 시작한다. 그 low, high의 중간을 mid로 둔 뒤, mid에 있는 값을 검색한다. 임의로 여..

문제 설명 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제가 아주 심플한데, n명의 병사, k번의 무적권(?)을 가지고 enemy 배열이 주어졌을 때 최대 몇 라운드까지 갈 수 있는지를 구하는 문제였다. 문제 풀이 과정 문제 접근은 아래와 같다. 우선 무적권를 초반에 몰아서 쓴다. 그리고 그것을 stack에 넣어서 stack의 요소 중에 가장 적은 요소보다 큰 enemy가 나왔을 때 무적권을 취소하고, 그 enemy에 무적권을 쓰고, 그 제일 작은 요소에 병사를 사용하는 것으로 문제를 해결했다. 일종의 그리디 알고리즘 느낌이랄까...? 그때그때 최적을..

문제 설명 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 시소 짝궁을 구하는 문제인데, 시소의 길이는 2, 3, 4가 있다. 만약 무게가 [100,180,360,100,270] 라고 한다면 [100, 100]은 시소 짝궁이 되고, [180, 360]도 4, 2길이에 앉게된다면 시소 짝궁이 된다. 문제 풀이 무게의 배열이 10만개가 주어지기 때문에 이중 for문을 하기에는 시간초과가 확실했다. 어떻게 하면 for문을 중복해서 사용하지 않을 수 있을까? 생각보다 정말 간단하게 접근이 가능했다. 우선 same 배열, multi 배열을 만들어서 무게의 최댓값이 ..