전체 글

[백준] 1158 - 요세푸스 문제 (자바/Java)

문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) 출력 예제와 같이 요세푸스 순열을 출력한다. 풀이 1 링크드 리스트를 큐처럼 활용하여 풀었다. cnt는 1부..

[알고리즘] 삽입 정렬 Insertion Sort (자바/Java)

목차 삽입 정렬 0번째부터 i번째까지 정렬된 배열의 크기를 증가시키며 정렬하는 알고리즘 이미 정렬된 i개짜리 배열에 하나의 원소를 더하여 정렬된 i+1개짜리 배열 만들기! 시간 복잡도: $O(n^2)$ 과정 i번째 원소를 정렬할 차례 i-1번째까지의 원소들은 정렬되어 있음 i-1부터 0까지의 원소들과 i번째 원소(key)를 비교하며, i번째 원소보다 작은 원소를 만나면 break, i번째 원소보다 크다면 해당 원소를 오른쪽으로 한 칸씩 shift break한 원소 다음 자리에 i번째 원소를 삽입 1부터 마지막 원소까지 반복 1 0번째 원소는 정렬된 상태 i=1, 10 10..

[자료구조] 트리 & 이진 탐색 트리 Binary Search Tree (자바/Java)

목차 트리 (Tree) 비-선형 자료 구조 (Non-Linear) 선형 자료 구조: 구조에 저장될 데이터들이 순차적으로 저장되는 형태 ArrayList, LinkedList, Map, Stack, Queue 등 비-선형 자료 구조: 복수의 데이터들이 복수의 데이터들과 연결될 수 있는 구조 Tree 검색 트리 내장 vs 외장 검색 트리 내장 검색 트리: 메인 메모리 내에 존재 외장 검색 트리: 검색 트리가 외부(주로 디스크)에 존재-검색 트리 전체를 메인 메모리에 올려놓고 쓸 수 없는 경우 이진 검색 트리(Binary Search Tree) 특성 각 노드는 키값을 하나씩 갖는다. 이 키값은 모두 다르다. 최상위 레벨에 루트 노드가 있고, 각 노드는 최대 2개의 자식 노드를 갖는다. 임의 노드의 키값은 자기..

[자료구조] 스택 Stack & 큐 Queue

목차 Stack 스택 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조 Last in First out: 마지막에 삽입한 자료를 가장 먼저 꺼냄 선형구조(자료 간의 관계가 1대 1의 관계) 맨 위의 원소만 접근 가능(top) 응용: 문자열 뒤집기, postfix 계산 메소드 push: 스택에 값을 추가 pop: 스택의 마지막 값을 삭제하고 반환 peek: 스택의 마지막 값을 반환(삭제x) isEmpty: 스택이 비어있는지 확인 push, pop 배열 스택을 이용 public class MyArrayStack { private E[] stack; private int topIndex; public void push(E item) { stack[++topIndex] = item; } public E po..

[자료구조] 스택 Stack 활용: 후위 표기식 계산기 (자바/Java)

목차 스택을 활용하여 후위 표기식 계산기를 구현할 수 있다. 먼저 중위표기식을 후위 표기식으로 바꾸고, 이를 다시 계산해야 한다. 1. 중위 표기식 → 후위 표기식 이 과정이 상대적으로 까다롭다. 먼저 연산자 우선순위를 고려해야 한다. 연산자는 사칙 연산(+ - * /)과 괄호만 들어온다고 가정한다. 1. 입력이 연산자가 아닌 경우 바로 출력해준다. StringBuilder를 사용하여 sb에 append하였다. 2. 입력이 연산자인 경우 2-1. 괄호인 경우 괄호는 연산자 중에서도 특수한 경우이다. 먼저 좌괄호 '('인 경우 stack에 그냥 push한다. 그리고 우괄호 ')'가 나오면, 좌괄호가 나올 때까지 stack에 있는 연산자들을 모두 pop하여 출력한다. 그리고 좌괄호는 연산에 포함되지 않으니,..

[백준] 4949 - 균형잡힌 세상 (자바/Java) 스택 Stack

문제 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다. 문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다. 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다. 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다. 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다. 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다. 짝을 이루는 두 괄호가 있을 때, 그 사이에 있..

[백준] 9012 - 괄호 (자바/Java) 스택 Stack 괄호 검사

문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 여러분은 입력으로 주어진 괄호 문자열..

[백준] 10156 - 개미 (자바/Java)

문제 가로 길이가 w이고 세로 길이가 h인 2차원 격자 공간이 있다. 이 격자는 아래 그림처럼 왼쪽 아래가 (0,0)이고 오른쪽 위가 (w,h)이다. 이 공간 안의 좌표 (p,q)에 개미 한 마리가 놓여있다. 개미는 오른쪽 위 45도 방향으로 일정한 속력으로 움직이기 시작한다. 처음에 (p,q)에서 출발한 개미는 1시간 후에는 (p+1,q+1)로 옮겨간다. 단, 이 속력으로 움직이다가 경계면에 부딪치면 같은 속력으로 반사되어 움직인다. 위 그림은 6×4 격자에서 처음에 (4,1)에서 출발한 개미가 움직인 길을 보여주고 있다. 처음에 (4,1)에 있는 개미는 2시간 후에 (6,3)에 있으며 8시간 후에 (0,1)에 있다. 만일 그 개미가 처음에 (5,3)에 있었다면 매 시간마다 (6,4), (5,3), (..

[SWEA] 1216 - 회문 2 (자바/Java)

처음에는 각 행과 열에서 0과 99에서 시작해서, 두 값이 같으면 start와 end를 1씩 감소 시키고, 아닌 경우에는 start와 end 중 하나만 감소시키며 검사하려고 하였는데, 재귀로 구현하였더니 case가 너무 많고 예외처리가 잘 안되어서 무한 루프가 일어났다. 두 값이 같지 않을 경우 start를 1 증가시키거나, end를 1 증가시키면서 값을 찾아야 하는데, 그 과정에서 최대 길이인 회문을 찾는 과정을 보장하지 못하였다. 그래서 이중 for문에서 값을 하나하나 돌며, 해당 index값을 중앙값으로 하는 최대 회문의 길이를 찾고, 그 중 가장 긴 회문의 길이를 반환하였다. 이 과정에서 회문의 길이가 홀수, 짝수인 경우가 있는데, 홀수인 경우는 해당 index에서 일정값만큼 빼고 더해주며 회문을..

[백준] N과 M (자바/Java) 순열, 조합, 중복순열, 중복조합

N과 M은 순열, 조합, 중복순열, 중복조합을 연습할 수 있는 문제이다. 순열과 조합은 재귀를 사용하여 풀 수 있다. 1. 순열 순열에서 nPr은, N개의 수에서 가능한 r개의 수를, 순서대로 나열하는 것이다. 순열에는 순서가 존재하기 때문에 1 2 3과 3 2 1은 다른 경우로 취급한다. 이를 재귀와 dfs를 활용하여 풀면 다음과 같다. cnt는 dfs의 깊이를 의미한다. cnt가 M이 되면 M개의 순열이 완성되었다는 의미이므로 함수를 return 한다. 또한 순열은 중복을 허용하지 않기 때문에 순열에 포함되었는지 여부를 확인할 boolean check 배열이 필요하다. 배열의 처음부터 for문을 돌며 방문하지 않은 노드일 경우 check를 true로 바꾸고, 다시 깊이 cnt를 +1 한 다음, 재귀적..