본문 바로가기

전체 글

 (336)
프로그래머스 - N으로 표현 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/42895 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정말 수준높은 DP문제라고 생각한다. 동적계획법은 언제나 어렵고 나를 힘들게한다.. 먼저 이 문제 분류를 통해 동적계획법을 알고 들어가긴 했지만 DP를 써야하는 이유는 역시나 이전의 값을 다시 재사용하게 된다는 점이다. 처음 접근할 때 DP[1]~ DP[32001] 를 각 N이 만들 수 있는 점화식을 구하여 보려 했으나 44퍼센트에서 틀렸다.. 아주 어림없는 도전은 아니었다고 생각하는데 아쉽다. ..
백준 - 1525번 퍼즐(C++) https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 퍼즐의 모든 상태를 queue에 넣어서 관리하는 것이 관건인 문제이다. 퍼즐을 2차원 배열이나 벡터로 만들어 관리하면 되는 문제이지만 이렇게 진행할 경우 방문처리를 진행하는 것이 쉽지 않고 무엇보다 이 문제는 메모리를 상당히 조금 주기 때문에 메모리 초과가 날 가능성이 매우높다. 먼저 방문처리는 겨우 3x3배열이기 때문에 9자리라서 문자열을 사용한 map을 사용하였다. (set도 가능하다. set이 더 좋을듯.) 그리고 중요한 퍼즐관리인데, 퍼즐을 2차원 벡터로 보관하지말고..
백준 1823번 수확 (C++) https://www.acmicpc.net/problem/1823 1823번: 수확 첫째 줄에 벼의 개수 N(1 ≤ N ≤ 2,000)이 주어지고 두 번째 줄부터 N+1번쨰 줄까지 벼의 가치 v(i) (1 ≤ v(i) ≤ 1,000) 가 주어진다. www.acmicpc.net 비슷한 문제를 몇 개 풀어본적이 있어서 비교적 쉽게 풀 수 있었다. 최댓값을 보고 생각해야하는 것은 bfs이다. 그러나 N의 개수를 보고 빠르게 접는다. 양방향을 보고 생각해야하는 것은 투포인터, 이분탐색, dp이다. 그리고 모든 방법을 고려해야하기 때문에 이분탐색과 투포인터는 제외시켜야한다. 그래서 남는 선택지는 dp이다. 두가지 선택지가 존재한다. 앞을 먼저 수확하거나 뒤를 먼저 수확하거나. 이것을 코드로 바꿔보면 dp[left..
백준 9024번 두 수의 합(C++) https://www.acmicpc.net/problem/9024 9024번: 두 수의 합 프로그램은 표준입력으로 입력을 받는다. 프로그램 입력은 t 개의 테스트 케이스로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 t 가 주어진다. 두 번째 줄부터 두 줄 www.acmicpc.net 문제를 보자마자 이분탐색 투포인터가 떠올라야한다. 난 누적합도 떠올랐는데 이 문제는 모든 조합을 확인하면 TLE임을 알았고 간격의 차이에 따라 계산을 걸러낼 수 있는 양 끝 시작 투포인터를 사용해야한다고 생각했다. 2 3 10 14 29 가 있다고 하자. 그렇다면 두 수의 합은 lo++를 할 수록 커지고 hi-- 할수록 작아진다. 그러므로 두 수의 합이 k보다 작다면 더 크게 만들어 줘야하니까 lo..
VScode Git 계정 이름 바꾸기 VScode 에서 Private 레포지토리를 클론해야할 일이 생겼다. 어떠한 이유로 내 깃허브 계정이 아닌 그 Private 레포지토리의 주인의 깃허브 계정을 받아 클론해야했는데 VScode 에서 그 계정으로 로그인 했는데도 깃클론이 되지 않았다. VScode 에서 사용자는 아직 나였기 때문이다. 그래서window 자격증명에서 github 연동을 지우고 나서야 새로운 계정의 자격이 내 PC에 부여되었다.
API 최적화1 - N + 1 문제, Lazy 메커니즘, 패치조인 N + 1 문제 Ex) 주문내역 엔티티는 회원 엔티티와 상품정보 엔티티 두개를 가지고 있다고 해보자 이 때, 주문내역 엔티티를 조회하면 어떻게 될까? 만약 3개의 주문내역이 있다고 생각해보자 그렇다면 결과는 3개가 나와야한다. 즉, 조회된 엔티티의 개수(N)만큼 추가적인 쿼리가 발생하는 문제를 뜻한다. 주문내역 엔티티를 구하기 위한 질의를 던진다. 주문내역에 회원 엔티티를 구하기 위한 질의를 던진다. 상품정보 엔티티를 구하기 위한 질의를 던진다. 지금 주문 내역 엔티티를 구하기 위해 쿼리가 2개가 더 날아갔다. 이것이 1 + N 문제이다. 하나의 쿼리면 될 것을 몇개나 더 날린다. 그리고 주문내역이 3개 있으므로 이 엔티티는 무려 7개의 쿼리를 날려야한다. 단순히 생각해도 네트워크 통신이 많다. 왜 이럴..
백준 25401번 카드 바꾸기 (C++) https://www.acmicpc.net/problem/25401 25401번: 카드 바꾸기 $N$개의 카드가 놓여있다. 편의상 가장 왼쪽에 있는 카드를 $1$번 카드, 그 다음에 있는 카드를 $2$번 카드 $\dots$, 가장 오른쪽에 있는 카드가 $N$번 카드라고 하자. $N$개의 카드에는 각각 정수가 하 www.acmicpc.net 수학적인 테크닉이 조금 필요한 문제이다. 일정하게 증가,감소 수열을 만들어야하기 때문에 처음 떠오른 방식은 dp, 이분탐색이었다. 1. DP : 내가 DP를 잘 못하기도 하고 어떻게 점화식을 짜야할지 감이잡히지 않았다. 2. 이분탐색: 숫자의 범위가 -100만~ 100만이기 때문에 이분탐색을 떠올리고 가장 최적의 증가, 감소치를 찾으면 될 것이라 생각하였으나. 만약 4..
백준 2758번 - 로또(C++) https://www.acmicpc.net/problem/2758 2758번: 로또 선영이는 매주 엄청난 돈을 로또에 투자한다. 선영이가 하는 로또는 1부터 m까지 숫자 중에 n개의 수를 고르는 로또이다. 이렇게 열심히 로또를 하는데, 아직까지 한 번도 당첨되지 않은 이유는 www.acmicpc.net 별로 특별해 보이지 않은 문제였다. 조합을 구하되 조건이 있는 조합이기 때문에 백트래킹으로 가지를 잘 치면 통과할 수 있을 것이라 생각했다. 그러나 계속 시간초과가 났고 구글링 해보니 dp 문제였다. 역시 난 dp가 약하다.. 아무튼, 1 2 4 8 1 2 4 9 1 2 4 10 1 2 5 10 이 가능하다고 할 때, 위 조합을 잘 보면 10개 중 3개를 뽑는 개수를 포함하고 있다. 왜냐하면 10개 중 4..

티스토리툴바