목록전체 글 (344)
![](http://i1.daumcdn.net/thumb/C200x200/?fname=https://blog.kakaocdn.net/dn/cY7kDt/btsE8M2igcn/cJ8TOOSTcNCRolMnBgZLRK/img.png)
https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS문제이다. 기존 알고리즘대로 푼다. 행렬 DP를 만들어준다. ACAYKP CAPCAK A C A Y K P 0 0 0 0 0 0 0 C 0 0 1 1 1 1 1 A 0 1 1 2 2 2 2 P 0 1 1 2 2 2 3 C 0 1 2 2 2 2 3 A 0 1 2 3 3 3 3 K 0 1 2 3 3 4 4 이런 행렬표를 얻게 되고 LCS값은 4이다..
![](http://i1.daumcdn.net/thumb/C200x200/?fname=https://blog.kakaocdn.net/dn/bI3XaB/btsEVhOM0Uc/MfTKUKQDJZIKzw0dBMIsVk/img.png)
https://leetcode.com/problems/number-of-subarrays-that-match-a-pattern-ii/description/ LeetCode - The World's Leading Online Programming Learning Platform Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문자열에서 패턴을 찾는 문제이다. 기존에 알고 있던 내용은 찾을 패턴 : AABA 문자열 : AABABAACA 가 있다고 할때 A A B A B A A C A..
![](http://i1.daumcdn.net/thumb/C200x200/?fname=https://blog.kakaocdn.net/dn/bmpwNc/btsEGO7lnMW/w19wKaKF621AwI31uZ7Nn0/img.png)
https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 나에겐 어려운 문제였다. 계속 시간초과 나서 풀이를 확인했다. 시간초과를 해결하는게 핵심이었다. data = [] n = int(input()) def dfs(cur_node, visited): if visited == pow(2, n)-1: if data[cur_node][0] != 0: return data[cur_node][0] else: return f..
![](http://i1.daumcdn.net/thumb/C200x200/?fname=https://blog.kakaocdn.net/dn/c8YVnm/btsEEYW0KlX/UrGTmyseW6pghEARHKdWP1/img.png)
https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 기본기가 중요한 문제였다. 뭔가 기업코테에 출제할만한 문제라고 생각한다. 에라토스테네스의 체로 소수의 수열을 구해주었다. 그 후 투포인터로 수열의 합을 구했다. 수열의 합을 구할때는 시간을 더 아끼기 위해 누적합을 이용했다. q가 오른쪽 포인터 p가 왼쪽포인터로 구간을 나타낼 수가 있으며 q가 올라가면 더해주고 p가올라가면 원래 자리에 있던 수를 빼준다. #include #include #include using namespace std; int main() { int n; cin >> n; if (n == 1) {..
![](http://i1.daumcdn.net/thumb/C200x200/?fname=https://blog.kakaocdn.net/dn/bkwBS7/btsEyRKfZcj/M6cRKpNSiKaKLG4Kag4Q5k/img.png)
https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 $n$, $m$, $k$가 주어진다. ($1 ≤ n ≤ 1\,000$, $0 ≤ m ≤ 2\,000\,000$, $1 ≤ k ≤ 100$) $n$과 $m$은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이 www.acmicpc.net c++복습할 겸 풀어보았다. 당분간 c++로 풀 것 같다. 다익스트라를 변형해서 푸는 문제이다. 지속적으로 최단거리를 가져와 최신화를 하는 게 정석이지만 이번에는 거리 데이터를 끝까지 가져가며 관리를 해준다. 정석 다익스트라는 거리 조건문을 통해 큐에 넣었으나 이번에는 k를 이용해서 다익스트라를 진행하게 했다. #inc..
![](http://i1.daumcdn.net/thumb/C200x200/?fname=https://blog.kakaocdn.net/dn/boCKyn/btsDpwtL0ov/m3VhoPyk9Nje5l3AQRtk4k/img.png)
https://school.programmers.co.kr/learn/courses/30/lessons/214288 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2023 현대모비스 알고리즘 경진대회 예선 문제 푸는데 하루를 썼다. 첫 구상은 상담원 배치를 재귀로 돌려 완전탐색 했다. 근데 시간 초과가 나서 product로 구했다. 각 상담원 배치 수를 이용해 계산을 진행한다. 1번 예제로 설명하면 (1, 1, 1) (1, 1, 2) (1, 1, 3) (1, 2, 1) (1, 2, 2) (1, 2, 3) (1, 3, 1) (1, 3, 2) (1, 3, 3..
![](http://i1.daumcdn.net/thumb/C200x200/?fname=https://blog.kakaocdn.net/dn/cjCAcR/btsDoo2qfTJ/Akgd8qLVjmFmCeBWgWTke1/img.png)
https://school.programmers.co.kr/learn/courses/30/lessons/258705 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2024 KAKAO WINTER INTERNSHIP 문제 타일링 문제는 항상 피보나치와 비슷하게 풀었던 경험이 있었다. 이번에도 몇 가지 테스트케이스를 만들어 수들의 연관성을 찾을 수 있었다. [0] = 3 [1] = 4 [0, 0] = 8 [0, 1] = 11 [1, 1] = 15 [0, 0, 0] = 21 도출한 테스트케이스만으로는 유추하기 힘들어 규칙성도 파악하기로 했다. 해당 사진을 예시..
![](http://i1.daumcdn.net/thumb/C200x200/?fname=https://blog.kakaocdn.net/dn/luv7r/btsDhhYpqOI/4B3PkZUO9gwDklKhandkd1/img.png)
https://school.programmers.co.kr/learn/courses/30/lessons/258707 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2024 KAKAO WINTER INTERNSHIP 문제 1. 나의 덱에 있는 요소들로 라운드 진출 가능한 경우 2. 나의 덱 하나와 coin 하나 써서 라운드 진출 가능한 경우 3. coin 두 개 써서 라운드 진출 가능한 경우 4. 모두 통과 못하면 최대 라운드이다. 라운드마다 두장의 카드는 바로 temp_card에 넣어두고 필요할 때 coin을 쓰고 temp_card에서 빼가기로 했다. s..