본문 바로가기

Archived(CSE Programming)/알고리즘(Java)

 (17)
프로그래머스 - 방문길이(Java, LV3) https://programmers.co.kr/learn/courses/30/lessons/49994 코딩테스트 연습 - 방문 길이 programmers.co.kr 풀이 시뮬레이션 문제로 전체 시뮬레이션 대상의 크기는 크지 않지만 조건들을 놓치기 쉬운 부분이 있는 문제였다. 2차원 배열로 방문했는지 안했는지 체크 -> X 3차원 배열로 해당 지점에 방문할 때 어느 방향에서 와서 방문한 길인지 체크 -> O 방문한 길이라고 했기 때문에 새로 방문했을 경우만 길이를 체크하는 것이 아니라 한 지점에 대해 4방의 길이를 생성할 수 있기에 그 부분을 주의해야 한다. 추가적으로 4방의 길이를 체크함에 있어 기존위치 -> 신규위치로 변할때 기존위치의 U 방향과 신규의치의 D 방향은 결국 같은 길 인점을 주의해야한다...
프로그래머스 - 숫자게임(Java, LV3) https://programmers.co.kr/learn/courses/30/lessons/12987 코딩테스트 연습 - 숫자 게임 xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다. 먼저 모든 사원이 무작위로 � programmers.co.kr 풀이 처음 풀었던 풀이 A 팀과 B 팀을 전부 오름 차순으로 정렬한다. 앞에서부터 A팀의 패를 이길 수 있는 B팀의 패를 찾는다. 이길 수 있는 패를 찾았을 경우, B팀 내에서 이번 대결의 상대를 탐색하는 것은 중단한다. 이길 수 있는 패를 찾았을 경우, INF 상수를 통해 마킹하여 다음 대결에 사용하지 않는다. 이 때, 오름차순 정렬으로 되어..
프로그래머스 - 섬 연결하기(Java, LV3) / MST https://programmers.co.kr/learn/courses/30/lessons/42861?language=java 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 풀이 해당 문제는 graph의 MST(Minimum Spanning Tree) 최소연결간선 트리 찾기 문제로 크루스칼 알고리즘으로 해결 가능하다. 먼저, 주어진 전체 costs를 비용 순으로 정렬 후 사이클체크를 하면서 사이클이 형성되지 않는다면 해당 간선을 연결한다. 연결하면서 두 노드를 union 해준다. 그렇게 전체 costs를 탐색하면서 MST가 구성되었다면 중단하여 지금까지 계산한 비용을 반환한다. import java.uti..
프로그래머스 거스름돈(Java, LV3) /DP https://programmers.co.kr/learn/courses/30/lessons/12907 코딩테스트 연습 - 거스름돈 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5�� programmers.co.kr 풀이 DP 문제 중 가장 대표중인 문제, 화폐 거스름돈과 유사한 문제이다. 단, 차이점은 지불할 수 있는 방법의 수를 계산하는 것이다. 점화식을 세우고 진행하는데, 2차원 배열을 통해 처음 접근했다. d[i][j] = i개의 화폐(moeny[0..i])로 j 금액을 낼 수 있는 방법 수 d[i][j] = d[i-1][j] + d[i][j-mone..
프로그래머스 - 멀쩡한 사각형(Java, LV2) https://programmers.co.kr/learn/courses/30/lessons/62048 코딩테스트 연습 - 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 �� programmers.co.kr 풀이 해당 문제는 사각형 패턴의 규칙을 찾는 것이 관건이었다. (나는 3개의 예제를 그려보며 패턴이 있음을 파악했다... 수학적 사고가 뛰어난 사람들은 저게 1차함수를 활용하는 문제임을 알고 푼 듯하다) 먼저 대각선이 그어지는 패턴을 보면 어느 꼭짓점(좌표)에서 딱 맞게 떨어진다. 그림 출처 : ajufresh.log 그렇기에, ..
프로그래머스 - 주식가격(Java, LV2) https://programmers.co.kr/learn/courses/30/lessons/42584?language=java 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr prices의 해당 값이 떨어졌을 때 그 시점의 인덱스 차이를 넣어주면 된다. 단, 값이 떨어질 경우없이 끝까지 갔을 경우에는 -1을 해줘야함(끝까지 간 경우는 index를 1 초과했으므로) 그리고 마지막 값은 무조건 0 이므로 계산해주지 않아도 된다. 아무리 생각해도 O(n^2)을 극복하는 방안..
프로그래머스 타겟 넘버 https://programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 자바 공부 겸 프로그래머스 탐색 Level2의 비교적 쉬운 난이도 문제를 풀어봤다. 일반적인 DFS 문제로 접근하면 되며 체크 idx에 도달하면 값을 비교하여 정답을 count 하면 된다. import java.util.*; public class Solution { int glb_answer = 0; int glb_target = 0; public void print(int n){ System.out.pri..
프로그래머스 큰 수 만들기 문제 : https://programmers.co.kr/learn/courses/30/lessons/42883?language=java 코딩테스트 연습 - 큰 수 만들기 | 프로그래머스 programmers.co.kr 해당 문제는 Java의 StringBuilder를 활용하여 풀 수 있었다. 가장 중요한 로직은 각 탐색 범위를 지정하는 것이다. 탐색 범위의 시작은 0(...전체길이 - k) 부터 시작한다. 그리고 실제 탐색은 이전에 선택한 idx 보다 큰 숫자부터 가능하다(고른 숫자의 오른쪽부터 고를 수 있으므로). 그래서 idx+1 ~ i+k 를 통해서 각 문자의 범위를 지정할 수 있고 이중 for문을 통해 이를 처리하여 구현할 수 있다. class Solution { public String solu..

티스토리툴바