hyowonii의 블로그

문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 이전 순열의 개수를 구한 다음 그 결과를 이용해 현재까지의 순열 개수를 구하는 방식으로 풀 수 있음 => dp 자신 이전의 자신보다 작은 숫자들 중 dp값이 가장 큰 값으로 자신의 dp값을 갱신해주면 됨 자신 이전의 값들의 dp값은 자신보다 작은 연속된 순열의 개수를 뜻하기 때문 dp 갱신 조건: 자신보다 값..

https://school.programmers.co.kr/learn/courses/30/lessons/12973 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 처음에는 앞에서부터 문자열을 돌면서 겹치는 두 문자가 나오면 그 두 개를 삭제하고 다시 앞으로 돌아가서 순회하는 방식으로 구현했는데, 시간초과가 발생했다.(효율성 꽝) 그런데 다른 구현 방법이 생각이 안나서.. 결국 서치를 해봤다. 🎈Key Point🎈 Stack 사용 앞에서 실패했던 로직에서 중간에 비교 -> 삭제 -> 비교 .. 의 프로세스를 줄여야 했다. 중간에 중복된 숫자를 지우..

https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net 문제 조합의 결과의 끝자리 수에 나오는 0의 개수를 세면 된다. 예제1) 25C12 = 5200300 => 끝자리 0의 개수는 2개 해설 🎈Key Point🎈 끝자리 0의 개수를 구하라는 의미는 조합의 결과에 10이 몇 번 곱해져 있는지를 세면 된다는 의미인 것 같다. a)분모의 10의 개수, b)분자의 10개수를 각각 구한 후 a-b를 구하고자 하였다. 10의 개수를 구하는 방법은 5의 개수와 2의 개수를 구한 다음 둘 중 작은 수를 선택하면 그것이 10..

https://programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 문제 해설 🎈Key Point🎈 순열 => next_permutation 나는 순열이 너무 약한 듯하다 ㅜㅜ 더 연습하자..! 여러번의 실패를 맛봄. 시행착오를 겪은 후 해결한 과정을 대충 적어보면 1. 주어진 numbers에 next_permutation만 돌려서 수행 => numbers의 일부 숫자로 이루어진 경우의 수 못 잡아냄 (ex. 01..

https://programmers.co.kr/learn/courses/30/lessons/1835 코딩테스트 연습 - 단체사진 찍기 단체사진 찍기 가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 programmers.co.kr 문제 해설 경우의 수를 계산하는 방법이 잘 떠오르지 않아 애먹었는데, 이 문제에서는 프렌즈 8명, n의 값이 최대 100으로 최대로 나오는 경우의 수가 8! * 100 = 4,032,000 이므로 그렇게 크지 않다. 따라서 프렌즈가 이룰 수 있는 모든 수열의 경우의 수를 확인하여 조건에 맞는지 체크하는 방법을 사용하면 된다! 🎈Key Point🎈 next_pe..

https://programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,-15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 문제 해결 사실 프로그래머스는 문제 풀이 유형이 사전에 다 보여서,, 그리디를 활용하여 어떻게 푸는지만 생각하면 된다. 그런데 그리디는 왜이리도 익숙해지지 않는지ㅠㅠ 어려운 유형은 아닌 것 같으면서도 막상 풀려고 하면 못풀겠는 그런,, 우선 내가 해결한 방식도 어렵진 않기 때문에 코드부터 보자. 🧨미리 말하자면, 필요없이 길어 그리 좋은 코드는 아닌듯싶다. 밑에 더 간단하고 좋은 코드도 첨부함! #include #include #include using namesp..

https://programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 문제 주어진 문자열을 문자 1개 / 2개 / ... 단위로 나누어 압축하여 표현했을 때 가장 짧은 길이가 되는 경우를 구하는 문제이다. ex) ababcdcdababcdcd의 경우 문자 1개를 단위로 하면 압축이 불가능하고, 2개로 하면 2ab2cd2ab2cd -> 12자리, 8개로 하면 2ababcdcd -> 9자리이므로 가장 짧은 경우는 8개를 기준으..

이번 포스팅은 Unity 프로젝트에서 VR raycaster를 구현하는 방법에 대해 정리한 내용이다. Raycaster는 수많은 광선(ray)를 쏴서(casting) 각 광선과 공간 상에 존재하는 물체 간의 접촉이 있는지 계산하는 모듈이다. 게임에서 주로 볼 수 있고, 레이저 포인터를 활용한 이벤트 수행을 가능하게 한다. 이 포스팅은 VR 기기를 사용할 준비와 세팅은 되어있다는 전제 하에 Raycaster를 구현하는 법만 설명할 것이다. 또한, 레이저 포인터와 상호작용할 UI도 이미 구현되어 있다고 가정한다. 우리는 VR기기를 사용하기 전 2D로 프로젝트를 진행할 때 만들었던 UI를 3D의 World space 공간으로 옮겨와 사용할 것이기 때문에 이 포스트에서 UI 제작에 대한 내용은 언급하지 않는다...

https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 문제 해결 처음 생각 : 이차원 배열 board[][]에 가장 초기 파이어볼들의 위치를 저장 -> 각 파이어볼들에 대해 이동을 수행 -> 겹치는 파이어볼들에 대해 처리 그래서 board[][]를 선언하고, i번 파이어볼의 질량, 속력, 방향을 각각 m[i], s[i], d[i]에 저장하는 식으로 질량, 속력, 방향에 대한 배열을 따로 선언한 뒤 진행했다. 여..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 해결 원소를 차례로 돌면서 현재의 값을 더하거나, 더하지 않고 여태까지의 원소의 합을 구하면 모든 부분수열의 합을 구할 수 있다. 그 중에서 입력한 값과 동일한 값을 가진 부분수열의 개수를 구하면 된다. 🎈Key Point🎈 백트래킹 [전체 코드] #include using namespace std; int n, s; int arr[20]; int resu..