beepbeep

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

문제 연결 리스트가 주어집니다. 연결 리스트의 처음부터 노드를 2개씩 고르고, 두 노드를 바꾸어줍니다. 모든 노드를 교환한 후 연결리스트를 반환합니다. 단, 노드의 값을 바꾸는게 아니라 노드 자체를 바꿔줘야 합니다. 아래는 예시입니다. 살펴보기 아직 연결 리스트에 익숙하지 않아서 그림을 그려보면서 차근차근 풀어보았다. 우선 더미 노드를 만들고, 더미 노드의 다음 노드에 주어진 노드를 연결한다. 물론 더미 노드의 값은 아무거나 상관없다. 그리고 더미 노드를 가리키는 포인터를 만들어준다. 변수명은 curr로 설정했다. ListNode dummy = new ListNode(0); dummy.next = head; ListNode curr = dummy; curr의 다음 노드와, 다음 다음 노드를 가리키는 포인..

문제 배열이 하나 주어집니다. 주어진 배열은 오름차순으로 정렬된 배열을, 특정 인덱스를 기점으로 회전시킨 배열입니다. * 회전 예시 : [0, 1, 2, 3, 4] -> 인덱스2를 기준으로 회전 -> [2, 3, 4, 0, 1] 주어진 값을 배열에서 찾고, 그 때의 인덱스를 반환하세요. 단, 작성한 코드의 시간 복잡도는 반드시 Big-O(logN)이어야 합니다. 살펴보기 주어진 조건( Big-O(logN) )을 만족하려면 선형탐색을 해선 안되고, 최악의 경우 BIg-O(logN)의 시간복잡도를 가지는 탐색법인 이분 탐색을 사용하는 것이 좋을 것 같다. 배열이 회전한 상태이므로 이분탐색에 약간 변형을 주어야 한다... 일단 시작은 기존의 이분탐색과 같다. 1. 배열에서 중간값을 고른다. 2. 중간값이 찾는..

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

문제 int 자료형 배열이 주어집니다. 배열에서 두 값을 꺼내서 용기를 만들어보려고 합니다. 이 때 두 값은 용기의 양쪽 높이가 되고, 두 값의 인덱스의 차이는 너비가 됩니다. 예를 들어 [1, 3, 7, 4, 5] 라는 배열이 있고 이 배열에서 3과 5를 꺼냈을 때, 상자의 한쪽 높이는 3, 반대쪽 높이는 5가 되고 상자의 너비는 두 값의 인덱스의 차이인 3(4 - 1)이 됩니다. 이렇게 만든 2차원 모양의 용기에 물을 담으려고 합니다. 가장 많은 양의 물을 담을 수 있는 용기를 찾아서, 그 용기에 담을 수 있는 물의 양을 계산하세요. 살펴보기 생각을 정리하다보니 내용이 길어졌는데... 요약하면 다음과 같다. 문제 핵심) 1. 인덱스를 가운데로 옮길 때마다 용기의 너비가 줄어든다. 즉, 담을 수 있는 ..

한때 sns에서 유행했던 일명 콜라 문제를 풀어낼 수 있는 코드를 작성하는 문제이다. n = 현재 가지고 있는 빈 병의 개수 a = 새 음료와 교환할 때 필요한 할 빈 병의 개수 b = 빈 병 a개와 교환할 수 있는 새 음료의 개수 처음에 푼 방법 int answer = 0; int remain = 0; while(n >= a){ if(n % a != 0) { remain += n % a; } n = n / a * b; answer += n; if(remain >= a || a > n){ n += remain; remain = 0; } } return answer; 처음에 작성한 내용인데... 요구사항을 해결하긴 했지만 불필요한 부분이 많이 들어있다. 나머지 변수를 만든다던지, n의 나머지가 있을 때 나..

기본적인 방법 // number : 주어진 숫자 // count : 약수의 개수 int count = 0; for(int i=1; i

원래 큐는 선입선출법을 따르는 자료구조로, 먼저 넣은 자료가 먼저 처리된다. 그러나 우선순위 큐는 선입선출법을 따르지 않는다. 우선순위 큐의 모든 원소에는 특정한 기준에 따라 우선순위가 부여된다. 우선순위 큐에서는 원소를 넣은 순서와 상관 없이, 이 우선순위에 따라서 원소가 처리된다. 우선순위가 같은 원소가 있을 때에만 원소를 넣은 순서를 확인하고, 먼저 넣은 원소가 처리된다. 즉 우선순위 큐는 자료를 넣은 순서와 상관 없이 우선순위가 높은 자료가 먼저 삭제되는 자료구조이다. 자바에서 우선순위 큐를 선언하려면 PriorityQueue 클래스를 이용해야 한다. 기본적으로 숫자의 크기를 기준으로 우선순위가 부여된다. 숫자의 크기가 작을수록 높은 우선 순위를 가지게 된다. PriorityQueue priori..

문제 주어진 연결 리스트가 회문 구조인지 확인하는 문제이다. 살펴보기 문제를 보고 가장 먼저 생각난 방법은 리스트를 이용하는 방법이었다. 리스트를 만들어 노드값을 전부 저장한 후, 반복문을 이용해 리스트의 양끝에서부터 가운데로 순회하면서 양쪽의 값을 비교해 회문인지 확인하는 방법이다. 그래서 우선 리스트를 이용해 문제를 푼 다음, 206번 문제를 풀 때 배운대로 뒤집힌 연결 리스트를 만든 후 원본 연결 리스트랑 비교하는 방식으로 풀어보았다. 의도했던 대로 문제를 풀긴 했지만.. 더 좋은 풀이가 있는걸 알게 되어서 풀이를 참고해 한번 더 풀어보았다. 우선 두 개의 포인터를 이용해, 연결 리스트의 중간 지점을 찾아야 한다. 160번 문제에서 했던 것처럼 한 포인터(slow)는 한 번에 한칸씩만 이동하고, 다..

문제 주어진 이진트리를 반대로 뒤집는 문제이다. 살펴보기 재귀호출을 이용한 방법과, 큐를 이용한 방법이 있었다. 1. 재귀호출을 이용한 방법 서브트리로 내려간다. 내려가면서 임시 노드를 만들어 오른쪽 자식 노드를 저장하고, 왼쪽 자식 노드와 스왑한다. 이 때, 해당 노드만 스왑되는게 아니라 노드와 연결된 서브 트리까지 스왑된다! 스왑이 끝나면 다음 서브트리로 내려가서 반복한다. 2. 큐와 반복문을 이용한 방법 먼저 큐에 루트 노드를 넣는다. 반복문을 통해 큐에서 노드를 하나씩 빼면서, 즉 노드에 방문하면서 왼쪽 자식 노드와 오른쪽 자식 노드를 스왑한다. 스왑이 끝나면 다시 큐에 노드를 넣어 연결하는 방법이다. 큐에서 노드를 꺼낼 때마다 한 레벨씩 아래로 이동하게 된다. 더 이상 내려갈 레벨이 없으면, 반..