일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
- 3D RPG
- SWEA
- 프로그래머스
- Unity
- Euclidean
- Greedy
- Bronze
- effective C++
- stack
- Project
- C++11
- programmers
- algorithm
- LEVEL2
- Zenject
- Silver
- binary search
- BFS
- smart pointer
- knapsack Problem
- two pointer
- level3
- trie
- Gold
- Modern C++
- level1
- PrefixSum
- algoritm
- 8-Puzzle
- BOJ
- Today
- Total
목록전체 글 (154)
Patrick's Devlog
1. 개요 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 1-1. 설명 10,000 이하 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중 그 합이 S 이상이 되는 것중, 가장 짧은 길이를 구하는 프로그램을 작성한다. 1-2. 제한 사항 - 첫 줄에 N과 S가 주어지며, N은 1 이상 100,000 이하, S는 1 이상 100,000,000 이하 - 둘째 줄에는 수열이 주어짐 2. 구현 2-1..
1. 투 포인터 알고리즘 투포인터 알고리즘 or 슬라이딩 윈도우라고 부르며, 배열에 순차적으로 접근해야 할 때 두 개의 점 위치를 기록하며 처리하는 알고리즘이다. 정렬되어 있는 두 리스트 합집합에도 사용된다. 문제 상황에 맞게 투 포인터를 적절히 사용하면 된다. 정확한 사용법은 아래의 예제를 확인해보자. 2. 특정 합을 가지는 부분 연속 수열 찾기 예제 특정 숫자의 배열이 주어질 때, 해당 배열의 연속 수열 합이 특정값을 가지는 것을 확인하는 문제이다. 앞 전에 풀었을땐, 완전 탐색으로 했으나 이번에는 투 포인터 알고리즘을 사용해보았다. 대략적인 순서는 우선 start와 end를 0으로 초기화 한 후, 현재 부분 배열 합이 특정값과 동일하면 count를 하나 올려준다. 그러나, 현재 부분 배열 합이 특정..
1. 개요 https://www.acmicpc.net/problem/20920 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 1-1. 설명 이번 영어 시험에서 틀린 문제를 바탕으로 영단어를 암기하려고 한다. 그 과정에서 효율적으로 영단어를 외우기 위해 단어장을 만든다. 단어장의 단어순서는 다음과 같은 우선순위를 차례로 적용하여 만들어진다 - 자주 나오는 단어일수록 앞에 배치 - 해당 단어 길이가 길수록 앞에 배치 - 알파벳 사전 순으로 앞에 ..
1. 개요 https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 1-1. 설명 비어있는 공집합 S가 주어졌을때, 원소 추가, 제거, 체크, 토글 등 여러 연산들을 수행하는 프로그램을 작성한다. 자세한 연산은 위의 링크를 참고한다. 1-2. 제한 사항 - 첫 줄에 수행해야 하는 연산 수 M이 주어지며, M은 1 이상 3,000,000 이하 - 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한줄에 하나씩 주어짐 2. 구현 2-1. 풀이 메모리가 매우 한정적이므, 비트마스킹을 이용해 풀었다..
1. 개요 https://www.acmicpc.net/problem/12919 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 1-1. 설명 A와 B로 이루어진 영단어를 통해 간단한 게임을 만들었다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀때는 다음과 같은 두가지 연산만 가능하다. - 문자열 뒤에 A 추가 - 문자열 뒤에 B를 추가 후 문자열을 뒤집음 주어진 조건을 이용해 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성한다..
1. 개요 https://www.acmicpc.net/problem/4659 4659번: 비밀번호 발음하기 좋은 패스워드를 만드는것은 어려운 일이다. 대부분의 사용자들은 buddy처럼 발음하기 좋고 기억하기 쉬운 패스워드를 원하나, 이런 패스워드들은 보안의 문제가 발생한다. 어떤 사이트들은 xvtp www.acmicpc.net 1-1. 설명 발음이 가능한 패스워드를 만드는 회사가 존재한다. 적당히 외우기 쉬우면서 안전하게 계정을 지킬 수 있는 비밀번호를 생성하기 위해 계획중이다. 높은 품질을 지닌 비밀번호 조건에 맞추어 비밀번호가 입력되었을 때, 높은 품질인지 확인하는 프로그램을 작성한다. 1-2. 제한 사항 - 여러개의 테스트 케이스로 이루어져 잇으며, 각 줄에 테스트할 패스워드가 주어짐 - 마지막 테..
1. 개요 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 1-1. 설명 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고있다. 어느날 이 N명의 학생이 X번 마을에 모여 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있으며, i번째 길을 지나가는데 T_i의 시간을 소비한다. 각각 학생들은 파티에 참석하기 위해 걸어서 다시 마을로 돌아와야 한다. 이때, 최단 시간에 오고가기를 원할 때 ..
1. 개요 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 1-1. 설명 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성한다. 방문할 수 있는 정점이 여러개 일 시, 정점 번호가 작은것을 먼저 방문하고 더이상 방문할 수 없는 경우 종료한다. 1-2. 제한 사항 - 첫 줄에 정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점 번호 V가 주어짐 - N은 1 이상 1,000 이..