막내의 막무가내 프로그래밍 & 일상

www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 브루트포스 분류별 풀기에 있는 백준 1759 암호 만들기를 풀어봤습니다. ㅎㅎ 정렬순 + 모음1개 이상 자음 2개이상인지 체크 해서 완전탐색하여 풀었습니다. 브루트포스 분류라 비효울적이여도 통과한 것 같습니다. 풀이는 다음과 같습니다. [Java] import java.util.Arrays; import java.util.Scanner; class Main { private static String[] arr; pr..

www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net import java.util.Scanner; class Main { static int[][] arr; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); for (int i = 0; i < n; i++) { int num = sc.nextInt(); if (num == 0) { System.out.println("1 0"); continue; } if (num == 1) { Sy..

www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 주석에 풀이를 적어놓았습니다. [Java] import java.util.Arrays; import java.util.Scanner; class Main { static int[] nums; static int[] arr; static boolean[] isVisited; static int N; static int M; static StringBuilder sb = new StringBuilder()..

www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 분류별풀기에서 백트랙킹을 보다 N과 M 시리즈가 더있길래 풀어봤습니다. 순서대로 출력해야하므로 정렬하고 백트랙킹 써주면 됩니다. 풀이는 다음과 같습니다. [Java] import java.util.Arrays; import java.util.Scanner; class Main { static int[] nums; static int[] arr; static boolean[] isVisited; stat..

www.acmicpc.net/submit/2805 로그인 www.acmicpc.net 이전 단계인 랜선자르기 문제를 풀었으면 조건만 조금 변경하면 쉽게 풀 수 있는 문제입니다. 문제는 Scanner 를 사용했을때 계속 메모리 초과가 나서 Buffered로 바꿔줬더니 해결되었습니다. 풀이는 주석에 정리했습니다. [Java] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; class Main { public static void main(String[] args) throws IOExce..

www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 백준 이분탐색 단계별풀기 랜선 자르기를 풀어봤습니다. 이분탐색을 살짝 응용한 문제입니다. 각각의 랜선을 최대 몇 cm로 잘라야 해당 자른 cm와 같은 랜선이 N개 생기냐는 문제입니다. 주의할 점은 int 범위가 벗어나므로 long 형 사용하는 것과 이분탐색시 left값을 0이 아닌 1로 세팅해야 된다는 점 입니다. 풀이는 다음과 같습니다. [Java] import java.util...

www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 벽 안에 물을 얼마나 채울 수 있냐는 문제입니다. 예제2를 예시로 보면 풀이가 이해하기 쉽습니다. 4 8 3 1 2 3 4 1 1 2 1. 양쪽 가장 자리는 물을 채울 수 없습니다. 2. 3번째 인덱스(2) 를 예시로 들면 왼쪽으로는 가장 높은 벽은 3이고 오른쪽에서 가장 높은 벽은 4입니다. 이 중에서 더 작은 벽 높이만큼 물이 채워 집니다. 이게 문제해결의 핵심입니다. 풀이는 다음과 같습니..

www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안 www.acmicpc.net 백준 1920 수 찾기 이분탐색 단계별 풀기 첫번째 문제를 풀어봤습니다. 말 그대로 이분탐색의 가장 기초적인 문제인 것 같습니다. 그리고 몰랐는데 이분탐색을 제공하는 함수가 있다는 것을 알았습니다. 풀이와 해당 내용을 정리합니다. [Java] import java.util.Arrays; import java.util.Scanner; public class Main { p..

www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 백준 1436 영화감독 숌 단계별풀기 브루트포스 마지막 문제 입니다. 숫자를 1씩 증가시켜가며 666이 포함된 숫자를 찾으면 오름차순으로 숌영화네임을 찾을 수 있습니다. 풀이는 다음과 같습니다. [Java] import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(Sy..

www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 백준 7562 나이트의 이동을 풀어봤습니다. 방향만 잘 설정해주면됩니다. 평소 map크기를 size+2 해서 index out of error를 해결했는데 여기서는 불편해서 비교문으로 처리를 했는데 이게 더 간편한거같아서 애용하려합니다. 풀이는 다음과 같습니다. [Java] import java.util.LinkedList; import java.util.Queue; import java.util.Scanner;..

www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 백준 10026 적록색약 문제입니다. 일반인이 보았을때의 구분되있는 색의 개수 초록색과 빨간색이 같은색으로 취급하는 적록색약인이 보았을때 구분되는 색의 개수를 각각 구해야합니다. 적록색약인은 R과 G를 같은색 취급하므로 map에서 G를 R로 치환한뒤 일반인과 똑같이 bfs()를 돌려주었습니다. 풀이는 다음과 같습니다. [Java] import java.util.LinkedList; import java...

www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 백준 14502 연구소를 풀었습니다. 벽을 3개 세우고 바이러스를 퍼트리고 안전지역을 구하는 문제입니다. 다음과 같이 로직으로 풀었습니다. 1. 안전지역(0)에 모든 경우의 수로 벽을 3개 세운다 -백트랙킹- 2. 벽 3개를 세운 후 바이러스를 퍼트립니다. -bfs- 3. 안전구역의 최댓값을 구합니다. 문제를풀며 삽질했던 부분은 copy()가 깊은 복사가 안된다는 점입니다. 평소 1차원 배열은 깊은 복사가 되었던것같은데 2..

programmers.co.kr/learn/courses/30/lessons/12909 코딩테스트 연습 - 올바른 괄호 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 ()() 또는 (())() 는 올바른 괄호입니다. )()( 또는 (()( 는 올바르지 않은 괄호� programmers.co.kr youngest-programming.tistory.com/398 [알고리즘] 백준 9012 괄호 -스택(stack)- 자바 코틀린 www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에..

programmers.co.kr/learn/courses/30/lessons/12899 코딩테스트 연습 - 124 나라의 숫자 programmers.co.kr 비슷한 문제를 최근에 풀었었는데 우연히 비슷한 문제를 만났슴다. 3진법이라 생각하고 살짝 응용해서 풀면됩니다. div 가 0일때 n-1 을 해주는거에 주의! 풀이는 다음과 같습니다. [java] import java.util.ArrayList; class Solution { public String solution(int n) { StringBuilder sb = new StringBuilder(); ArrayList list = new ArrayList(); while (n > 0) { int div = n % 3; list.add(div); n..

www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 백준 분할정복 단계별풀기 네번째 곱셈 문제를 풀어봤습니다. 처음 단순하게 곱하고 나눠주고 반복문 돌렸다가 시간복잡도 때문에 시간초과가 났습니다. 분할정복 단계므로 분할해서 재귀를 사용해 풀었습니다. 밑 공식대로 풀면 됩니다. 풀이는 다음과 같습니다. [Java] import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in..