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

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/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 백준 단계별풀기에서 큐에 해당하는 문제를 풀어봤습니다. 데큐(Dequeue)는 알고는 있었는데 자바에서 직접 사용해보는건 처음이었네요. 양방향으로 입출력이 가능한 데큐의 특성을 활용하여 문제 그대로 풀면 되었습니다. 풀이는 주석으로 자세히 적어놨고 다음과 같습니다. [Java] import java.util.ArrayDeque; import java.util.Deque; import java.ut..

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/14659 14659번: 한조서열정리하고옴ㅋㅋ 첫째 줄에 봉우리의 수 겸 활잡이의 수 N이 주어진다. (1 ≤ N ≤ 30,000) 둘째 줄에 N개 봉우리의 높이가 왼쪽 봉우리부터 순서대로 주어진다. (1 ≤ 높이 ≤ 100,000) 각각 봉우리의 높이는 중복 없이 www.acmicpc.net 백준 그리디 유형의 한조서열정리하고옴ㅋㅋ 문제를 풀어봤습니다. 간단한 그리디 유형의 문제였는데 가독성이 조금 안좋은 것 같습니다.. 풀이는 다음과 같습니다. [Java] import java.util.Scanner; public class Main { private static int answer = Integer.MIN_VALUE; public static..

https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 백준 그리디 유형에서 보물이라는 문제를 풀어봤습니다. A와 B 배열의 인덱스 곱의 합이 최솟값이 나와야하는데 A만 재배열이 가능하고 B는 불가능합니다. B가 재배열이 불가하다는 말에 꽂히지말아야합니다. A와 B를 오름차순으로 정렬한다음에 A의 가장 작은값과 B의 가장 큰 값 인덱스들을 서로 곱해주는게 최소의 S결과가 나오게됩니다. 풀이는 다음과 같습니다. [Java] import java...

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

https://programmers.co.kr/learn/courses/30/lessons/17684?language=java 코딩테스트 연습 - [3차] 압축 TOBEORNOTTOBEORTOBEORNOT [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34] programmers.co.kr 알고리즘 그만보고싶어... 개발이 나아.. 오랜만의 알고리즘 풀이입니다. ㅎㅎ 오늘은 프로그래머스의 Level2 문제인 압축이라는 문제를 풀어봤습니다. 처음 문제를 보자마자 HashMap을 사용해야겠다고 생각해서 빠르게 접근할 수 있었습니다. 저의 풀이방법을 요약하면 다음과 같습니다. 1. 현재까지의 입력 단어 w 를 받는다. 2. w의 압축번호 계산 3. w..

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/17683?language=java 코딩테스트 연습 - [3차] 방금그곡 방금그곡 라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다. 그럴 때 네오는 다음 포털의 '방금그곡' 서비스를 이용하곤 한다. 방금그곡에서는 TV, programmers.co.kr 프로그래머스 방금그곡 문제를 풀어봤습니다. ㅎㅎ 한 단어로 된 음 여러개로 이루어진 악보문장이 아니라 C# 과 같이 뒤에 #이 들어가 2개의 문자로 이루어져 있는 음인 경우 문자열에서 한개씩 불러와 음을 비교하기가 조금 까다로울 수 있습니다. 그래서 두단어로 이루어진 C#과 같은 음을 c로 치환을 하면 더 쉽게 문제를 풀 수..

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://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/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..