고양이 퍼레이드

슈도 코드를 작성하면 다음과 같다. 더보기 str(정렬할 수) A(자릿수별로 구분해 저장할 배열) for(str 길이만큼 반복){ A 배열 저장 -> str.substring 사용 } for(i:0 ~ str길이만큼 반복){ for(j:i+1 ~ str 길이만큼 반복){ 현재 범위에서 max 값 찾기 } 현재 i의 값과 max 값 중 max 값이 더 크면 swap 수행 } A 배열 출력 구현 코드는 다음과 같다. import java.util.*; public class P_1427 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String str = sc.next(); int[] A = new int[str..

버블 정렬의 swap이 발생하지 않은 루프가 언제인지 알아내는 문제이다. 이 문제의 N의 최대 범위는 500000이기 때문에 버블 정렬도 문제를 해결할 경우 시간을 초과할 수 있다.(실제로 처음 문제를 풀었을 때 내가 그랬다;;;) 여기서 생각해봐야할 점은 안쪽 루프는 1 ~ n-i까지 swap을 수행한다는 것이다. 이는 특정 데이터가 안쪽 루프에서 swap의 왼쪽으로 이동할 수 있는 최대 거리는 1이므로, 데이터의 정렬 전 index와 정렬 후 index를 비교해 왼쪽으로 가장 많이 이동한 값을 찾으면 된다는 것이다. 슈도코드를 작성하면 다음과 같다. 더보기 N(데이터 개수), A(데이터 배열 -> 클래스를 데이터로 담는 배열) for (N만큼 반복) { A 배열 저장 ) A 배열 정렬 for (N만큼..

버블 정렬 파트에서 나온 내용이니 버블 정렬로 풀어보려 한다. N의 최대 범위가 1000으로 매우 작기 때문에 O(n^2)의 시간복잡도를 가진 버블 정렬로 문제를 해결할 수 있다. 먼저 슈도코드를 작성하면 다음과 같다. 더보기 N(정렬할 수의 개수) A(수를 저장할 배열) for (i: 0 ~ N-1) { for (j: 0 ~ N-i-1) { 현재 A배열의 값보다 1칸 오른쪽 배열의 값이 더 작으면 swap } } 코드로 구현하면 다음과 같다. import java.util.*; public class P_2750 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[]..

버블 정렬 두 인접한 데이터의 크기를 비교해 정렬하는 방법 루프를 돌면서 인접한 데이터 간의 swap 연산으로 정렬 시간복잡도 O(n^2) 정렬 과정 1) 비교 연산이 필요한 루프 범위를 설정 2) 인접한 데이터 값을 비교 3) swap 조건에 부합하면 swap 연산 수행 4) 루프 범위 끝날 때까지 2~3을 반복 5) 정렬 영역 설정, 다음 루프 실핼할 때 해당 영역 제외 6) 비교 대상이 없을 때까지 1~5를 반복 선택 정렬 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법시간복잡도 O(n^2) 시간복잡도 O(n^2) 정렬 과정 1) 남은 정렬 부분에서 최솟값 또는 최댓값을 찾음 2) 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap 3) 가장 앞..

트리(Tree) 노드와 엣지로 연결된 그래프의 특수한 형태 -> 그래프의 일종 순환구조(cycle)를 가지고 있지 않고, 1개의 루트 노드 존재 루트 노드 제외 모두 단하나의 부모 노드 존재 연결된 트리의 경우 임의의 두 노드를 연결하는 경로는 유일 트리도 그래프의 일종이기에 그래프로 풀이 가능 -> 인접리스트로 표현(dfs, bfs) 트리만을 위한 문제 -> 이진트리, 인덱스트리, LCA(최소공통조상) 이진트리(Binary Tree) 각 노드의 자식 노드 개수(=차수)가 2 이하로 구성된 트리 일차원배열로 표한하기 위해서는 무조건 이진트리 포화이진트리 : 리프 노드가 모두 차있는 상태 완전이진트리 : 마지막 레벨은 왼쪽부터 채워져 있는 상태 왼쪽 자식 노드 = 현재 index*2 오른쪽 자식 노드 = ..

stack을 구현하라는 문제인데 C++은 STL에서 stack이 구현되어있다. 그래서 그냥 구현되어있는 stack을 이용하겠다. 그전에 내용을 간단히 정리하자. 스택(stack)은 LIFO(Last In First Out)의 자료구조이다. 제일 마지막에 넣은 데이터가 처음으로 나오는 알고리즘으로 기본적으로 push와 pop 으로 동작한다. 이때 push는 stack의 최상단에 자료를 넣고, pop은 stack의 최상단 자료를 추출한다. stack STL을 사용하기 위해 #include 헤더파일을 포함해야 한다. 이후 " stack 스택명; " 으로 stack을 선언한다. 1. 데이터 추가 : 스택명.push(넣을 데이터) 형태로 데이터를 추가한다. stack.push(data); 2. 데이터 삭제 : 스..

코테 준비... 먼 훗날의 이야기라고 생각했었다 영원히 신입생일 거라 생각했지만 어느새 졸작을 준비하며 취업시장에 뛰어들 때가 왔다(나만 늙었어...) 그래서 코테준비를 위해 프로그래머스와 백준의 문제를 조금씩 풀기로 했다. 뭔가 재정비하는 시간이 온 것 같아 약간 설레기도~ 처음은 무난한 것부터! 정렬문제로 시작해보자. 이번 문제같은 경우에 대략 윤곽이 나왔지만 문제에서 vector를 이용했기 때문에 해당 문법에 관련된 오류가 많았다.(보면 프로그래머스는 배열은 대부분 vector로 던져주는 듯...) 여기서는 vector과 정렬에 대한 부분을 정리하면 될 것 같다. What is Vector? Vector란 C++ 표준 라이브러리(Standard Template Library)에 있는 컨테이너로 사용..

자료구조를 놓은 지 너무 오래되어서 가장 기본인 정렬 문제도 정리할 겸 이 문제를 풀었다. 문제에 대한 설명에서 시간 복잡도가 O(n²)인 정렬 알고리즘으로 풀 수 있고, 그 예로 삽입 정렬, 거품 정렬 등이 있다고 한다. 그래서 그냥 삽입 정렬로 풀어보기로 했다.(거품 정렬은 다음 포스팅에서 해보도록 하겠다) 그럼 우선 삽입 정렬에 대해 정리해보자. 삽입 정렬(insertion sort) 삽입 정렬이란 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입해 정렬을 완성하는 알고리즘이다. 구체적인 과정을 살펴보겠다. 삽입 정렬은 2번째 자료부터 시작하여 그 요소의 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자..

오늘도 이어서 간단한 알고리즘 문제를 풀어보려고 한다. 이전 내용과 동일하게 재귀함수 관련 문제이다. [문제 풀이] 일단 규칙성을 확인해봐야 할 것 같다. 가장 작은 도형부터 시작하자. 가운데 부분만 비어있고 나머지는 채워져 있음을 알 수 있다. 이를 한줄로 이어보자. 비어 있는 칸은 차례대로 (1, 1), (1, 4), (1, 7), (1, 10), (1, 13), (1, 16) ... 이다. 이는 j % 3 == 1 일 떄 빈칸이라는 말과 동일하다. 같은 방식이 아래쪽, i에도 적용되므로 i % 3 == 1 && j % 3 == 1 을 만족할 때 좌표는 비어있게 된다. 이제 이를 확장해 n=9일 때를 살펴보자. 비어 있는 공간은 기본 빈 공간에 더해 (3, 3), (3, 4), (3, 5) (3, 3..

최근 준비했던 일이 마무리되어 한달 정도의 시간적 여유를 가질 수 있게 되었다. 무엇을 할까 고민하다 최근 코딩 공부에 소홀했던터라 당분간은 빡세게(?) 전공 공부를 해볼까한다. 백준 알고리즘을 매일 풀어보려 하는데 특별한 목적이 있는게 아닌터라 그냥 내 마음가는대로 아무거나 선택해서 풀어볼 생각이다. 더불어 프로그래밍언어 중에서도 C++에 가장 소홀했기 때문에 백준 문제 풀이 겸 C++ 문법 정리 겸...(정말 거짓없이 C++ 문법 하나도 생각 안난다......;;;) 그래서 글이 개인적인 복습노트(?)가 될 터라 내용이 엉망진창이겠지만 누군가에게는 도움이 될 수도 있으니 글을 이어나가려 한다. [C++ 문법] C++의 표준 입력과 출력 : cin, cout //std 네임스페이스의 객체, 클래스 내 ..