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

https://www.acmicpc.net/problem/16922 16922번: 로마 숫자 만들기 2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다. www.acmicpc.net 백준 백트래킹 유형문제를 골라 풀어봤습니다. ㅎㅎ 4개의 로마숫자가 있는데 N개를 사용하여 만들 수 있는 합의 모든 경우의 수를 구하는 문제였습니다. 처음에 N이 20개로 작아보여서 Set과 리얼완전모두탐색으로 풀었는데 시간초과가 났네요 ㅠ 중복배열선언과 같은 합이 안나오게 탐색하게끔 인덱스를 설정하여 탐색하여 통과할 수 있었습니다. ㅎㅅㅎ [Set 사용시 시간초과] import java.util.HashSet; import java.util.Scanner; public class Main {..

https://www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 연산자의 개수 www.acmicpc.net 백준 유형별풀기에 백트래킹 문제 연산자 끼워넣기 (2) 를 풀어봤습니다. 연산자 우선순위는 배제하고 정해지 연산자별 개수로 가장 큰 수식과 작은 수식 결과를 도출해내는 문제였습니다. 연산자 개수를 한개씩 줄여가며 백트래킹을 돌리면 되는 문제였습니다. 그리고 이렇게 두 개의 값을 연산하는 문제인 경우 첫번째 값을 넣어주고 돌리면 풀기 좋습니다 :) 풀이는 ..

https://www.acmicpc.net/problem/10974 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net 오랜만에 백트래킹과 자바 감도 익힐겸 백트래킹 유형에서 기본문제를 풀어봤습니다. ㅎㅎ 요즘 코볼만 쓰고 있는데 자바 정말 오랜만에 쓰네요.... 그립다 자바야 ㅜㅜㅜㅜㅜㅜㅜㅜ 풀이는 다음과 같습니다. [Java] import java.util.Scanner; public class Main { private static int N; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.ne..

https://www.acmicpc.net/problem/15656 15656번: N과 M (7) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 오랜만에 알고리즘을 풀고 백트래킹의 기본이라 할 수 있는 N과 M 시리즈를 풀어봤습니다. 확실히 오랜만에 자바를 사용하고 알고리즘을 풀었더니 없던 실력도 많이 줄은 것 같네요.. ㅠ 주어진 숫자를 여러번 사용할 수 있지만 오름차순으로 중복되지 않은 순열을 출력해야 했습니다. 그러므로 isVisited[] 같은 중복을 체크하는 Boolean 형 타입은 필요하지 않고 StringBuilder..

https://programmers.co.kr/learn/courses/30/lessons/12905?language=java 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr 프로그래머스 가장 큰 정사각형 찾기 라는 문제를 풀었습니다. 처음에 BFS문제로 접근했으나 밑에처럼 효율성에서 통과를 하지못했습니다. 그래서 DP로 풀어야한다고하는데 https://zzang9ha.tistory.com/189 프로그래머스[Java] - (Level2)가장 큰 정사각형찾기(DP) https://programmers.co.kr/learn/courses/30/lessons/12905 프로그래머스 코드 중심의 개발자 채..

https://www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 백준 완전탐색 유형에서 미친 로봇이라는 문제를 풀어보았습니다. ㅎㅎ 동서남북으로 움직일 수 있는 로봇이 N만큼 이동을 하는데 로봇이 같은 곳을 한 번보다 많이 움직이지 않을 때 이동경로가 단순한 로봇이고 이러한 움직임을 가질 확률을 구하는 문제였습니다. 추가로 동서남북 이동확률이 존재합니다. 그래서 풀이방법은 움직임과 해당 경로까지 움직임의 확률을 DFS로 넘기면서 탐색해주면 되는 문제였습니다..

https://programmers.co.kr/learn/courses/30/lessons/81302?language=kotlin 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 요즘 할일이 많아 블로그랑 개인 공부를 2주 넘게 못한거 같네..

https://programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 프로그래머스 메뉴리뉴얼 문제를 풀어봤습니다. ㅎㅎ 풀다가 테스트케이스 18,20이 시간초과가 뜨고 나머진 다 통과했는데 원인을 찾지 못하고 있습니다. ㅠ 효율성검사도 아닌 정확도 검산데 뭐가 문젠건지 잘 모르겠네요.. 통과는 못하였지만 다른 할일도 있어 일단 제가 풀이한 코드를 포스팅하려고 합니다. 이후에 코드를 좀 더 효율적으로 짤게 있을지 생각해봐야겠습니다. ..

https://programmers.co.kr/learn/courses/30/lessons/1835 코딩테스트 연습 - 단체사진 찍기 단체사진 찍기 가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 programmers.co.kr 프로그래머스 단체사진 찍기 문제를 풀어봤습니다. ㅎㅎ 8명의 카카오 프렌즈들이 사진을 찍는데 프렌즈의 규칙에 맞게 사진을 찍을 수 있는 경우의 수를 구하는 문제였습니다. DFS로 완전탐색을 한 후 해당 순열이 조건을 만족하는 순열인지 구하는 방식으로 해결했습니다. 주석으로 추가 설명을 달아놨습니다. 풀이는 다음과 같습니다. [Java] class Solutio..

https://programmers.co.kr/learn/courses/30/lessons/42840?language=kotlin 코딩테스트 연습 - 모의고사 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 programmers.co.kr 프로그래머스 모의고사 문제를 풀어봤습니다. 쉬운 문제로 별도의 설명은 필요 없을 것 같습니다. ! [Java] import java.util.ArrayList; import java.util.List; class Solution { public int[] solution(int[] answers) { int[] score = new ..

https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 백준 치즈라는 BFS 유형 문제를 풀어봤습니다. ㅎㅎ 공기와 닿아있는 치즈는 녹게되고 순차적으로 반복하여 몇시간 뒤에 치즈가 다 녹고 다 녹기전 마지막으로 남아있는 치즈의 개수를 구하는 문제였습니다. BFS를 사용하여 공기와 닿아있는 치즈들을 시간마다 녹여주면 됩니다. 풀이는 주석으로 대체합니다. [Kotlin] import java.util.* private var R = 0 private var C =..

https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 백준 2661 좋은수열이라는 백트래킹 유형 문제를 풀어봤습니다. ㅎㅎ 인접한 두 개의 부분 수열이 동일한게 없는게 좋은수열이며 이를 만족하는 가장 작은 수를 구하는 문제였습니다. 가장 중요한 부분은 check() 함수로 끝에서부터 1,2,3... 개로 양쪽으로 나눠 동일한 부분수열을 가졌는지 체크해줍니다. 풀이는 다음과 같습니다. [Kotlin] import java.util.* import kotlin.sy..

https://www.acmicpc.net/problem/15664 15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백준 백트래킹 대표문제 N과 M 시리즈 10번을 풀어봤습니다. ㅎㅎ 풀이는 다음과 같고 설명은 주석으로 대체했습니다. [Java] import java.util.Arrays; import java.util.HashSet; import java.util.Scanner; import java.util.Set; public class Main { private static int N; private..

https://www.acmicpc.net/problem/15665 15665번: N과 M (11) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백준 백트래킹 문제 시리즈로 유명한 N과 M 시리즈의 11번째 문제를 풀어봤습니다. 같은 수를 여러번 고를 수 있는 순열조합이므로 중복 선택을 체크할 boolean[] isVisited 는 사용하지않았습니다. 풀이는 다음과 같습니다. [Java] import java.util.Arrays; import java.util.Scanner; public class Main { private stat..

www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 백준 백트래킹 유형의 2529번 부등호 문제를 풀어봤습니다. 부등호가 주어지면 해당 부등호를 만족하는 숫자들 중 최댓값과 최솟값을 출력하면 되는 문제였습니다. DFS 백트래킹을 사용하여 완전탐색 해주면 해결이 됩니다. 풀이는 주석으로 적어놨고 다음과 같습니다. [Java] import java.util.ArrayList; import java.util.Collections; import java.util.Li..