ps [PS] 큰 수 만들기 (LV2) 큰 수 만들기 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 ... Lv2ps프로그래머스Lv2 [PS] 가장 큰 수 (LV2) 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 ... Lv2ps프로그래머스Lv2 [BOJ/C++] 2563 색종이 - 구현 bojImplementationpsImplementation [PS] 체육복 (LV1) 가장 큰 수 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문... Lv1ps프로그래머스Lv1 [백준 13549 파이썬] 숨바꼭질 3 (골드 5, 다익스트라 or BFS) 알고리즘 유형 : 다익스트라 or BFS 다익스트라 풀이 BFS 풀이 SOLVE 1) 풀이 요약 (다익스트라 풀이) 이 문제는 가중치가 0 또는 1인 그래프로 생각할 수 있다. 가중치가 모두 0 또는 양수이고, 특정 노드에서 특정 노드까지의 최단 경로 가중치를 구하는 것이므로 다익스트라 알고리즘을 적용할 수 있다. 기존의 다익스트라 형태에서 조금 다른 점은, 그래프 간선 정보가 따로 주어지는... 파이썬ps알고리즘다익스트라BFS최단 경로백준코딩테스트BFS 백준 5670번: 휴대폰 자판 자동완성이 안되는 경우는 단어가 완성되는 경우, 혹은 자식이 2개 이상인 경우이다. 모든 단어가 같은 알파벳으로 시작하더라도 처음에는 버튼을 한 번 눌러줘야 한다. 다들 C-style 문자열(const char*)로 trie를 구현하고, 그걸 돌려쓰길래 맘에 안들어서 문자열 레퍼런스랑 인덱스를 넘기는 방식으로 구현했다.... cppTriepsTrie [PS]로또의 최고 순위와 최저 순위 (LV1) 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호가 일치 3 4개 번호가 일치 4 3개 번호가 일치 5 2개 번호가 일치 6(낙첨) 그 외 로또를 구매한 민우는 당첨 번호 발표일을 학수고대하고 있었습니다. ... psLv1프로그래머스Lv1 2018 KAKAO BLIND RECRUITMENT 비밀지도 (lv1) 정답 코드 1 정답 코드 2 배운 점 1. 2진수 비트연산자 2. zip 함수... KAKAO 블라인드 테스트psKAKAO 블라인드 테스트 백준 14891 톱니바퀴 목표 : 톱니바퀴를 K번 회전시킨 후 점수를 구하자. 조건 : 1 <= K <= 100, 톱니바퀴는 8개의 톱니로 구성되어있다. 해결방안 전형적인 구현문제이다. 회전하는 톱니바퀴에 인접한 톱니바퀴의 좌우가 맞물릴 때 서로 다른 극이라면 해당 톱니바퀴도 반대방향으로 회전한다.... psps 2019 KAKAO BLIND RECRUITMENT 실패율 (lv1) 정답 코드 1 정답 코드 2 배운 점 첫 번째 코드에 비해 두 번째 코드의 실행 속도가 많이 빠르다. 시간 복잡도 향상을 위한 고민이 부족하다. dun dun dance 들으면서 코딩하면 좋다.... psKAKAO 블라인드 테스트KAKAO 블라인드 테스트 [백준 10217 파이썬] KCM Travel (골드 1, DP) 전체 문제를 "출발 노드에서 row 노드까지 정확히 비용 column으로 갈 때의 최단 시간"으로 둘 때의 풀이 전체 문제를 "출발 노드에서 row 노드까지 예산 column 내의 비용으로 갈 때의 최단 시간"으로 둘 때의 풀이 SOLVE 1) 풀이 요약 (전체 문제를 "출발 노드에서 row 노드까지 정확히 비용 column으로 갈 때의 최단 시간"으로 둘 때의 풀이) 전체 문제를 "출발 노... 파이썬ps알고리즘냅색최단 경로백준DP코딩테스트DP [백준 1956 파이썬] 운동 (골드 4, 플로이드 워셜) 알고리즘 유형 : 플로이드-워셜(최단 경로) 풀이 참고 없이 스스로 풀었나요? 풀이 요약 플로이드-워셜 알고리즘으로 풀면 pypy3으로 제출해야 통과된다. 다익스트라를 활용하여 풀 수도 있는데, 더 오래 걸리길래 시간복잡도를 비교해봤는데 다익스트라는 노드 수만큼 실행해줘야하니까 2VElogV, 문제의 조건에서 E의 범위가 V^2-V 까지랬으니 대충 V^3logV 정도 되겠다. 플로이드-워셜은... 플로이드 워셜파이썬ps알고리즘최단 경로백준코딩테스트ps [PS]올바른 괄호 (LV2) 올바른괄호 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 "()()" 또는 "(())()" 는 올바른 괄호입니다. ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다. '(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 ... Lv2ps프로그래머스Lv2 [PS]최댓값과 최솟값 (LV2) 최댓값과 최솟값 문자열 s에는 공백으로 구분된 숫자들이 저장되어 있습니다. str에 나타나는 숫자 중 최소값과 최대값을 찾아 이를 "(최소값) (최대값)"형태의 문자열을 반환하는 함수, solution을 완성하세요. 예를들어 s가 "1 2 3 4"라면 "1 4"를 리턴하고, "-1 -2 -3 -4"라면 "-4 -1"을 리턴하면 됩니다. 제한사항 s에는 둘 이상의 정수가 공백으로 구분되어 있습... Lv2ps프로그래머스Lv2 백준 12025 장난꾸러기 영훈 목표 : 영훈이는 장난꾸러기라서 희현이의 비밀번호 중 1은 6으로, 6은 1로 바꾸거나 2는 7으로 7은 2로 바꿔버렸다. 이를 해결하기 위해 희현이는 비밀번호 수열의 숫자 중 1과 6을 모두 1로, 2와 7을 모두 2으로 바꾼 숫자와 1과 6을 모두 6으로 2과 7을 모두 7로 바꾼 숫자 사이에 가능한 경우를 모두 사전순으로 나열한 다음 그 중 k번째 수열인 비밀번호를 찾기로 했다. 멘붕에... psps 프로그래머스 가장 먼 노드 Java 풀이 풀이 해당 문제는 그래프와 그래프 탐색 알고리즘 개념만 알면 상당히 쉬운 문제이다. 필자의 풀이는 인접 리스트를 만들어 각 노드가 연결된 노드들을 리스트에 넣어주고(인접리스트) 너비 우선 탐색을 한다. 방문하지 않은 노드는 방문을 체크할 배열이 있으므로, 방문시 무조건 처음 방문한게 보장이 되므로 그 노드의 level을 배열에 저장한다. 각 노드의 level이 저장된 배열의 max 값을 찾고... 알고리즘psps 백준 13913: 숨바꼭질 4 (파이썬) 정답코드 문제유형 BFS... psps [AtCoder] Beginner Contest 243 (A, B, C) 결과 : D번까지 solve(30:09) || 패널티 : 1회 1회 문제 설명 문제 정의 매일 밤 다카하시네 집에서는 전원이 [아버지, 어머니, 다카하시] 순으로 머리를 감습니다. 이때 [아버지 => A 리터, 어머니 => B 리터, 다카하시 => C 리터] 순으로 각각 사용한다고 했을 때, (누구 차례에 샴푸가 부족할까요?) 입력 및 제약 입력 내 풀이 해설 풀이 1회 문제 설명 문제 정의... psatcoderalgorithmalgorithm [BOJ] 18870번 좌표 압축(Python) 문제를 분석해보면, 중복을 제거한 후 정렬된 리스트에서 각 수에 대응되는 인덱스를 출력하는 문제이다. 매번 인덱스를 찾는 과정을 대신해서 dictionary를 통해 인덱스를 저장했다.... ps정렬bojboj 백준 #1912. 연속합 정리 이 문제도 다이나믹 프로그래밍 기법으로 해결할 수 있는 문제이다. bottom-up 방식으로, 연속합의 최댓값을 비교해서 저장해 두고, 계속 수열을 비교해 나가면서 기존의 연속합의 최댓값과, 새로운 연속합의 값을 비교해 나가는 방식으로 문제를 해결했다. 수열의 숫자는 -1000보다 크거나 같고, 1000보다 같거나 작은 정수이다. 즉, 수열에 음수가 포함될 수 있다. 따라서 각 숫자가 ... ps동적 계획법cpp백준algorithmalgorithm 백준 9020 - 골드바흐의 추측 소수 관련 문제 소수 리스트를 만든다. input값의 절반에 가장 가까운 작거나 같은 소수(a)를 찾고 소수 리스트에서 a의 index값을 찾는다. a와 더해서 input값이 되는 또 다른 소수(b)를 찾는다. 만약 조건에 맞는 b가 없다면 a보다 인덱스가 하나 작은 소수를 찾는다. 3-4를 조건에 맞는 a, b를 찾을 때 까지 반복한다. 처음 문제를 풀 때, 테스트 케이스 하나마다 소수리스... ps백준ps [PS] Union-Find Union-Find 자료구조는 그룹핑하여 자료를 저장하고, 같은 그룹인지 확인할 때, O(logN) 시간 만에 확인이 가능하다. 10의 최종보스가 8의 최종 보스 밑으로 들어간다! 그룹 개수를 구하기 위해서는 기본 코드에서 살짝만 변화를 주면 된다. Cycle 유무를 판단하기 위해서는 제약사항이 존재한다. 단방향그래프는 Cycle 판별 불가, 양방향그래프만 Cycle 판별 가능 cycle 유... psps 백준 7576번 - 앱 배낭 문제 알고리즘으로 풀이할 수 있는 문제다. 앱이 차지하는 메모리 용량이 Ai 소요되는 비용이 C_{i} Ci 라고 쳤을 때 확보해야하는 메모리 용량 M 이상을 확보 했을 때 최소 비용을 구하는 문제다. 그러므로 배낭 문제에 대응 해보았을 때 소요되는 비용이 배낭의 사이즈고, 해당 배낭 사이즈로 가져갈 수 있는 가치의 목록들이 각각의 앱의 메모리 용량이라고 생각하면 된다. 즉 dp배열과 ... ps냅색알고리즘DP백준DP [Python] 백준 1032 명령 프롬프트 제일 처음 N으로 받아올 테스트 케이스의 갯수를 입력 받는다. 입력 받은 테스트 케이스 X의 첫번째는 result에 저장하여 비교 대상으로 저장한다. 이후 for문으로 반복하여 X를 받아오는데 이미 위에서 result로 첫번째 테스트 케이스를 저장하였으니 n - 1번만 반복하여 받아온다. 비교값인 result와 반복하여 얻은 X의 값을 차례로 비교하며 만약 값이 같을 시 해당 값을 '?'로 ... pspython백준algorithmalgorithm 2022 KAKAO BLIND RECRUITMENT 신고 결과 받기 (lv1) 정답코드 다른 정답코드... psKAKAO 블라인드 테스트KAKAO 블라인드 테스트 2019 카카오 개발자 겨울 인턴십 (lv1) psKAKAO 블라인드 테스트KAKAO 블라인드 테스트 [PS] Heap Heap은 Priority Queue로 구현하는 방식이다. PQ : 우선순위부터 꺼내는 트리구조 조건 1 : Perfect Binary Tree Perfect : 노드의 순서가 위쪽 왼쪽 순 Binary : 자식이 최대 2개 Tree : CYCLE이 없는 그래프 조건 2 : 어떤 Node에서 직접 연결된 Node간의 우선순위가 알맞게 연결된 트리 우선순위 : 작은 값 로 변경하면 된다. 구조... psps [백준] 2615번 오목 사용 알고리즘 완전 탐색 + DFS 방향 설정 오목인지 판단을 하기 위해선 한 점에 대해서 총 8방향을 봐야한다. 하지만 2중 for문을 사용할 때, 위에서 아래 / 왼쪽에서 오른쪽으로 탐색을 하게 된다면, 파란색을 칠해진 방향에 대해선 볼 필요가 없다 (중복되기 때문) 5목 판단 DFS 시작 2중 for문을 이용하여 위에서 아래 / 왼쪽에서 오른쪽 으로 탐색을 하다가 0이 아닌 값일 경우,... psbaekjoonalgorithmalgorithm 프로그래머스 : 다리를 지나는 트럭 (파이썬, lv2) psps 이전 기사 보기
[PS] 큰 수 만들기 (LV2) 큰 수 만들기 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 ... Lv2ps프로그래머스Lv2 [PS] 가장 큰 수 (LV2) 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 ... Lv2ps프로그래머스Lv2 [BOJ/C++] 2563 색종이 - 구현 bojImplementationpsImplementation [PS] 체육복 (LV1) 가장 큰 수 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문... Lv1ps프로그래머스Lv1 [백준 13549 파이썬] 숨바꼭질 3 (골드 5, 다익스트라 or BFS) 알고리즘 유형 : 다익스트라 or BFS 다익스트라 풀이 BFS 풀이 SOLVE 1) 풀이 요약 (다익스트라 풀이) 이 문제는 가중치가 0 또는 1인 그래프로 생각할 수 있다. 가중치가 모두 0 또는 양수이고, 특정 노드에서 특정 노드까지의 최단 경로 가중치를 구하는 것이므로 다익스트라 알고리즘을 적용할 수 있다. 기존의 다익스트라 형태에서 조금 다른 점은, 그래프 간선 정보가 따로 주어지는... 파이썬ps알고리즘다익스트라BFS최단 경로백준코딩테스트BFS 백준 5670번: 휴대폰 자판 자동완성이 안되는 경우는 단어가 완성되는 경우, 혹은 자식이 2개 이상인 경우이다. 모든 단어가 같은 알파벳으로 시작하더라도 처음에는 버튼을 한 번 눌러줘야 한다. 다들 C-style 문자열(const char*)로 trie를 구현하고, 그걸 돌려쓰길래 맘에 안들어서 문자열 레퍼런스랑 인덱스를 넘기는 방식으로 구현했다.... cppTriepsTrie [PS]로또의 최고 순위와 최저 순위 (LV1) 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호가 일치 3 4개 번호가 일치 4 3개 번호가 일치 5 2개 번호가 일치 6(낙첨) 그 외 로또를 구매한 민우는 당첨 번호 발표일을 학수고대하고 있었습니다. ... psLv1프로그래머스Lv1 2018 KAKAO BLIND RECRUITMENT 비밀지도 (lv1) 정답 코드 1 정답 코드 2 배운 점 1. 2진수 비트연산자 2. zip 함수... KAKAO 블라인드 테스트psKAKAO 블라인드 테스트 백준 14891 톱니바퀴 목표 : 톱니바퀴를 K번 회전시킨 후 점수를 구하자. 조건 : 1 <= K <= 100, 톱니바퀴는 8개의 톱니로 구성되어있다. 해결방안 전형적인 구현문제이다. 회전하는 톱니바퀴에 인접한 톱니바퀴의 좌우가 맞물릴 때 서로 다른 극이라면 해당 톱니바퀴도 반대방향으로 회전한다.... psps 2019 KAKAO BLIND RECRUITMENT 실패율 (lv1) 정답 코드 1 정답 코드 2 배운 점 첫 번째 코드에 비해 두 번째 코드의 실행 속도가 많이 빠르다. 시간 복잡도 향상을 위한 고민이 부족하다. dun dun dance 들으면서 코딩하면 좋다.... psKAKAO 블라인드 테스트KAKAO 블라인드 테스트 [백준 10217 파이썬] KCM Travel (골드 1, DP) 전체 문제를 "출발 노드에서 row 노드까지 정확히 비용 column으로 갈 때의 최단 시간"으로 둘 때의 풀이 전체 문제를 "출발 노드에서 row 노드까지 예산 column 내의 비용으로 갈 때의 최단 시간"으로 둘 때의 풀이 SOLVE 1) 풀이 요약 (전체 문제를 "출발 노드에서 row 노드까지 정확히 비용 column으로 갈 때의 최단 시간"으로 둘 때의 풀이) 전체 문제를 "출발 노... 파이썬ps알고리즘냅색최단 경로백준DP코딩테스트DP [백준 1956 파이썬] 운동 (골드 4, 플로이드 워셜) 알고리즘 유형 : 플로이드-워셜(최단 경로) 풀이 참고 없이 스스로 풀었나요? 풀이 요약 플로이드-워셜 알고리즘으로 풀면 pypy3으로 제출해야 통과된다. 다익스트라를 활용하여 풀 수도 있는데, 더 오래 걸리길래 시간복잡도를 비교해봤는데 다익스트라는 노드 수만큼 실행해줘야하니까 2VElogV, 문제의 조건에서 E의 범위가 V^2-V 까지랬으니 대충 V^3logV 정도 되겠다. 플로이드-워셜은... 플로이드 워셜파이썬ps알고리즘최단 경로백준코딩테스트ps [PS]올바른 괄호 (LV2) 올바른괄호 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 "()()" 또는 "(())()" 는 올바른 괄호입니다. ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다. '(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 ... Lv2ps프로그래머스Lv2 [PS]최댓값과 최솟값 (LV2) 최댓값과 최솟값 문자열 s에는 공백으로 구분된 숫자들이 저장되어 있습니다. str에 나타나는 숫자 중 최소값과 최대값을 찾아 이를 "(최소값) (최대값)"형태의 문자열을 반환하는 함수, solution을 완성하세요. 예를들어 s가 "1 2 3 4"라면 "1 4"를 리턴하고, "-1 -2 -3 -4"라면 "-4 -1"을 리턴하면 됩니다. 제한사항 s에는 둘 이상의 정수가 공백으로 구분되어 있습... Lv2ps프로그래머스Lv2 백준 12025 장난꾸러기 영훈 목표 : 영훈이는 장난꾸러기라서 희현이의 비밀번호 중 1은 6으로, 6은 1로 바꾸거나 2는 7으로 7은 2로 바꿔버렸다. 이를 해결하기 위해 희현이는 비밀번호 수열의 숫자 중 1과 6을 모두 1로, 2와 7을 모두 2으로 바꾼 숫자와 1과 6을 모두 6으로 2과 7을 모두 7로 바꾼 숫자 사이에 가능한 경우를 모두 사전순으로 나열한 다음 그 중 k번째 수열인 비밀번호를 찾기로 했다. 멘붕에... psps 프로그래머스 가장 먼 노드 Java 풀이 풀이 해당 문제는 그래프와 그래프 탐색 알고리즘 개념만 알면 상당히 쉬운 문제이다. 필자의 풀이는 인접 리스트를 만들어 각 노드가 연결된 노드들을 리스트에 넣어주고(인접리스트) 너비 우선 탐색을 한다. 방문하지 않은 노드는 방문을 체크할 배열이 있으므로, 방문시 무조건 처음 방문한게 보장이 되므로 그 노드의 level을 배열에 저장한다. 각 노드의 level이 저장된 배열의 max 값을 찾고... 알고리즘psps 백준 13913: 숨바꼭질 4 (파이썬) 정답코드 문제유형 BFS... psps [AtCoder] Beginner Contest 243 (A, B, C) 결과 : D번까지 solve(30:09) || 패널티 : 1회 1회 문제 설명 문제 정의 매일 밤 다카하시네 집에서는 전원이 [아버지, 어머니, 다카하시] 순으로 머리를 감습니다. 이때 [아버지 => A 리터, 어머니 => B 리터, 다카하시 => C 리터] 순으로 각각 사용한다고 했을 때, (누구 차례에 샴푸가 부족할까요?) 입력 및 제약 입력 내 풀이 해설 풀이 1회 문제 설명 문제 정의... psatcoderalgorithmalgorithm [BOJ] 18870번 좌표 압축(Python) 문제를 분석해보면, 중복을 제거한 후 정렬된 리스트에서 각 수에 대응되는 인덱스를 출력하는 문제이다. 매번 인덱스를 찾는 과정을 대신해서 dictionary를 통해 인덱스를 저장했다.... ps정렬bojboj 백준 #1912. 연속합 정리 이 문제도 다이나믹 프로그래밍 기법으로 해결할 수 있는 문제이다. bottom-up 방식으로, 연속합의 최댓값을 비교해서 저장해 두고, 계속 수열을 비교해 나가면서 기존의 연속합의 최댓값과, 새로운 연속합의 값을 비교해 나가는 방식으로 문제를 해결했다. 수열의 숫자는 -1000보다 크거나 같고, 1000보다 같거나 작은 정수이다. 즉, 수열에 음수가 포함될 수 있다. 따라서 각 숫자가 ... ps동적 계획법cpp백준algorithmalgorithm 백준 9020 - 골드바흐의 추측 소수 관련 문제 소수 리스트를 만든다. input값의 절반에 가장 가까운 작거나 같은 소수(a)를 찾고 소수 리스트에서 a의 index값을 찾는다. a와 더해서 input값이 되는 또 다른 소수(b)를 찾는다. 만약 조건에 맞는 b가 없다면 a보다 인덱스가 하나 작은 소수를 찾는다. 3-4를 조건에 맞는 a, b를 찾을 때 까지 반복한다. 처음 문제를 풀 때, 테스트 케이스 하나마다 소수리스... ps백준ps [PS] Union-Find Union-Find 자료구조는 그룹핑하여 자료를 저장하고, 같은 그룹인지 확인할 때, O(logN) 시간 만에 확인이 가능하다. 10의 최종보스가 8의 최종 보스 밑으로 들어간다! 그룹 개수를 구하기 위해서는 기본 코드에서 살짝만 변화를 주면 된다. Cycle 유무를 판단하기 위해서는 제약사항이 존재한다. 단방향그래프는 Cycle 판별 불가, 양방향그래프만 Cycle 판별 가능 cycle 유... psps 백준 7576번 - 앱 배낭 문제 알고리즘으로 풀이할 수 있는 문제다. 앱이 차지하는 메모리 용량이 Ai 소요되는 비용이 C_{i} Ci 라고 쳤을 때 확보해야하는 메모리 용량 M 이상을 확보 했을 때 최소 비용을 구하는 문제다. 그러므로 배낭 문제에 대응 해보았을 때 소요되는 비용이 배낭의 사이즈고, 해당 배낭 사이즈로 가져갈 수 있는 가치의 목록들이 각각의 앱의 메모리 용량이라고 생각하면 된다. 즉 dp배열과 ... ps냅색알고리즘DP백준DP [Python] 백준 1032 명령 프롬프트 제일 처음 N으로 받아올 테스트 케이스의 갯수를 입력 받는다. 입력 받은 테스트 케이스 X의 첫번째는 result에 저장하여 비교 대상으로 저장한다. 이후 for문으로 반복하여 X를 받아오는데 이미 위에서 result로 첫번째 테스트 케이스를 저장하였으니 n - 1번만 반복하여 받아온다. 비교값인 result와 반복하여 얻은 X의 값을 차례로 비교하며 만약 값이 같을 시 해당 값을 '?'로 ... pspython백준algorithmalgorithm 2022 KAKAO BLIND RECRUITMENT 신고 결과 받기 (lv1) 정답코드 다른 정답코드... psKAKAO 블라인드 테스트KAKAO 블라인드 테스트 2019 카카오 개발자 겨울 인턴십 (lv1) psKAKAO 블라인드 테스트KAKAO 블라인드 테스트 [PS] Heap Heap은 Priority Queue로 구현하는 방식이다. PQ : 우선순위부터 꺼내는 트리구조 조건 1 : Perfect Binary Tree Perfect : 노드의 순서가 위쪽 왼쪽 순 Binary : 자식이 최대 2개 Tree : CYCLE이 없는 그래프 조건 2 : 어떤 Node에서 직접 연결된 Node간의 우선순위가 알맞게 연결된 트리 우선순위 : 작은 값 로 변경하면 된다. 구조... psps [백준] 2615번 오목 사용 알고리즘 완전 탐색 + DFS 방향 설정 오목인지 판단을 하기 위해선 한 점에 대해서 총 8방향을 봐야한다. 하지만 2중 for문을 사용할 때, 위에서 아래 / 왼쪽에서 오른쪽으로 탐색을 하게 된다면, 파란색을 칠해진 방향에 대해선 볼 필요가 없다 (중복되기 때문) 5목 판단 DFS 시작 2중 for문을 이용하여 위에서 아래 / 왼쪽에서 오른쪽 으로 탐색을 하다가 0이 아닌 값일 경우,... psbaekjoonalgorithmalgorithm 프로그래머스 : 다리를 지나는 트럭 (파이썬, lv2) psps 이전 기사 보기