beepbeep

문제 2차원 배열이 주어집니다. 주어진 2차원 배열을 시계방향으로 90도 회전시키세요. 단, 2차원 배열을 새로 만들지 않고 주어진 2차원 배열만 이용해서 회전시켜야 합니다. 살펴보기 2단계로 나누어서 풀 수 있습니다. 1단계 가상의 우하향 대각선을 배열에 그려주고, 대각선을 기준으로 양쪽 값을 바꿔줍니다. 2단계 배열의 가운데 열을 기준으로, 좌우 대칭되는 지점의 값을 바꿔줍니다. 시계방향으로 90도 돌아간 모습의 2차원 배열이 완성되었습니다. 이 과정을 코드로 옮겨주면 끝! 풀어보기 for(int i=0; i

알고리즘 문제를 풀던 중 다음 순열을 구하는 문제가 나왔습니다. 그래서 관련 내용을 공부한 후, 정리해 보았습니다. 다음 순열(Next Permutation)이란? 일단 다음 순열을 구하기 위해선, 다음 순열이 무엇인지부터 살펴보아야 할 것 같습니다. 1, 2, 3 예를 들어서 1부터 3까지 적힌 카드가 주어지고, 이 카드를 나열해서 백의 자리 수를 만들어본다고 하면 세 카드를 이용해서 만들어낼 수 있는 백의 자리 수 중 가장 작은 숫자는 123입니다. 그 다음으로 작은 숫자는 132이고, 또 그 다음번 숫자는 213이 됩니다. 만들어낼 수 있는 백의 자리 수를 전부 찾아 오름차순으로 나열하면 다음과 같습니다. 123 132 213 231 312 321 만들어진 백의 자리 숫자를 다시 세 개의 카드로 분..

문제 살펴보기 숫자가 들어있는 배열이 주어진다. 이 배열에 있는 모든 숫자는 2개씩 들어있으며, 딱 한 숫자만 1개 들어있다. 1개만 있는 숫자를 찾아서 반환해야 한다. 단, 숫자를 찾는 코드의 시간 복잡도는 0(n) (= linear runtime complexity) 이어야 하고, 공간 복잡도는 0(1) (=constant extra space) 이어야 한다. 생각의 흐름 단일 반복문과 비트 연산을 활용하면 주어진 요구사항을 지킬 수 있다... 비트 연산자 중 XOR을 사용하면 되고, XOR의 규칙을 이용하면 된다. x ^ 0 = x x ^ y = 0 또한 XOR은 교환법칙이 성립한다. 따라서 다음과 같이 풀 수 있다. x ^ y ^ x = x ^ x ^ y = y 풀어보기 int num = 0; f..

문제 살펴보기 int 자료형 배열이 주어진다. 배열의 인덱스는 일차에 해당하고, 각 숫자는 해당 일차의 주식 매매가를 의미한다. 예를 들어 [3, 5, 9]와 같은 배열이 주어진 경우 다음과 같은 의미를 가진다. 인덱스 0, 숫자 3 -> 0일차, 주식 가격 3 인덱스 1, 숫자 5 -> 1일차, 주식 가격 5 인덱스 2, 숫자 9 -> 2일차, 주식 가격 9 주어진 배열을 바탕으로, 주식을 구매하고 다시 팔아서 수익을 남기려고 한다. 최대 얼마의 수익을 낼 수 있을까? 생각의 흐름 1. 구매하는 일자(인덱스)는 판매하는 일자(인덱스)보다 빨라야 한다. 2. 이중 반복문을 사용할 경우 계산 시간이 너무 길어져 시간 초과가 된다. 이 문제의 핵심! 2번 이유로 인해 이중 반복문을 사용할 수 없다. 최저값과..

문제 살펴보기 주어진 int 자료형 배열을 이용해 이진 탐색 트리(Binary Search Tree)를 만드는 문제이다. * 이진 탐색 트리 : 왼쪽 자식 노드는 부모 노드보다 작은 값을, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가진 트리 구조를 의미한다. 생각해보기 만약 주어진 배열이 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이라면? 위와 같은 모습의 이진 트리가 만들어져야 한다. (*점선은 빈 노드를 의미합니다) 그러기 위해서는 우선, 배열에서 부모 노드에 저장할 값을 꺼낸다. 그러고 나서 해당 값을 기준으로 2개의 묶음으로 나눈다. [0, 1, 2, 3, 4] 5 [6, 7, 8, 9, 10] 트리의 다음 단계로 넘어간다. 각 묶음에서 다시 부모 노드에 저장할 값을 꺼내고,..