본문 바로가기

분류 전체보기

[리눅스 마스터] 공부 자료 정리
보호되어 있는 글입니다.
[이분탐색] 징검다리 - Java 코드 ★★★★
2021. 8. 18. https://programmers.co.kr/learn/courses/30/lessons/43236?language=java 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 레벨 4지만 정말 어려웠다. 문제 이해 예제를 기준으로 다시 정리해보면 0 ~ 25 사이거리에 [2,11,14,17,21] 위치에 돌들이 존재하는 상황이며, 0 ~ 25 사이에서 어떤 위치값이 N개의 돌을 제거 했을때, 가질수 있는 최소 거리값들 중 최대값일까?이다. 예제와 같이 5개의 돌의 위치가 주어지면, 돌과 돌사이거리..
[이분탐색] 입국심사 - Java코드 ★★★
2021. 8. 17. https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 문제 이해 몇 분이 가장 최적의 시간인지를 찾으면 된다. 시간을 탐색할 범위는 1 ~ N x times[LastIndex] 이다. 이 범위 안에서 이분탐색을 통해, 해당시간에 n명을 만족하는 경우를 찾아 반환해주면 된다. 주의 문제에서 input의 범위는 n은 총 10억명까지, 대기시간은 총 10억 분까지도 들어올수있다. 이분탐색의 맨 우측 끝값이 최악의 경우 1..
[DFS/BFS] 여행경로 - Java코드 ★★★
2021. 8. 12. https://programmers.co.kr/learn/courses/30/lessons/43164?language=java 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 문제 풀이 import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; class 여행경로 { /* 테스트 1 〉통과 (78.43ms, 106MB) 테스트 2 〉통과 (8.62ms, 81.2MB) 테스트 3 〉통과 (..
[DFS/BFS] 단어변환 - Java코드 ★★
2021. 8. 11. https://programmers.co.kr/learn/courses/30/lessons/43163?language=java 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 문제 설계 DFS / BFS 을 통해 결과를 구하는 로직은 어렵지 않지만, 여러가지 클래스와 인터페이스의 존재를 알고 사용하는것이, 간결하면서도 효율적인 코드를 만들 수 있다고 생각되므로 Stream() 클래스에 대해서 좀더 공부해야할것같다. 풀이 import java.util.ArrayList..
[DFS/BFS] 네트워크 - Java코드
2021. 8. 11. https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 문제 설계 노드별 간선의 연결여부가 네트워크수를 결정 짓는다. Top으로부터 연결된 아이들을 제거해가면서 네트워크수를 Count해주면 될것 같다. 나는 computers[i][i]값이 무조건 1이라는 속성을 이용해서 Flag로 활용하여 이미 연결된 네트워크라는 것을 확인 할때마다 0으로 바꿔주었다. (잘못된) 풀이 class Solution { static..
[DFS/BFS] 타겟넘버 - Java코드
2021. 8. 11. https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 문제 설계 쉽습니다. 사칙연산도 2개만 존재하고, 이전에 동적계획법에서 N으로의 표현문제를 풀었었기에, 비슷하면서도 난이도가 낮은 DFS로 판단하고 풀었습니다. 결과를 저장하는 answer 변수를 전역으로 선언하여 반환하지 않는 재귀함수로 구현하여 경우의 수를 순회하였습니다. 풀이 class Solution ..
[동적 계획법] 도둑질 - Java 코드
2021. 8. 2. https://programmers.co.kr/learn/courses/30/lessons/42897 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 programmers.co.kr 문제 이해 원형의 구조를 가지기 떄문에 첫번째집을 털면 마지막집을 털수없고, 두번째 집부터 털어야 마지막까지 비교가 가능해진다. 그러므로 두 가지 Case를 나눠서 순회하여 최댓값을 구하고, 두 경우 중 큰값을 반환해주면 된다. 중요한건 DP를 사용해야하므로, 두번의 케이스의 메모이제이션을 위해 Array를 만들어야한다. (두번 돌려면 원본을 훼손하면 안되니깐....
[동적 계획법] 등굣길 - Java코드 ★★★ (설계가 어려움)
2021. 8. 2. https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 문제 설계 오른쪽, 아래로만 움직이면서 침수된 판을 제외하고 지나갈수 있는 경로중 최소값 경로의 갯수를 구하는 문제이다. 최단 경로를 구하라 했지만, 사실 어떻게 가도 경로값은 같을수 밖에 없다;; 포인트 경로를 구하는 법은 내머리로 나오지 않았고 한 블로그를 참고했다 M,N의 이차원배열을 선언하고, 경로값을 초기화해주되, 범람지역은 0으로 생각하고 ..
[동적 계획법] 정수 삼각형 - Java코드
2021. 8. 2. https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 문제 풀이 아래에서 부터 순회하면서, 상위노드에 값을 더해주면서 메모이제이션 한다. class Solution { public int solution(int[][] triangle) { for(int i=triangle.length-2;i>=0;i--) { for(int j=0;j
[동적계획법] N으로 표현 - Java 코드 ★★★(★★)
2021. 8. 2. https://programmers.co.kr/learn/courses/30/lessons/42895?language=java 코딩테스트 연습 - N으로 표현 programmers.co.kr 문제 이해 DP는 메모이제이션이 필요하다. 해당 문제에서 이전단계에 대한 메모이제이션을 위해서는 각각의 N을 사용하여 만들어지는 모든 경우의 수를 만들어 저장하고, 그렇게 저장한 이전의 경우들을 바탕으로 이후에 단계를 만들어가는 풀이가 필요하다. 풀이 메모이제이션을 위해 Set배열을 만들어서 푼 풀이이다. 각각의 Set 배열에는 연산의 숫자로 만들어질 수 있는 모든 값들을 저장한다. 이후에 Set 배열의 낮은 인덱스에서부터 만들고자했던 목표값 number가 있는지 검사해주면, 최솟값 연산을 반환 할 수 있다. imp..
[그리디] 단속카메라 - Java코드 (프로그래머스 버그존재)
2021. 7. 30. https://programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 문제 항상 느끼는건데 문제가 참 상냥하지 못함. + 이번에는 문제 설명에 이상한점이 있음, 입출력의 설명 부분에서 -5, -15 지점을 지난다는 말은 틀린말이 아니지만, 사람들에게 혼동을 줄 수 있는 말들임 로직상 통과하는 부분에 카메라를 설치해주어야 최소값을 찾을수 있을것으로 보인다. 올바른 로직으로 구현했을때 카메라는 제일 먼저 빠져나가는 3번 차량의 -13에서 카메라가 설치되어 1번, 2번 을 같이 찍고, 그외에 포함되지않는 4번차량의 범위내에 한번더 설치되어 ..
[그리디] 섬 연결하기 - Java코드 ★★★ (크루스칼, 신장트리)
2021. 7. 29. https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 문제 설계 일단 최속밧을 찾기위해서는 Costs로 오름차순 정렬은 필수이다. Costs가 1이거나 작다고 해서 불필요하게 무작정 연결해서는 안된다. 모든섬 하나 이상의 선이 연결되어도 전체 통행에 대한 연결이 안됬을 수 있다. 선이 이어지는지 여부를 체크하기위한 부분이 필요하다. 이 문제는 신장 트리 구조를 알고 트루스칼 알고리즘을 사용해야하는 문제이다. 트루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하는 알고리즘이다. 연결해야 하는 노드수만큼의 배열..
[그리디] 구명보트 - Java코드 ★★
2021. 7. 29. https://programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 문제 설계 정렬된 자료에서 몸무게가 높은 순서로 뽑으면서 Count하되, 제일작은 사람과의 합이 limit을 넘지않으면 같이 뽑을 수 있도록, Deque 자료구조를 활용하여, 정렬된 자료에서 앞뒤로 poll()을 해주도록 하였다 풀이 public static int solution(int[] people, int limit) { int..
[그리디] 큰 수 만들기 - Java코드 ★★★
2021. 7. 28. https://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr https://hsin.hr/coci/archive/2011_2012/ Croatian Open Competition in Informatics hsin.hr 문제 출처이자 다양한 테스트케이스를 볼 수 있음 (4번의 테스트 다운후, kerk 폴더내 in, out 파일 참고) 문제 나의 접근법 (오답) number 문자열안에 가장 큰수인 9 ~ 0까지 순서대로 반복문을 돌면서, 해당수를 문자열 내에 큰수를 가장 먼저 만나는 부분에서 문자열을 잘라서, 가장 작은숫자부터 차례차례 제거하는 연산을 해서 반복해서 답을 구하려했지만, 테스트케이스 3..
[그리디] 조이스틱- Java코드 ★★★
2021. 7. 27. https://programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 문제 이해 문제 설명이 조금어렵다. 이해가 중요하다. AAA 시작해서 위아래로 알파벳이동은 하나씩 움직인다. 그리고 또다른 움직임인 커서이동이 있다. 커서이동은 문자열에 자리 이동이다. 첫번째 문자를 목표하는 값으로 셋팅하였으면, 다음 두번째 문자로 이동할 수 있다. 그런데 문제에서는 다음 두번째 문자는 이미 A이므로 좌측이동이아닌 우측이동으로 맨끝지점으로 한번에..
[그리디] 체육복 - Java코드
2021. 7. 27. https://programmers.co.kr/learn/courses/30/lessons/42862?language=java 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 문제 접근법 전체사람 중, 잃어버린 사람을 제외하고, 그들중, 빌릴 수 있는 경우마다 count해서 정답을 반환해주어야겠다. 나는 리스트를 이용하면 빌려준 사람들의 요소를 삭제할수있기 때문에 좋을것같다는 바보같은 생각을 했다. 포인트 예제에는 존재하지 않지만, 잃어버린 사람들중 여벌을 가지고 있을수 있다. 그런 경우를 대비하여, 잃어버린 ..
[완전탐색] 카펫 - Java 풀이
2021. 7. 27. https://programmers.co.kr/learn/courses/30/lessons/42842 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 programmers.co.kr 문제 접근법 들어온 두 값의 합이 카펫의 수이고, 카펫수를 인수분해하여 경우의 수를 검사하여 가로세로 크기를 맞춰야 한다. 풀이 public static int[] solution(int brown, int yellow) { int[] answer = {0,0}; int sum = brown+yellow; for(int x=2; x
[완전탐색] 소수찾기 - Java 풀이, 순열 포인트,★★
2021. 7. 27. https://programmers.co.kr/learn/courses/30/lessons/42839?language=java 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 문제 접근법 이것은 순열이 필요해 보인다. 모든 경우에 수로 순열로 만들고, 중복을 제거 해야 한다. (HashSet에 담으면 해결될것 같음) 중복 제거된 리스트에서 소수를 찾아서 count 해주면 끝! 포인트 1. 순열을 만드는 메소드의 구현 (그동안 순열 조합 코드를 안해봐서 이번기회에 외울 예정) 2. 소수검사는 아리..
[완전탐색] 모의고사 - Java 풀이
2021. 7. 27. https://programmers.co.kr/learn/courses/30/lessons/42840 코딩테스트 연습 - 모의고사 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 programmers.co.kr 문제 접근법 완전탐색, 브루트포스는 결국 모든 경우에 수를 따져야하는 알고리즘이이다. 풀기 위해서는 무식해보이는 코딩을 할 수 밖에 없다. 1. 학생별로 반복되는 패턴을 배열에 담아서 맞춘수를 카운트해주고, 2. 맞춘수 중에서 Math.max를 이용해 최댓값을 구해, 제일 많이 맞춘 학생들을 추려내서 배열에 넣어준다. 3. 배열은 크기를 지정해야하는 특성상 정답..

티스토리툴바