전체 글
이진 트리의 순회
2022.09.01종류 중위 순회 (in-order): 왼쪽 자식노드(L), 내 노드(P), 오른쪽 자식노드(R) 순서로 방문한다. 전위 순회 (pre-order): 내 노드(P), 왼쪽 자식노드(L), 오른쪽 자식노드(R) 순서로 방문한다. 후위 순회 (post-order) : 왼쪽 자식노드(L), 오른쪽 자식노드(R), 내 노드(P) 순서로 방문한다. 문제 루트가 0인 이진트리가 주어질 때, 이를 전위순회, 중위순회, 후위순회한 결과를 각각 출력하는 프로그램을 작성하시오. 입력 첫 번째 줄에 트리의 노드 개수 n이 주어진다. ( 1 ≤ n ≤ 100 ) 두 번째 줄부터 트리의 정보가 주어진다. 각 줄은 3개의 숫자 a, b, c로 이루어지며, 그 의미는 노드 a의 왼쪽 자식노드가 b, 오른쪽 자식노드가 c라는 뜻이다...
이진 트리 (Binary Tree)
2022.08.25구조 이진 트리(二進-, 영어: binary tree)는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조이다. 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다. 특징 트리 구조의 가장 큰 특징으로는 재귀적 성질을 갖는다는 것이다. 위 이미지에서 루트 노드인 노드 2의 왼쪽 자식 노드는 노드 7을 루트로 갖는 또 하나의 트리가 된다. 이렇게 만들어진 트리는 부트리(sub tree)라고 부른다. 용어 왼쪽 자식 노드(left child node)는 왼쪽 부트리의 노드이다. 오른쪽 자식 노드(right child node)는 오른쪽 부트리의 노드이다. 부모 노드(parent node)는 그 노드를 자식으로 하는 노드이다. 형제 노드(sibling node)는 부모가 같은 두 노드..
마시멜로 분배
2022.08.18문제 알고리즘 에듀 학생들은 코치가 나눠주는 마시멜로를 받기 위해 반별로 학생들이 줄을 서 있다. 알고리즘 에듀는 Q개의 반으로 운영되고 있으며, 각각의 반에 해당하는 학생수는 N_i명이다. 학생들은 본인이 원하는 만큼의 마시멜로를 얻으면 행복해지고 줄을 빠져나간다. 각 줄의 맨 앞에 있는 학생에게만 마시멜로를 줄 수 있으며, 마시멜로를 받은 학생이 빠져나가면 다음 학생이 앞으로 올 수 있다. K명의 학생들을 행복하게 만들기 위해 필요한 최소 마시멜로의 숫자를 구하는 프로그램을 작성하시오 . 입력 첫 줄에는 반의 수 Q(1
.gitignore를 전역으로 설정하기
2022.08.11대다수의 프로젝트는 .gitignore 파일을 이용하여 Git 저장소에서 제외할 파일을 정의합니다. 만약 프로젝트에 참여하는 개발자들이 서로 다른 IDE를 사용한다면 IDE의 임시 파일을 제외할 패턴을 .gitignore 파일에 추가해야 할까요? 이 글에서는 이렇게 모호한 상황에 대한 해답을 제시합니다. Git 설정 Git은 다양한 설정을 제공합니다. 예를 들면 Git Log에 남길 이름과 이메일 주소 등도 Git의 설정으로 저장되어 있습니다. 어떤 설정이 지정되어 있는지 확인하려면 터미널에 아래 명령어를 입력합니다. $ git config --global --list Git 설정과 관련된 더 자세한 설명은 공식 문서를 참조하세요. core.excludesFile 만약 IDE 임시 파일과 같이 프로그램 ..
전염병
2022.08.04문제 철수네 마을에는 갑자기 전염병이 유행하기 시작하였다. 이 전염병은 전염이 매우 강해서, 이웃한 마을끼리는 전염되는 것을 피할 수 없다. 철수네 마을은 1번부터 N번까지 번호가 매겨져 있다. 철수네 마을의 구조는 꽤나 복잡한데, i번 마을에서 출발하면 i * 2 번 마을에 갈 수 있고, 또한 i / 3(i를 3으로 나눈 몫) 번째 마을에도 갈 수 있다. 전염병은 사람에 의하여 옮는 것으로 알려져 있다. 따라서 i번 마을에 전염병이 돌게 되면, i * 2 번 마을과 i / 3(i를 3으로 나눈 몫) 번 마을 역시 전염병이 돌게 된다. K번 마을이 가장 처음으로 전염병이 돌기 시작했을 때, 전염병이 돌지 않는 마을의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 전체 마을의 개수 N과, 처음으로 ..
원형 큐 (Circular Queue)
2022.07.28구조 원형 큐(Circular Queue)는 보통의 큐의 확장시켜 마지막 요소가 첫 요소에 연결된 형태이다. 원형 큐는 보통의 큐의 가장 큰 제약 사항을 해결한다. 보통의 큐에서는 push 후 pop을 하면 사용이 불가능한 빈 공간이 생기지만, 원형 큐에서는 큐의 끝에 다다르면 다시 큐의 시작부터 데이터를 삽입한다. 구현 코드 import java.util.Scanner; public class Main { static class Queue { private int front = 0; private int rear = 0; private int size = 0; private int[] arr = new int[100]; public Queue(int size) { this.create(size); } ..
[MyBatis] java.sql.SQLException: 부적합한 열 인덱스
2022.07.14MyBatis로 개발하던 중 얻었던 '부적합한 열 인덱스'(Invalid column index) 오류에 대해 정리해본다. TL;DR 변수에 대한 Getter, Setter가 올바르게 생성되었는지 확인 문자열이라고 따옴표를 사용했던 것은 아닌지 확인 주석에 변수를 포함한 것은 아닌지 확인 Getter, Setter Java Bean으로부터 데이터를 가져오거나 반환할 때에는 Getter와 Setter를 이용합니다. MyBatis가 호출할 Getter 메소드와 Setter 메소드가 존재하는지 확인합니다. 따옴표 보통 SQL에서 문자열을 다룰 때에는 작은 따옴표를 사용합니다. 혹시라도 나도 모르게 아래와 같이 SQL을 작성한 것은 아닌지 확인합니다. SELECT '${userId}' AS USER_ID FRO..
큐 (Queue)
2022.06.23구조 큐(queue)는 컴퓨터 과학 분야에서 쓰이는 컴퓨터의 기본적인 자료 구조의 한가지다. 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 되어 있다. 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다. 자료를 넣는 것을 푸쉬(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 스택과 달리 가장 먼저 푸쉬한 자료부터 나오게 된다. 구현 코드 import java.util.Scanner; public class Main { static class Queue { private int front = 0; private int rear = 0; private int size = 0; private int[..
괄호의 값 [백준 2504번]
2022.06.16문제 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다. 예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다. ‘()’ 인 괄호열의 값은 2이다. ‘[]’ 인 괄호열의 값은 3이다. ‘(X)’ 의 괄호값은 2×값..
괄호 [백준 9012번]
2022.06.09문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 여러분은 입력으로 주어진 괄호 문자열..
접시
2022.06.02문제 접시 a, b, c, d 가 있고, 알파벳 순으로 한쪽이 막혀 있는 세척기에 들어간다고 할 때, b a c d 순으로 꺼내기 위해서는 push, push, pop, pop, push, pop, push, pop을 하면 된다. 세척기에서 꺼내는 순서가 주어질 때 그 동작을 출력하는 프로그램을 작성하시오. 만약 주어진 순서대로 접시를 꺼낼 수 없다면 “impossible”을 출력한다. 입력 첫째 줄에 소문자 알파벳이 주어진다. 중복된 소문자 알파벳은 입력되지 않는다. 알파벳 소문자는 26개이다. 입력되는 알파벳의 길이는 최대 26 자리이다. 출력 접시를 꺼내는 것이 가능한 경우 push, pop의 순서를 출력한다. 이것이 불가능하다면 impossible을 출력한다. 입력 예시 1 bacd 출력 예시 1..
스택 (Stack)
2022.05.26구조 스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다. 끝먼저내기 목록(Pushdown list)이라고도 한다. 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다. 자료를 넣는 것을 '밀어넣는다' 하여 푸쉬(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 푸쉬한 자료부터 나오게 된다. 이처럼 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다. 이를테면, a부터 b와 c를 순서대로 넣은 다음 자료를 하나씩 꺼내면 c부터 b와 a의 순서로 나오게 된다. 구현 코드 import java.util.*; p..