본문 바로가기
반응형

PS 문제 풀이/Baekjoon446

[BOJ] 백준 1427 소트인사이드 출처: https://www.acmicpc.net/problem/1427 Input 2143 Output 4321 자릿수를 정렬하는 것이므로 『0』 ~ 『9』에 해당하는 숫자를 정렬합니다. 버블정렬 이용 내림차순이므로 배열의 끝자리부터 정렬의 낮은 숫자가 배치되는 형태입니다. 버블 정렬(Bubble Sort) 특징 - O(N2) - 서로 인접한 두 원소를 비교하여 정렬 - 한 번의 탐색으로 가장 큰 원소가 맨 뒤에 위치하게 됩니다. (오름차순 기준) 시뮬레이션 구현 코드 (오름차순 기준) #include int swap(int* a, int* b zoosso.tistory.com import java.util.Arrays; import java.util.Scanner; public class Main {.. 2021. 2. 24.
[BOJ] 백준 2667 단지 번호 붙이기 출처: https://www.acmicpc.net/problem/2667 Input 7 0110100 0110101 1110101 0000111 0100000 0111110 0111000 Output 3 7 8 9 총 3개의 단지가 존재하며, 각 단지의 집의 수는 7, 8, 9개 입니다. BFS 알고리즘을 이용해 배열을 순회하며 연결된 집을 처리. import java.util.Collections; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.Stack; class House{ int x,y; int number; public House(int x, int y, int numb.. 2021. 2. 24.
[BOJ] 백준 1652 누울 자리를 찾아라 출처: https://www.acmicpc.net/problem/1652 Input 5 ....X ..XX. ..... .XX.. X.... Output 5 4 배열을 순회하며 양 끝 중에 벽이나 짐이 놓여있는지 확인 - 가로로 누울 수 있는 공간 5개 - 세로로 누울 수 있는 공간 4개 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = Integer.parseInt(sc.next()); String[] arr = new String[N]; for(int i=0; i 2021. 2. 24.
[BOJ] 백준 1205 등수 구하기 출처: https://www.acmicpc.net/problem/1205 Input 3 90 10 100 100 90 Output 3 N : 랭킹 리스트에 올라와 있는 점수 개수( 0 2021. 2. 24.
[BOJ] 백준 9012 괄호 출처: https://www.acmicpc.net/problem/9012 Input 6 (())()) (((()())() (()())((())) ((()()(()))(((())))() ()()()()(()()())() (()((())()( Output NO NO YES NO YES NO 1) 여는 괄호인 경우 → push 2) 닫는 괄호인 경우 → pop해서 여는 괄호인지 확인 3) 주어진 괄호 문자열을 모두 처리한 후 → 스택에 남아 있는 원소 확인 import java.util.Scanner; class Stack{ int top; int[] stack; public Stack(int size) { top = -1; stack = new int[size]; } public void push(int x.. 2021. 2. 24.
[BOJ] 백준 1193 분수찾기 출처: https://www.acmicpc.net/problem/1193 Input 14 Output 2/4 배열에 지그재그로 분수가 주어집니다. X가 주어질 때, X번째 분수를 구하는 문제입니다. * 10,000,000 숫자를 입력받기 위해 long타입 처리 구현 지그재그 순서는 다음과 같습니다. 대각선 한 줄에 위치한 칸의 개수는 등차수열 형태를 가집니다. ▷ 1 + 2 + 3 + 4 + 5 + ... + (n-1) + n [등차수열 공식] 등차 수열 공식을 이용해 x는 몇 번째 대각선에 위치한지 알 수 있습니다. 14 → 5 Line 15 → 5 Line 16 → 6 Line 21 → 6 Line 22 → 7 Line 28 → 7 Line 29 → 8 Line n-th Line이 홀수일 때, → 분.. 2021. 2. 24.
[BOJ] 백준 1021 회전하는 큐 출처: https://www.acmicpc.net/problem/1021 Input 10 3 2 9 5 Output 8 덱 = { 1 2 3 4 5 6 7 8 9 10 }이 주어져있고 『2』, 『9』, 『5』를 뽑고자 합니다. ②번 연산 1번 수행 후 『2』를 뽑습니다. → 덱 = { 3 4 5 6 7 8 9 10 1 } ③번 연산 3번 수행 후 『9』를 뽑습니다. → 덱 = { 10 1 3 4 5 6 7 8 } ③번 연산 4번 수행 후 『5』를 뽑습니다. → 덱 = { 6 7 8 10 1 3 4 } ▶ ②, ③ 연산이 총 8번 수행. [구현] 원형 큐를 이용하거나 덱(Dequeue)을 이용. → ①번 연산은 덱에서 front 부분 삭제 → ②, ③번은 한쪽에서 pop()한 다음, 다른 쪽에 push().. 2021. 2. 24.
[BOJ] 백준 5430 AC 출처: https://www.acmicpc.net/problem/5430 Input 4 RDD 4 [1,2,3,4] DD 1 [42] RRD 6 [1,1,2,3,5,8] D 0 [] Output [2,1] error [1,2,3,5,8] error 덱(Dequeue) 활용 이 문제의 경우 덱을 구현하여 원소 순서를 뒤집을 때 실제 배열의 원소를 뒤집으면 시간제한에 걸립니다. 따라서, R(뒤집기) 함수의 경우 원소의 순서는 유지하되 바라보는 방향을 반대쪽으로 해서 처리합니다. → D(버리기) 함수일 때, 앞단(front)에서 제거할지, 뒷단(rear)에서 제거할지 결정 * 배열이 비어있는 상태에서 R(뒤집기) 하는 것은 『error』가 아닙니다. Input 1 R 0 [] Output [] * 매 Test.. 2021. 2. 24.
[BOJ] 백준 2579 계단 오르기 출처: https://www.acmicpc.net/problem/2579 Input 6 10 20 15 25 10 20 Output 75 ▶ 동적계획법(Dynamic Programming, DP) 동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 zoosso.tistory.com 계단은 아래와 같습니다. ▶ 10 + 20 + 25 + 20 = 75 게임 진행 방식 ① 계단은 한 번에 1계단씩 또는 2계단씩 오를 수 있다. ex) 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라갈 수 없다. .. 2021. 2. 24.
[BOJ] 백준 1463 1로 만들기 출처: https://www.acmicpc.net/problem/1463 Input 10 Output 3 ▶ 10 → 9 → 3 → 1 로 연산 3번 사용 [구현] dp[i] = 숫자 i에 연산 횟수 최소 비용 = 1 + Min(dp[i / 3] + dp[i / 2] + dp[i-1]) [x = 1] → result = 0 [x = 2] 2 / 2 = 1 2 - 1 = 1 → result = 1 [x = 3] 3 / 3 = 1 3 - 1 = 2 / 2= 1 = 2 - 1 = 1 → result = 1 [x = 4] 4 - 1 = 3/ 3 = 2 4 / 2 = 2 / 2 = 1 = 2 - 1 = 1 → result = 2 [x = 9] ※9는 2로 나누어 떨어지지 않습니다. dp[9] = 1 + Min(d.. 2021. 2. 23.
반응형

티스토리툴바