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

보호되어 있는 글입니다.

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/9237 9237번: 이장님 초대 입력은 두 줄로 이루어져 있다. 첫째 줄에는 묘목의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에는 각 나무가 다 자라는데 며칠이 걸리는지를 나타낸 ti가 주어진다. (1 ≤ ti ≤ 1,000,000) www.acmicpc.net 백준 그리디 유형에서 9237번 이장님 초대라는 문제를 풀어봤습니다. ㅎㅎ 그리디 유형은 코드는 간단한데 생각을 빨리하는게 역시 중요한 것 같습니다 주석으로 설명은 대체합니다. [Java] import java.util.Arrays; import java.util.Collections; import java.util.Scanner; public class Main { p..

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/11497 11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net 백준 11497 통나무 건너뛰기 문제를 풀어봤습니다. 그리디 유형의 문제였습니다. 최소의 난이도를 가진 둥근 모양의 통나무 배치를 하기 위해서는 통나무를 양 옆으로 작은것들로 시작하여 점점 가운데로 올 수록 크게 배치하면 최소의 난이도를 만들 수 있습니다. 풀이는 다음과 같습니다. [Java] import java.util.Arrays; import java.util.Scanner; public..

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://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/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로 치환을 하면 더 쉽게 문제를 풀 수..