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

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 백준 동적계획법1 단계별 풀기 마지막 문제인 평범한 배낭 문제를 풀어보았습니다 ㅎㅎ 풀다가 도저히 모르겠어서 아래 사이트를 참고해서 풀이했습니다. (설명도 매우 잘되어있었습니다.!) https://fbtmdwhd33.tistory.com/60 [백준,BOJ 12865] 평범한 배낭(JAVA 구현) -내 생각 이 문제의 경우 혼자 풀..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 백준 동적계획법1 (dp) 단계별 풀기에 있는 연속합 문제를 풀어봤습니다. ㅎㅎ [입력 단계] dp[] 에는 해당 인덱스까지의 최댓값을 담도록 합니다. arr[] 에는 입력 숫자를 받습니다. [반복문 단계] 현재 인덱스까지의 연속된 합과(dp[i-1] + arr[i]) 현재 값을(arr[i]) 비교합니다. 현재 인덱스보다 지금까지의 연속합이 더 작으면 최대값dp를 바꿔주도록 하고 아니면 현재인덱스까지의 연속..

보호되어 있는 글입니다.

https://programmers.co.kr/learn/courses/30/lessons/42629 코딩테스트 연습 - 라면공장 라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니�� programmers.co.kr 오랜만에 알고리즘을 풀어봤습니다. Level2 에 heap 문제입니다. 자바에서는 힙을 우선순위큐로 구현합니다. (PriorityQueue) * 밀가루가 0개일때 지급받을 밀가루가 없는 경우는 없다고 가정합니다. [첫날부터 목표날인 k까지 반복문을 돌립니다.] 1. 지급날짜인 경우 내림차순인 우선순위 큐에 밀가루를 추가합니다. 2. 밀가루 재고가 0인 경우 큐..

https://programmers.co.kr/learn/courses/30/lessons/42884?language=java 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 프로그래머스 LEVEL3 의 단속카메라 문제를 풀어봤습니다. ㅎㅎ 풀이 방법은 다음과 같습니다. 1. 종착지점을 기준으로 오름차순 정렬합니다. 2. 반복문을 통해 routes를 갖고옵니다. 3. 카메라 설치 지점과 현재 route의 진입 지점과 비교하여 카메라 설치 지점에 커버되는 곳이면 PASS 아닌 경우는 카메라 설치 지점을 현재 route 의 종착 지점으로 변경해주고 카메라 설치 개수가 한개 늘어납니다. 풀이는 다음과 같습니다. [Jav..

https://programmers.co.kr/learn/courses/30/lessons/43164#qna 코딩테스트 연습 - 여행경로 [[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO] programmers.co.kr 프로그래머스 LEVEL3의 여행경로 문제를 풀어봤습니다.ㅎㅎ 이전 문제와 마찬가지로 탐색문제인데요. 이전 문제가 BFS 여서 그랬는지 BFS로도 풀 수 있겠다 싶어 처음에 BFS 로 접근했습니다. 솔직히 풀면서 너무 더러워져서 DFS 가 낫겟다 싶었는데 이왕 시작한거 끝을 볼려고 계속 풀었습니다...;; 코드는 다음과 같았는데요. 하지만 주어진 테스트케이스는 다 맞는데 제출시 ..

https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 프로그래머스 LEVEL3 단어 변환 문제를 풀어봤습니다. bfs 를 사용해서 풀이했습니다. 한 단어는 한 글자만 변경이 가능한 경우 변경할 수 변환할 수 있습니다. (탐색 조건) 1. 큐에 시작 단어를 넣습니다. 2. 단어들을(words) 불러오고 이미 사용한 단어가 아닌 경우 현재 단어와 한글자씩 비교하고 변환이 가능..

https://github.com/mtjin/algorithm_practice/tree/master/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC%20-bfs%2Cdfs- https://programmers.co.kr/learn/courses/30/lessons/43162?language=kotlin 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있�� programmers.co.kr BFS 를 사용하여 처음 연결된 ..

https://programmers.co.kr/learn/courses/30/lessons/12913?language=java 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟�� programmers.co.kr 프로그래멋 LEVEL2의 땅따먹기 문제를 풀어봤습니다 ㅎㅎ dp 로 바로 접근하고 복잡한 문제가 아니라 빠르게 풀 수 있었습니다. 풀이는 다음과 같습니다. [Java] class Solution { int solution(int[][] land) { int answer = 0; for (int i = 1; i < ..

https://programmers.co.kr/learn/courses/30/lessons/42888?language=kotlin 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr 프로그래머스 LEVEL2 문제 오픈채팅방을 풀어봤습니다. ㅎㅎ 문제 풀이법은 HashMap으로 풀어야겠다고 바로 생각나서 쉽게 접근할 수 있었습니다. 1. HashMap 으로 마지막으로 추가 혹은 변경된 이름을 저장하게 합니다. uid를 key로 이름을 value로 2. 출력 문장을 만들어 줍니다. Levae는 두 단어인거 주의 3...

https://programmers.co.kr/learn/courses/30/lessons/49994?language=java 코딩테스트 연습 - 방문 길이 programmers.co.kr 프로그래머스 LEVEL3 의 방문 길이 문제를 풀어봤습니다 ㅎㅎ 처음에 별생각없이 좌표를 칸으로 취급하고 바로 2차원 배열의 map, isVIsisted 하고 bfs queue 로 접근해서 풀었는데 한문제만 맞고 나머지 한문제는 틀리고 오답이 나왔었습니다. 바로 위와 같이 7번처럼 방문이 안되야하는데 된걸로 되서 잘못풀었단거를 꺠달았습니다. 그래서 어디서 어디로 왔는지 알아야했습니다. 이를 4차원 배열을 이용해서 풀었습니다. 1,2 차원 지점에서 3,4차원지점으로 이동했다는 것을 기록합니다. 문제 풀이방법이 더 간단해..

https://programmers.co.kr/learn/courses/30/lessons/42578?language=java 코딩테스트 연습 - 위장 programmers.co.kr 프로그래머스 LEVEL2 의 해시 유형 문제를 풀어봤습니다. ㅎㅎ 처음에 해시로 접근할 때 value 값을 List로 할려했는데 생각해보니 같은 옷이 나오는 경우는 생각을 안해도 되서 key 값은 옷의 종류, value 값은 해당 옷 종류의 옷 개수로 설정해서 쉽게 풀 수 있었습니다. hash 문제를 풀때 getOrDefault() 함수를 참 많이 사용하는 거 같습니다 저같은 경우는.. 그리고 이 문제에서는 확률과 통계 지식도 필요했는데요. 다음과 같이 이 문제 수학지식에 대해 잘 설명해논 글이 있어 가져와봤습니다. !! ..

https://programmers.co.kr/learn/courses/30/lessons/43165?language=java 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 프로그래머스 LEVEL2 의 타겟넘버를 풀어봤습니다. ㅎㅎ + 일떄와 - 일때 두가지 경우로 재귀를 돌려 결과값이 타겟넘버라면 개수를 1 증가시키게 풀었습니다. 문제풀이는 다음과 같습니다. [Java] class Solution { private static int target; pr..

https://programmers.co.kr/learn/courses/30/lessons/12952?language=kotlin 코딩테스트 연습 - N-Queen 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 programmers.co.kr 프로그래멋 LEVEL3 의 백트래킹 유형의 N-Queen 문제를 풀어봤습니다. 예전에 백준에서도 풀었었는데 아마 백트랙킹의 대표적인 문제라 프로그래머스에도 있는 것 같습니다. 복습할겸 다시한번 풀어봤습니다 ㅎㅎ 풀이는 다음과 같습니다. [Java] class Solution { public static int N; pu..

https://programmers.co.kr/learn/courses/30/lessons/12973 코딩테스트 연습 - 짝지어 제거하기 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙 programmers.co.kr 프로그래머스 LEVEL2 의 짝지어 제거하기 문제를 풀어봤습니다. ㅎㅎ 처음에 문자열로 비교해서 양쪽이 같은 경우도 제거해주는 건줄 알았는데 아니었고 한 단어로만 비교해주면 되는 문제이기 때문에 스택으로 쉽게 풀 수 있었습니다. 풀이는 다음과 같습니다. import java.util.Stack; class Solution { public int so..