본문 바로가기

알고리즘

[프로그래머스] 12946 하노이탑 java 풀이 1. 문제 설명문제 링크하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.한 번에 하나의 원판만 옮길 수 있습니다.큰 원판이 작은 원판 위에 있어서는 안됩니다.하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원.. 더보기
겁나 쉽게 설명한 [프로그래머스] 12903. 3xn 타일링 java 1. 문제 설명문제 링크문제 설명가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 3이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다타일을 가로로 배치 하는 경우타일을 세로로 배치 하는 경우예를들어서 n이 8인 직사각형은 다음과 같이 채울 수 있습니다.직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.제한사항가로의 길이 n은 5,000이하의 자연수 입니다.경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.입출력 예nresult411입.. 더보기
[Programmers] 12977 소수 만들기 Java 1. 문제 설명[문제 링크](https://school.programmers.co.kr/learn/courses/30/lessons/12977?language=java)주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.제한사항nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.입출력 예numsresult[1,2,3,4]1[1,2,7,6,4]4입출력 예 설명입출력 예 #1 .. 더보기
[코드 트리] 배열 회전 2 Java 1. 문제 설명문제 링크2. 풀이 설명idx, idy를 활용해서 배열을 이동시킬 수 있는가에 대한 문제이다.하지만 한 가지 생각해야할 부분은 배열을 이동시킬 때, 중앙에서 가로 갈수록 건너 뛰어야하는 행렬의 GAP이 1씩 커진다는 점이다.이 점만 주의하면 된다.배열 이동 시키는 법은 다음과 같다.초기값을 temp라는 변수에 넣고, 배열을 한 칸씩 이동하여 돌리고, 맨 마지막 행렬 위치에 아까 temp에 넣었던 값을 삽입하면 된다.2번의 이동마다 90도씩 꺾으면 되므로, 반복문을 이용해 idx,idy의 값을 변경해줬다. idx, idy가 무엇인지 모르겠다면, 배열의 방향 전환에 대해서 검색해보고 공부하길 바란다. 더보기
JAVA 2차원 배열 (matrix) 회전 공식 완벽 정리! 1. 시계방향으로 90도 회전Before(R,C) 는 원래 행렬에서의 원소의 위치를 말하는 것이고, After()는 바뀐 행렬에서 동일한 원소의 위치를 말하는 것이다.예를 들어, 원소 '9'는 (1,3) 이다. 따라서 바뀐 행렬에서는 공식대로하면 (3,3) 이다. 실제로도 그렇다.2. 반 시계 방향으로 90도 회전 3. 배열 시계 방향 혹은 반 시계 방향으로 원소를 한 칸씩 이동idx, idy를 이용하여, 한 칸씩 이동.최초의 값을 temp라는 변수에 저장한다.idx,idy를 이용하여, 배열의 끝부분에서는 뱡향 전환을 하며, 동서남북으로 원소를 한 칸씩 옮긴다.마지막 원소는 최초의 값에 인접한 원소이다. 여기에는 temp의 값을 집어넣는다. 더보기
시간 복잡도의 개념과 코딩 테스트에서의 활용법 1. 시간 복잡도 란?(1) 개념시간 복잡도는 주어진 문제를 해결하는데 필요한 연산 횟수를 말한다.(2) 표기 방법의 종류시간 복잡도를 표기하는 방법에는 다음의 3 가지가 있다.이름설명빅-오메가 표기법문제를 풀기 위해 주어진 상황이 최선의 상황일 때 필요한 연산 횟수를 나타내는 표기법빅-세타 표기법문제를 풀기 위해 주어진 상황이 보통의 상황일 때 필요한 연산 횟수를 나타내는 표기법빅-오 표기법문제를 풀기 위해 주어진 상황이 최악의 상황일 때 필요한 연산 횟수를 나타내는 표기법예를 들어 설명1~100의 숫자가 랜덤한 순서로 저장된 배열이 주어졌을 때, 해당 배열에서 56의 INDEX를 찾아서 출력하라 라는 문제를 풀어야 한다고 하자.이때 내가 선택한 방법은 배열의 첫 번째 인덱스부터 일일히 조회이다.빅-오.. 더보기
💚 백준 1940 주몽 1. 문제 분석문제 링크N개의 수 중 2개를 뽑아서 그게 M과 맞는지 계산하면 된다고 생각했다.그래서 조합을 사용했다. N이 15000개까지 주어진다. 15000C2 = 112492500 이다.주어진 시간이 2초임으로 20억 번의 계산이 가능한 상황에서 11억의 계산은 Safe다. 따라서 단순 조합을 해도 문제는 풀린다. (시간이 오래 걸렸지만...)나는 DO IT! 알고리즘 코딩테스트 책에서 소개한 투 포인터로도 문제를 풀어 보았다. 투 포인터를 쓰면 정렬 후 최대 N+1 번의 연산이 필요해서 총 N+1 +NlogN = O(NlogN) 의 시간이 든다.이걸 N의 최대 값인 15000으로 계산해보면, 15000 * log(15000) = 62641 개의 연산만 하면 되어서 훨씬 빠르다.두 방법 다 소개해.. 더보기
💜 백준 2108 통계학 JAVA 1. 문제 설명[문제 링크](https://www.acmicpc.net/problem/2108)산술 평균, 중앙값, 최빈값, 범위를 구하면 된다. 2. 푸는 원리 산술 평균 -> 총합 / 머릿수 중앙값: 중앙에 있는 녀석 계산 최빈값: TreeMap을 사용 Key = 입력 받은 값, value = 해당 값이 나온 횟수, TreeMap은 순서가 보장됨으로, 입력을 한번 정렬한 후에 TreeMap에 넣으면 된다. 범위 : 최대값 - 최소값 3. 코드 분석import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.TreeMap;/* * .. 더보기

티스토리툴바