ps

주어진 문자열에 정수들이 공백을 사이에 두고 주어진다. 공백이 아닌 문자를 버퍼에 추가하다가 문자가 공백 혹은 마지막 위치의 문자일 경우, 버퍼를 정수로 변환하고 최댓값, 최솟값을 갱신한 후에 다음 정수를 입력받기 위해 버퍼를 초기화한다.https://scho

두 배열의 원소를 하나씩 곱하여 더했을때 최소인 값을 만들어내야 한다.완전 탐색으로 수행하면 O(N!)이 소요되고 (1$\\leq$ N $\\leq$ 1000) 이므로 불가능하다.직관적으로 큰 수를 작은수들과 우선적으로 곱했을 때 결과가 더 작아진다는 걸 알 수 있으므

단어의 첫 문자를 대문자, 그 외는 모두 소문자로 바꿔야 한다.각 단어는 공백으로 구분되므로 공백을 만날 때마다 그 다음 문자만 대문자로 바꾸고 그 외는 모두 소문자로 바꿔주도록 한다.https://school.programmers.co.kr/learn/cou

정수 N을 이진수로 나타냈을 때, 양쪽에 1이 있고 모든 원소가 0인 부분 리스트들 중 가장 긴 것의 길이를 구하는 문제.N이 10010000와 같은 꼴일 때, 오른쪽에 1이 없는 경우를 제외하기 위해 N이 홀수가 될 때 까지 나누어준다. (10010000 -> 100

스택을 이용해 여는 괄호와 닫는 괄호 개수 세며 검사https://school.programmers.co.kr/learn/courses/30/lessons/12909

간단한 구현문제. 제시된 대로 작성하면 된다.https://school.programmers.co.kr/learn/courses/30/lessons/70129cpp code

$$n$$과 일치하는 자연수의 연속합을 구하는 문제.$$n$$의 크기가 최대 $$10^4$$이기 때문에 $$O(n^2)$$인 브루트포스로 구현해도 시간초과가 발생하지 않지만 투 포인터를 이용하면 더 빠르게 $$O(n)$$으로 해결가능하다.https://scho

K만큼 오른쪽으로 쉬프트된 배열을 반환해야 하는 간단한 문제.K가 A보다 클 때 미리 나머지 연산을 하면 불필요한 반복을 줄일 수 있다.$$ret{i}$$ = $$A{i-k}$$https://app.codility.com/demo/results/training

https://school.programmers.co.kr/learn/courses/30/lessons/12911cpp code

https://school.programmers.co.kr/learn/courses/30/lessons/12945cpp code

배열 내의 같은 값을 원소 중에서 짝을 이루지 못하는 원소의 값을 반환하는 문제.등장한 값들의 개수를 카운트하여 홀수개수를 찾아내는 방식으로 해결했다.원소값의 범위가 $$0$$~$$10^9$$이기 때문에 배열을 사용하면 메모리 초과가 발생하므로 map을 사용했다.마지막

문자열S가 주어졌을 때, 같은 값의 이웃 문자를 제거하고 그 사이를 이어붙이는 동작을 반복하여서 빈 문자열로 만들 수 있는지 확인하는 문제.처음에는 방문처리를 이용해 짝이 더이상 생기지 않을때까지 문자열의 모든 원소를 짝검사 하는 방식으로 접근했다. S의 길이는 최대

갈색격자와 노란색격자의 개수가 각각 주어졌을 때, 가로와 세로 길이를 구하는 문제.갈색 격자의 개수는 테두리 길이의 합이고 노란색 격자의 개수는 총 격자 개수에서 테두리격자 개수만큼 뺀 것이므로 다음과 같은 식을 얻을 수 있다.$$brown = 2Width + 2Hei

주어진 배열을 이용해 끝말잇기를 진행하다가 진 사람의 번호와 차례를 얻어야 하는 문제.set를 이용해 방문처리를 해주고 틀린 사람이 나왔다면 나머지 연산과 나눗셈 연산을 적절히 활용하여 해결하면 된다.https://school.programmers.co.kr/

주어진 리스트를 두 개로 분할했을 때, 각 리스트별 원소값 총합을 구하고 총합 차이가 가장 작을 때 그 차이가 얼마인지 구해야 하는 문제.하나의 변수에는 0, 또 다른 변수에는 주어진 리스트 A의 총합을 대입해둔다. 그 후에 A를 순회하며 값을 넣고 빼고 비교하면서 최

무게 제한이 있고 최대 2명 태울 수 있는 보트의 최소 개수를 구하는 문제.처음에는 무게순으로 정렬한 후에 투포인터로 해결하려 했으나 TLE가 나왔다. 제한사항을 잘 살펴보니 사람의 무게 범위는 40~240이라고 명시되어 있어서 굳이 정렬할 필요가 없었고 값의 하한과

k비용으로 k만큼 이동 (k > 0)0비용으로 현재 이동한 거리의 두 배만큼 이동위의 두 동작을 적절히 이용하여 최소 비용으로 n에 도착하는 문제처음에는 bfs로 접근했었는데 N의 최대가 $$10^9$$인 탓에 TLE가 나와버렸다. 한참 헤맸었는데 해법은 의외로 정말

총 n명의 선수가 있는 토너먼트의 a번째 선수와 b번째 선수가 몇 번째 라운드에서 만나는지 찾아내야 하는 문제.우선 총 라운드 수를 log2(n)으로 구하고 대진표의 결승전부터 탐색하도록 했다.n을 절반으로 나눴을 때, a와 b가 서로 다른 구역에 있는지 여부를 통해

주어진 배열 속 모든 원소의 최소공배수를 구하는 문제.두 수의 최소공배수는 두 수를 곱한 수를 두 수의 최대공약수로 나누는 것으로 구할 수 있다.https://school.programmers.co.kr/learn/courses/30/lessons/12953c

점프를 한 칸 또는 두 칸 뛸 수 있을 때, n에 도달할 때까지 나올 수 있는 모든 경우의 수를 구하는 문제.메모이제이션으로 간단하게 해결 가능하다. foo(i)는 i에서 n까지 가면서 나타날 수 있는 모든 경우의 수를 반환한다.경우의 수가 int의 범위를 초과할 수

귤을 크기별로 분류한 후에 최대한 다른 종류가 적도록 하면서 k개를 고른다면 최소 종류는 몇 개인지 구하는 문제.개수가 가장 많은 종류부터 귤을 담으면 최소 종류로 귤을 담을 수 있다.https://school.programmers.co.kr/learn/cou

주어진 배열의 원소들이 순열을 이루는지 확인해야 하는 문제.중복을 검사하고 방문 횟수와 배열 내 최댓값을 비교해서 순열을 이루는지 확인한다.https://app.codility.com/programmers/lessons/4-counting_elements/pe

배열의 몇 번째 원소까지 방문해야 1~X가 모두 등장하게 되는지 확인하는 문제.방문검사를 이용해 해결한다.https://app.codility.com/programmers/lessons/4-counting_elements/frog_river_one/

배열 A 내 원소값이 0인 인덱스를 P, 1인 인덱스를 Q라고 했을 때, (P < Q)를 만족하는 쌍의 개수를 구하는 문제.upper_bound를 이용하면 P가 주어졌을 때, 유효한 Q의 개수를 바로 구할 수 있다.https://app.codility.c

배열 내 등장하는 값이 몇 개인지 구하는 문제.방문처리에 배열을 사용했는데 등장하는 값의 범위에 음수가 있으므로 $$10^6$$만큼 더해준 값을 이용했다.https://app.codility.com/programmers/lessons/6-sorting/dist

배열 A에서 세 개의 원소를 골라 곱한 결과들 중 가장 큰 값을 구하는 문제.원소값의 범위에 음수가 포함되어 있으므로 최대값을 구하기 위해서 두 가지 경우를 체크하면 된다.절대값이 가장 큰 세 개의 양수절대값이 가장 큰 두 개의 음수와 하나의 양수https:/

배열 A가 주어졌을 때 다음 조건을 만족하는 경우가 있는지 찾는 문제.$$0<=P<Q<R<A$$\_$$size$$$$AP + AQ > AR$$,$$AQ + AR > AP$$,$$AR + AP > AQ$$비슷한 크기의 값들만 비교하더라도 만족 여부를

물고기의 크기를 나타내는 배열 A와 물고기의 방향을 나타내는 B가 주어졌을 때, 마지막에 살아남은 물고기의 수를 구하는 문제.스택을 이용하여 연속으로 같은 방향의 물고기들이 나오는 경우를 체크해준다.https://app.codility.com/programme

10일 동안의 할인 품목들로 원하는 물품을 모두 구매할 수 있는 경우의 수를 구하는 문제.Map을 이용해 원하는 물품이 등장한 횟수를 관리한다. 원하는 물품이 아닌 경우에는 결과에 영향을 미치지 않으므로 카운트하지 않아도 된다.https://school.pro

정수 n, left, right가 주어질 때, 다음과 같은 행렬이 만들어진다.이 때, 0행부터 n-1행을 모두 한 줄로 이어붙이고 left번째부터 right번째까지의 값들을 모두 구하는 문제이다.index가 주어졌을 때, 행과 열은 n으로 나눈 값과 그 나머지 값으로

h번 이상 등장하는 h 이상의 값들 중 최댓값을 구하는 문제.i번째 원소의 값보다 큰 값이 i-1개 만큼 있는지 확인하면 된다. 정렬을 이용하면 i번째보다 큰 값의 개수를 상수 시간 내에 구할 수 있다.https://school.programmers.co.kr

행렬의 곱셈 결과를 구하는 문제.https://school.programmers.co.kr/learn/courses/30/lessons/12949cpp code

도시이름 배열과 cache크기가 주어졌을 때, 비용 계산을 하는 문제.캐시 교체 알고리즘은 LRU인데 이는 Queue와 Map을 같이 적절히 이용하면 구현할 수 있다. Map의 Key 개수를 캐시에 담긴 데이터의 수로 보고 만약 Key의 개수가 cacheSize보다 커

가능한 적은 수의 돌을 써서 주어진 배열 H에 맞게 돌벽을 짓는 문제.낮은 벽에 사용되는 돌이 큰 돌의 받침에도 쓰이도록 했을 때, 항상 최소 개수만이 요구된다는 점을 이용하면 된다.h 크기의 벽 뒤에 더 큰 벽을 쌓고 다시 h 크기의 벽을 쌓아야 한다면 새로운 돌이

배열이 주어졌을 때 가능한 부분수열의 합이 몇 개인지 구하는 문제1부터 배열크기만큼의 부분수열을 모두 구하고 방문 검사를 통해 총 개수를 구하면 된다.https://school.programmers.co.kr/learn/courses/30/lessons/131

세 가지 종류의 괄호로 이루어진 문자열이 주어지고 그 문자열을 회전시킬 수 있을 때, 올바른 괄호 문자열이 되는 경우의 수를 구하는 문제.각 괄호별 여는 괄호 개수와 스택을 이용한 괄호 짝 검사를 통해 문자열이 올바른 괄호 문자열인지 알아낸다.https://s

옷의 이름과 종류가 담긴 배열이 주어졌을 때, 가능한 조합의 수를 구하는 문제.처음에는 백트래킹으로 접근했었는데 모든 옷이 다른 종류일 경우 시간복잡도가 $$O(2^30)$$이 되어버려서 TLE를 받았다.가짓수만 구하는 경우는 굳이 백트래킹할 필요 없이 각 옷의 종류별

주어진 문자열로부터 튜플을 구하는 문제.각 중괄호 안 수열을 MultiSet에 담아두었다가 가장 작은 크기의 MultiSet부터 순회하면서 answer과 겹치는 부분을 erase하고 남은 하나의 원소를 answer에 삽입한다.다른 코드를 보니 각 원소의 등장횟수만을 이

창고에 보관된 토마토가 모두 익는데 걸리는 최소 일수를 구하는 문제.익은 토마토의 위치를 현재큐에 모두 넣는다.현재큐를 순회하며 인접하면서 익지 않은 토마토의 위치를 다음 큐에 넣어준다.만약 다음 큐가 비었다면 더 이상 익을 토마토가 없다는 뜻이므로 5번으로 이동.현재