[프로그래머스] Level3 - 줄 서는 방법
> 문제
문제 : [줄 서는 방법]
> 문제풀이
문제에서 k번째의 숫자를 찾아야 한다.
k는 n! 이하의 자연수이기 때문에 recursive하게 풀지는 못한다.
아이디어는 1 2 3 4 5 의 숫자가 있을 때,
'’뒤에서부터 자리를 바꾸면 되지 않을까” 에서 착안하였다.
k번 바꿀 수 있다면 뒤에서 부터 바꿔주면 된다.
1이 맨 앞에올 수 있는 경우의 수는 4! 이다.
첫 번째 인덱스는 k/4!이 될것이다.
두 번째 인덱스는 첫번째 인덱스 나머지 값 k%4! 에서 3!을 나눈 값이다.
즉, 해당 인덱스에 올 수 있는 값은 k/(n-1)!...
[프로그래머스] Level3 - 매칭 점수[2019 카카오 문제]
> 문제
문제 : [매칭 점수 (2019 KAKAO BLIND RECRUITMENT)]
> 문제풀이
문제가 다소 복잡하다.
하나의 단어와 HTML 페이지 문자열들이 주어지며,
기본점수, 외부 링크 수, 링크점수를 구하여 여기서 말하는 매칭점수를 구해야 한다.
위 세가지만 찾으면 매칭점수는 그대로 연산하면 된다.
기본점수는 HTML 페이지에 포함하는 단어의 개수이다.
대소문자 무시하기 때문에 소문자로 통일하였다.(혹시 태그명을 단어로 쓰일지 몰라서 소문자로 사용)
외부 링크 수는 “<a href="“에 해당하는 문자열을 찾아서 구하였다.
...
[프로그래머스] Level3 - 배달
> 문제
문제 : [배달]
> 문제풀이
문제에서 노드간 연결하는 간선이 두개 이상일 수 있기 때문에 가장 작은값을 저장하였고,
1번 마을(0번 노드)에서 시작하여 각 노드에 도달하는 거리가 최솟값이 되도록 다익스트라를 적용하였다.
시작점을 제외한 모든 노드를 최댓값으로 초기화하고, 작은 값으로 계속 갱신해준다.
소스는 다음과 같다.
import java.util.*;
class Solution {
static final int MAX_TIME_VALUE = 500000;
public int solution(int N, int[][] road, ...
[프로그래머스] Level3 - 경주로 건설(2020 카카오 인턴십)
> 문제
문제 : [경주로 건설]
> 문제풀이
최소 경로값 찾는 문제이다.
dfs, bfs 모두 풀이가 가능하지만, 메모이제이션을 이용해서 풀어야 한다.
나는 dfs로 풀었으며 가지치기해서 시간을 줄였다.
class Solution {
static boolean check(int x, int y, int[][] map){
if(x>=0 && y>=0 && x<map.length && y<map[x].length) return true;
else return fals...
[백준] 2186번, 문자판
> 문제
문제 : [문자판]
> 문제풀이
문자배열과 단어가 주어지면, 문자배열 임의 위치에서 시작하여 상하좌우 최대 K까지 이동하여 만들수 있는 단어의 갯수를 찾는 문제이다.
1<=M,N<=100, 1<=K<=5, 1<=단어길이<=80
배열 각각의 위치에서 시작하여 단어를 찾는데 완전탐색을 할 경우 시간이 터질것이다.
접근방법
피보나치 수열에서 메모이제이션을 쓰지 않고 Top-down 방식을 사용할 시, 중복된 결과값을 찾기위해 불필요한 연산을 하게된다. 이를 고려하면 각 배열에서 메모이제이션을 사용하여 풀이를...
[SpringBoot] EnableAutoConfiguration, ComponentScan
SpringBoot에서 web 프로젝트를 최초로 생성하면 ProjectNameApplication 클래스가 기본적으로 생성되며, main() 메소드로 실행할 수 있다.
import org.springframework.boot.SpringApplication;
import org.springframework.boot.autoconfigure.SpringBootApplication;
@SpringBootApplication
public class ProjectNameApplication {
public static void main(String[] args) {
SpringApplication.run(P...
[프로그래머스] Level2 - 멀쩡한 사각형
> 문제
문제 : [멀쩡한 사각형]
> 문제풀이
W, H 값이 1억 이하의 자연수이다.
분명 배열을 만들어서 풀이하지는 않을 것이다.
최대 공약수 또는 최소 공배수를 사용한 방법으로 접근해 보았다.
대각선으로 잘랐을 때, 대각선을 꼭지점으로 한 덩어리를 볼 수 있다.
예시에 따라 8,12 값이 주어졌을 때 네 덩어리를 볼 수 있는데, 이는 w,h값의 최대 공약수가 될 것이다.
정사각형인 4,4 값 역시 네 덩어리로 최대 공약수 4가 나올 수 있다.
이를 활용하여 덩어리는 구했고,
그 안에 대각선을 포함한 사각형은 어떻게 구할까..
대각선...
유클리드 호제법(Euclidean Algorithm)이란? Java 구현
유클리드 호제법(Euclidean Algorithm)을 알아보기로 한다.
l. 유클리드 호제법(Euclidean algorithm)이란?
두 수(자연수)의 최대공약수를 구하는 알고리즘의 하나이며, 기원전 300년경에 만들어진 가장 오래된 알고리즘으로 알려져 있다.
여기서 호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 말하며, 유클리드가 제안한 방법이다.
일반적으로 최대 공약수를 얻기 위해서는 두 수를 소인수 분해 해야 한다.
이 방법은 수가 커질수록 소인수 분해하기 어려울 수 있다.
ll. 구하는 방법
유클리드 호제법은...
103 post articles, 13 pages.