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

https://programmers.co.kr/learn/courses/30/lessons/12981 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 영어 끝말있기 문제를 풀어봤습니다. 반복문과 문자열을 조작하여 풀이했습니다. 과거의 기록들을 리스트에, 이전(최근) 단어를 String 에 따로 관리하여 현재단어와 비교하여 해결했습니다. 풀이는 다음과 같습니다. import java.util.ArrayList; import java.util.List; class Solution { public int[] solution(int n, String[] words..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS란 Longest Common Subsequence 로 최장 부분 수열을 말합니다. 이전 dp 문제들에서도 부분 수열문제들을 풀었었는데 이번 문제는 하나의 문자열 또는 집합이 아닌 두개의 문자열 비교까지 했어야 했습니다. 풀다가 모르겠어서 다음 사이트를 참고하였습니다. https://jaesungbong.tistory.com/21 백준 온라인 저지..

https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5 www.acmicpc.net 해설을 보고도 이해가 좀 어려운 문제였습니다. 재귀 이해도가 많이 약한 것 같습니다. 참고 https://milkye.t..

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 백준의 가장 긴 바이토닉 부분 수열 문제를 풀어봤습니다. 동적계획법1 의 단계별문제이며 이전에 풀었던 문제에서 조금씩 응용을 하며 풀고 있습니다. 이 문제도 한가지의 케이스를 더 생각하고 응용하면 풀리는 문제였습니다. 이전문제는 다음 포스팅에서 참고합니다. https://youngest-programming.tistory.com/265 [알고리즘] 백준 2156 포도주 시식 -dp- https://www.acmicp..

https://programmers.co.kr/learn/courses/30/lessons/12911 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 프로그래머스 레벨2 연습문제 다음 큰 숫자를 풀어봤습니다. 문제가 너무 간단하길래 문자열 차례대로 1이 있는지 검사하면 효율성에서 에러가 날줄 알았는데 잘통과하네요. 이진수로 바꾸는 법을 알면 쉽게 풀 수 있는 문제였습니다. class Solution { public static void main(String[] args) { Solution solution = new Solution(); solution.s..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net https://youngest-programming.tistory.com/265 [알고리즘] 백준 2156 포도주 시식 -dp- https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고 www.acmicpc.net 백준 동적계획법1 단계별 풀기 포도주 시식 문제를 풀어봤습니다. dp[] 에 n개의 포도주 최대양을 저장, wine[] 에 n 번 째..

https://programmers.co.kr/learn/courses/30/lessons/12951 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 프로그래머스 레벨2에 있는 문제이고 분류는 안되어있지만 문자열을 조작하는 문제입니다. 처음에 쉽게 풀릴 거 같았는데 예외사항과 실수가 조금 있었습니다. (문제가 좀 빈약한 것 같아요) 예를들어 (제가 잘못이해한거 포함해서) 1. 공백이 연속으로 올 수도 있고 공백다음의 공백은 첫 문자로 치지 않는다. 즉 공백은 문자가 아니라고 생각하면 됩니다. 2. 처음 풀때 저는 제한 조건쪽만 보고 첫 문자가 영문이 아닌 ..

https://programmers.co.kr/learn/courses/30/lessons/1829?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 처음 문제를 보고 BFS를 사용해서 큐로 풀어야겠다고 생각했고 테스트 통과도 잘 통과되었습니다. 하지만 제출을 하니 계속 실패가 뜨더라고요. 그래서 다른 케이스도 해봤으나 다 맞길래 질문하기에 들어가보니 이 문제는 테스트 실행이 아닌 제출하기에서는 전역변수를 전역변수에서 바로 초기화 해놓으면 안되고 solution 함수 내에서 초기화를 해줘야 한다더라고요. 옛날 문제라 그런가.. 왜....

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 백준 1463 1로 만들기 문제에 이어 동적계획법 다음단계인 쉬운계단수를 풀어봤습니다. 이전 문제보다 바로 2차원 배열로 접근해서 쉽게 풀수 있었습니다. 그리고 주의해야할점이 문제에 나와있는것처럼 %1000000000 을 해줘야합니다. 위와 같이 먼저 dp 정의를 세우고 dp[자릿수][오는숫자] = 경우의수; dp 문제의 경우 대부분 초기 값을 몇개 세팅해주고 풉니다. 위 그림은 두자리(N=2) 의 예시인데 앞자리는 0이 못오고 1~9가 올 수 있음을 알 수 있습니다. 그러므로 초깃값을 0빼고 다음과 같이 해줍..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 처음 2차원 배열로 접근 했다가 삽질했습니다. import java.util.Scanner; class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] dp = new int[N + 1]; // 인덱스 : 숫자, 값 : 최솟값 dp[0] = 0; dp[1] = 0; for (int i = 2; i

https://programmers.co.kr/learn/courses/30/lessons/60057 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 프로그래머스 프로그래머스 문자열 압축 -2020 KAKAO BLIND RECRUITMENT- 를 풀어봤습니다. 처음 생각난게 split 특성으로 푸는거여서 그대로 풀었습니다. 중간에 다른 쉬운방법도 생각났는데 외골수 성향이 있어서 더럽게 풀어도 이대로 풀어버렸네요.. ㅠ 너무 더럽게 풀었다는... 늦었으니 내일 생각나면 다른 방법으로 풀어볼까 합니다. 자바 문자열 split의 다음과 같은 특성을 이용했습니다...

https://programmers.co.kr/learn/courses/30/lessons/42747 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제를 이해하기 어려웠습니다... ㅠㅠ 특히 문제에서 나머지 논문이 h번 이하 인용되었다면을 -> h번 이하 인용된 논문이 h편 이하의 개수여야한다로 잘못이해해서 엄청 삽질했습니다. (h번 이상 인용된 논문이 h편 이상의 개수인 것만 만족하면 되는데 말이죠..) 매번 문제를 이상하게 해석하는 경우가 많은데 정신 똑바로 차려야겠습니다... [풀이] ex) 3, 0, 6, 1, 5 => 오름차순 정렬 0, 1, ..

https://programmers.co.kr/learn/courses/30/lessons/42883 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근은 빠르게 했으나 테스트 10의 시간초과 때문에 고생한 문제입니다. 먼저 풀이법은 다음과 같습니다. (주석에 쓸려했는데 주석 쓰고 코드 돌리면 시간초과 뜨더라고요 ㅋㅋㅋ ㅠㅠ) 1. 앞자리수는 항상 뒷자리보다 큰 수가와야 한다. 그러므로 반복문을 돌며 인덱스 0부터 한칸씩 증가하면서 n, n+1을 비교해주고 앞자리수가 작다면 n 인덱스를 제거해준다. 2. 마지막까지 온 경우 중복숫자들이거나 정렬이 잘 되있..

https://programmers.co.kr/learn/courses/30/lessons/62048 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 프로그래머스 멀쩡한 사각형이라는 문제를 풀어봤습니다. 30분 정도 풀다가 사각형에서 자도 없어서 대각선 그려서 사각형 몇개 지나는지 그리거나 보기도 힘들고 기울기 방정식이나 분할해서 계산, 규칙 등 계속 볼려고 했으나 모르겠어서 바로 구글링했습니다. 허허 그렇답니다. 설명은 사이트 들어가면 자세히 나와있습니다. 공식을 아니 최대공약수만 구할 줄 알면 바로 풀리는 문제였습니다. 이번 문제로 얻어간 거는 저러한 ..