코딩테스트 공부

문제 설명 https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 처음 주사위는 지도 위에 윗면이 1, 아래는 6 처음 이동 방향은 동쪽 조건 점수 계산 문제에 대한 아이디어 이 문제를 해결하기 위해서는 필요한 메소드를 생각해야 할 필요가 있습니다. 주사위 움직이는 메소드 위치를 움직이는 메소드 방향을 정하는 메소드 점수를 계산하는 메소드 주사위를 움직이는 메소드 public static void moveDice(int dir) { ..

https://www.acmicpc.net/problem/17232 17232번: 생명 게임 첫줄에는 바둑판의 세로길이, 가로길이를 나타내는 두 정수 N과 M, 준표가 바둑판을 관찰하고자 하는 시간 T가 주어진다. 두번째 줄에는 주위의 기준이 되는 정수 K, 각 칸의 다음 상황을 결정하 www.acmicpc.net 문제 설명 바둑판 안에서 계속 움직이는 생명에 위치를 알아내는 게임입니다. 이 때 각칸은 주위의 영향을 받습니다. 여기서 말한 주위는 색칠한 영역과 같이 현재 칸을 중심으로 둔 한 변의 길이가 (2K+1)인 정사각형 입니다. (단, 현재 칸 제외) 생존 : 만약 현재 칸에 생명이 있고, 주위에 a개 이상 b개 이하의 생명이 있다면 현재 칸의 생명은 다음 단계에 살아남는다. 고독 : 만약 현재 ..

유명한 정렬 알고리즘 시간복잡도 N^2 알고리즘 Bubble Sort (버블 정렬) 버블 정렬은 배열의 인접한 요소를 비교하고, 필요한 경우 위치를 바꾸는 방식으로 정렬을 수행합니다. 이 과정은 배열의 모든 요소가 올바르게 정렬될 때까지 반복됩니다. Selection Sort (선택 정렬) 선택 정렬은 배열을 반복적으로 탐색하여 가장 작은(또는 가장 큰) 요소를 찾아, 정렬되지 않은 부분의 첫 번째 위치와 교환하는 방식으로 작동합니다. 이 과정은 배열의 모든 요소가 정렬될 때까지 반복됩니다. 선택 정렬은 버블 정렬보다 일반적으로 더 효율적이지만, 큰 데이터 세트에 대해서는 여전히 비효율적입니다. Insertion Sort (삽입 정렬) 삽입 정렬은 배열의 각 요소를 이미 정렬된 부분에 적절한 위치에 삽입..

https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순 www.acmicpc.net 문제 설명 괄호를 적절하게 추가하여 결과의 최댓값을 출력합니다. 8*3+5를 보면 (8*3)+5, 8*(3+5) 이렇게 2가지 경우가 있습니다. 이때 최댓값은 8*(3+5) = 64입니다. 문제에 대한 아이디어 이 문제는 연산자의 우선순위는 존재하지 않습니다. 그러므로 앞에서부터 계산을 하면 됩니다. 문제는 괄호를 어디에 넣어야 할지 선택을 해야 합니다. 괄호는 한 개만 들어갈 수도 ..

https://school.programmers.co.kr/learn/courses/30/lessons/133500# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 한 줄로 축약해서 어느 등대에 촛불을 켜야 모든 뱃길에 불을 밝힐 수 있는지 찾는 프로그램을 만드는 것입니다. 1에 키면 2,3,4에 다 불을 킬 수 있고 5에 키면 6,7,8에 불을 킬 수 있어 결국 모든 곳에 불을 킬 수 있습니다. 문제에 대한 아이디어 이 문제를 보면 n개인 노드에서 간선이 n-1개이고 모든 등대까지 갈 수 있는 길이 모두 주어진다 했으므로 모든 노드가 연결되어..

https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제설명 이 문제는 현재 자신의 오른쪽에서 가장 크지만 제일 왼쪽에 있는 숫자를 찾으면 됩니다. 예를 들어 3은 오큰수가 5이고 5는 오큰수가 2는 자신보다 작기 때문에 아니고 7이 됩니다. 문제에 대한 아이디어 이 문제를 제일 처음보고 느낀점은 뒤에서 부터 오면서 stack에 숫자를 집어 넣고 현재 자신의 수보다 작은 stack 안의 수는 빼주면 되지 않을까? 였습니다. 예를 들어 3 5 2 6 7이 있다..

https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 문제설명 0인 곳에서 돌아다니면서 책을 알맞은 위치까지 가져가야 합니다. 위 예제를 풀어보면 {-39, -37}, {-29, -28}, {-6}, {2, 11}로 총 22 + 12 + 58 + 39 = 131입니다. 문제에 대한 아이디어 처음에는 0에서 가까운 부분 부터 배달을 해야 하지 않을까?라는 고민을 했습니다. 하지만 경우의 수가 너무 많아져 복잡해집니다. 그래서 먼 곳부터 배달을 하는 방법을 ..

https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 문제 설명 괄호가 예제 처럼 주어질 때, () 이렇게 바로 열고 닫힌 것은 레이저 ( .... ) 인 괄호는 막대기 입니다. 이 레이저가 막대기를 총 몇번 부스는지 찾아내는 프로그램을 구현하면 됩니다. 문제에 대한 아이디어 제일 처음 생각한 아이디어는 레이저를 만나면 레이저를 ArrayList에 저장을 합니다. Stack에는 괄호를 '(' 집어넣고 ')' 이것을 만났을 때 레이저인지 판별해주고 레이저가 아니..