케이스윔의 개발 블로그

문제두 문자열이 주어질 때 부분 수열 중 가장 긴 부분 수열의 길이를 구하시오.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/9251) 풀이처음에 이 문제를 보고 잘 못풀 것 같다는 생각이 들어서 넘겨버렸었는데 다시 풀어보았습니다! 생각보다 쉬운 문제였는데 LCS알고리즘이란 말이 붇어있으니 어려워 보여서 못 풀었던 것 같기도..합니다. 이전에 풀었던 문제는 숫자의 배열이 주어지면 그것을 통해 가장 긴 증가 수열의 길이를 구하는 것이었는데 문자열을 통해서 공통된 부분을 찾는다고 접근하려니 어렵게 느껴졌습니다. 두 문자열을 쪼개어서 차례차례 생각을 하면 풀어나갈 수 있습니다. 만약 두 문자열이 'ABC'와 'ADB'라고 하겠습니다. 문자열을 첫번째문자부터 잘라서 보면 ..

문제릴레이션을 나타내는 문자열 배열 relation이 매개변수로 주어질 때, 이 릴레이션에서 후보 키의 개수를 return 하도록 solution 함수를 완성하시오.문제 출처: 프로그래머스(https://programmers.co.kr/learn/courses/30/lessons/42890) 풀이이 문제도 지난 하반기 때 못풀었었는데 그 당시 생각했었던 방법으로 새로 풀었습니다. 후보키는 유일성과 최소성을 만족해야하기 때문에 가능한 모든 조합을 구한 다음 각 조합이 유일성과 최소성을 만족하는지 그대로 구현해서 확인하면됩니다. 당시에는 그 모든 조합을 확인할 수 있을지에 대한 의문이 있어서 다른 문제를 먼저 풀었던 것 같은데 다시 풀면서 조건을 보니 최대 column의 수와 row 수가 작기 때문에 모든 ..

문제트리를 구성하는 노드의 x, y 좌표들이 주어질 때 규칙에 맞게 이진트리를 그리고 전위 순회와 후위 순회 결과를 출력하시오.문제 출처: 프로그래머스(https://programmers.co.kr/learn/courses/30/lessons/42892) 풀이이 문제는 지난번 하반기 채용 당시 풀어야했던 문젠데 못 풀었던! 문제였습니다. 오늘은 오랜만에 프로그래머스에 들어갔다가 이 문제를 골랐는데 풀 수 있는 방법이 떠올라서 풀었습니다! 처음에 이 문제를 봤을 때는 좌표가 x, y로 주어지는데 이진트리로 표현하기 위한 방법이 떠오르지않아서 못풀었는데 오늘은 우선순위큐를 이용하면 풀 수 있겠다는 생각이 들었습니다. y좌표가 높을수록, x좌표가 작을수록 우선순위큐를 만들어주면 가장 위에서 부터 차례대로 각 ..

문제N과 수열이 주어질 때 부분 수열 중에서 가장 합이 큰 것을 구하시오.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/11055) 풀이전에 풀었던 가장 긴 증가 부분 수열(https://kswims.tistory.com/152) 문제와 거의 비슷합니다. 이전 문제는 길이를 구해야했다면 이번엔 합으로 dp배열을 추가해나갑니다. i번째 값이 들어왔을 때 i-1번째부터 쭉 내려가며 i번째 값보다 작은 숫자이면서 dp의 값을 가장 큰 값을 택해서 dp[i] = 해당값+num[i]를 해주면 됩니다. 코드https://github.com/kswim/Algorithm/blob/master/DP/11055.cpp

문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구하시오.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/2133) 풀이저번에 이 문제를 풀려했던적이 있는데 점화식을 세우지 못해서 포기했던 문제였습니다. N이 홀수인 경우에는 0이 된다는 점과 타일의 위치에 따라 규칙을 알 수 없는 특수한 케이스로 점화식을 세우지 못했었습니다. 그러다 bitmasking을 공부하며 관련 문제들을 풀다가 이 문제도 해당분류에 속함을 알 수 있었습니다. dp[i][000~111] 과 같이 표현을 할 수 있고 이는 i-1번째까지 다 채워졌다고 했을 때 i-1번째의 행에 채워진 타일을 bit로 나타냅니다. 다 채워지지 않은 경우를 000, 다 채워진 경우를 111,..

문제 상근이는 20병의 맥주를 가지고 있고 50미터에 한 병씩 마시며 목적지에 도착해야한다. 출발지와 목적지 사이에 맥주를 파는 편의점이 주어질 때 상근이가 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/9205) 풀이처음에 문제를 봤을 때는 주어지는 좌표도 너무 넓어서 50으로 나눠서 관리를 해줄지.. 등의 생각이 많이 드는 문제였는데 하나의 힌트로 쉽게 해결할 수 있는 문제였습니다. 편의점을 통해서 그래프를 그리는 것입니다. 처음에 20병으로 시작하게되고 어느 편의점을 들리던지 먹은만큼 맥주를 살 수 있기 때문에 편의점에 들리게 되면 20병으로 다시 채워집니다. 남은 병수와 관계없이 20병안으로 편의점을 ..

Annotation을 이용한 스프링 설정지금까지는 스프링 설정파일로 bean을 생성하기 위해서 GenericXmlApplicationContext를 통해서 스프링 컨테이너와 함께 bean을 생성해서 getBean()을 통해서 해당 bean을 사용했습니다. xml파일 대신에 Java파일로도 설정파일을 만들 수 있습니다. Java 파일을 통해서 설정파일을 만들었다면 AnnotationConfigApplicationContext를 통해서 스프링컨테이너를 생성하고 getBean()을 통해 사용할 수 있습니다. 1. xml파일 대신 설정해줄 Java파일을 만들고 @Configuration을 해줍니다. @configurationPublic class MemberConfig{….} 2.xml에서 생성했던 bean들은..

DI(Dependency Injection)외부에서 의존관계의 객체를 주입하는 것입니다. 객체 생성 후 다른 객체에 해당 객체를 주입하는 것입니다. 그냥 정의로는 잘 이해가 안가니 예를 들어보면 만약 클래스 A의 필드로 클래스 B가 존재하고, 클래스 A에서 어느 메소드에서의 연산에서 클래스 B가 필요하다면 클래스 A와 B를 생성하고, 클래스 A의 생성자 또는 setter를 통해서 클래스 B를 A의 필드로 만들어주어야 합니다. 이렇게 해주는 것이 바로 의존성 주입입니다.이전 글에서 스프링 설정파일에서 bean을 만들 수 있다고 했는데 생성한 bean에 주입하고자 하는 객체를 태그를 통해 주입할 수 있습니다. 위의 예시에서 A라는 bean을 생성할 때 해당 태그안에 와 같이 해주면 됩니다. 이렇게 만들어진 ..