본문 바로가기

Thinking62

코딩테스트 문제 분석 방법 코딩테스트 문제 분석 방법 코딩 테스트 문제를 효율적으로 분석하고 파악하기 위한 몇 가지 방법과 전략을 소개합니다. 1. 문제 이해하기문제의 목적 파악: 문제에서 요구하는 최종 결과가 무엇인지 명확히 합니다.입력과 출력 확인: 주어지는 입력의 형태와 조건, 그리고 출력의 형태와 조건을 이해합니다.제약 조건 확인: 입력의 크기, 시간 제한, 메모리 제한 등을 확인하여 사용할 알고리즘의 효율성을 미리 판단합니다.2. 예제 분석제공된 예제 검토: 문제에서 제공하는 예제 입력과 출력을 통해 문제를 이해합니다.추가 예제 만들기: 예제만으로 이해가 부족하다면 직접 몇 가지 입력을 만들어보고 예상되는 출력을 도출해 봅니다.3. 주요 요구사항 파악핵심 기능 식별: 문제를 해결하기 위해 꼭 필요한 기능이나 알고리즘이 무.. 2024. 5. 23.

LV2 PCCP 기출문제 2번 석유 시추 [level2] [PCCP 기출문제] 2번 / 석유 시추 문제 설명 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다.예를 들어 가로가 8, 세로가 5인 격자 모양의 땅 속에 위 그림처럼 석유가 발견되었다고 가정하겠습니다. 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리이며, 석유 덩어리의 크기는 덩어리에 포함된 칸의 수입니다. 그림에서 석유 덩어리의 크기는 .. 2024. 2. 21.

2024 KAKAO WINTER INTERNSHIP 가장 많이 받은 선물 [2024 KAKAO WINTER INTERNSHIP] 가장 많이 받은 선물[level 1] 가장 많이 받은 선물 - 258712문제 링크성능 요약메모리: 4.19 MB, 시간: 1.72 ms구분코딩테스트 연습 > 2024 KAKAO WINTER INTERNSHIP채점결과정확성: 100.0합계: 100.0 / 100.0제출 일자2024년 2월 2일 3:10:51문제 설명선물을 직접 전하기 힘들 때 카카오톡 선물하기 기능을 이용해 축하 선물을 보낼 수 있습니다. 당신의 친구들이 이번 달까지 선물을 주고받은 기록을 바탕으로 다음 달에 누가 선물을 많이 받을지 예측하려고 합니다.두 사람이 선물을 주고받은 기록이 있다면, 이번 달까지 두 사람 사이에 더 많은 선물을 준 사람이 다음 달에 선물을 하나 받습니다.예.. 2024. 2. 20.

LV1 PCCP 기출문제 1번 붕대 감기 - 250137 [level 1] [PCCP 기출문제] 1번 / 붕대 감기 - 250137문제 링크성능 요약메모리: 4.2 MB, 시간: 0.01 ms구분코딩테스트 연습 > PCCP 기출문제채점결과정확성: 100.0합계: 100.0 / 100.0제출 일자2024년 2월 2일 1:14:51문제 설명어떤 게임에는 붕대 감기라는 기술이 있습니다.붕대 감기는 t초 동안 붕대를 감으면서 1초마다 x만큼의 체력을 회복합니다. t초 연속으로 붕대를 감는 데 성공한다면 y만큼의 체력을 추가로 회복합니다. 게임 캐릭터에는 최대 체력이 존재해 현재 체력이 최대 체력보다 커지는 것은 불가능합니다.기술을 쓰는 도중 몬스터에게 공격을 당하면 기술이 취소되고, 공격을 당하는 순간에는 체력을 회복할 수 없습니다. 몬스터에게 공격당해 기술이 취소당.. 2024. 2. 20.

프로그래머스 PCCE 기출문제 후기 [프로그래머스] PCCE 기출문제 후기PCCE (프로그래머스 코딩필수역량인증시험)권장대상 : 비전공자, 초/중급 학습자응시과목 : Python, Java, C++ 중 1개 언어 선택하여 평가문항수 : 10문항시험시간 : 50분시험구성 : 빈칸채우기, 디버깅, 코드 작성자격증 유효기간 : (응시일 기준으로) 7년 무료로 제공되는 기출문제 10개를 풀어봤습니다.풀이 시간은 약 60분 ~ 90분 정도 걸린 것 같습니다. 문제 수준은 이전 정보처리 기능사 ~ 산업기사 수준으로 편성되어 있었습니다.프로그래머스 난이도가 0 ~ 1인 만큼 문제의 난이도는 낮지만 직접 코드를 작성하는 것이 아닌 빈칸 채우기, 수정하기 등의 문제로 디버깅 능력을 확인합니다.다른 사람이 작성한 코드를 분석하고 이해하지 못한다면 조금 어.. 2024. 2. 19.

오일러각(Euler Angle)과 쿼터니언(Quaternion) 오일러각(Euler Angle)과 쿼터니언(Quaternions) 오일러 각은 강체가 놓인 방향을 3차원 공간에 표시하기 위해 레온하르트 오일러가 도입한 세 개의 각도이다. 오일러각은, xyz를 세 축을 기준으로 회전하는 것을 의미한다. 오일러각의 정의 자체가 한 축을 기준으로 돌리는것을 의미하기 때문에 x,y,z 축의 회전연산을 한 번에 할 수 없다. z축을 돌리는 순간 x,y축은 함께 도는 오일러각 시스템상에, 피할 수 없는 유명한 문제점이 하나 있다. 바로 짐벌락 현상이다. 회전을 하다 보면 특정 시점에 한 축이 축 자체의 역할을 잃어버리게 되는 현상을 말한다. 이런 문제들을 보완한게 바로 쿼터니언이다. 사원수(Quaternions)는 아일랜드의 수학자 윌리엄 해밀턴(William Rowan Ham.. 2023. 11. 3.

KD-트리 (K-Dimensional Tree) [k-차원 트리] KD-트리 (K-Dimensional Tree) [k-차원 트리] KD-트리는 이진 탐색 트리를 확장한 것으로 k개(k>=2)의 필드로 이루어지는 키를 사용한다. 동일한 레벨에 있는 노드는 모두 동일한 하나의 필드만 이용해서 분기한다 KD-트리에서 검색을 이용해 내려간다는 것은 다차원 공간에서 이렇게 나누어진 결과에 따라 공간의 범위를 점점 좁혀나가는 것이다. 3차원일 경우 입체적인 형상이 된다. KD-트리 삽입 A(50, 50) → B(10, 70) → C(80, 85) → D(25, 20) → E(40, 85) → F(70, 85) → G(10, 60) 1. A(50, 50)이 루트 자리를 차지 2. B(10, 70)는 x값 10이 루트의 x값 50보다 작으므로 왼쪽 자식이 된다 3. C(80, 85.. 2023. 10. 3.

B-트리 (B-Tree) B-트리 (B-Tree) B-트리(B-tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. B-트리는 디스크 환경에서 사용하기에 적합한 외부 다진 검색 트리이다. B-트리는 자료를 정렬된 상태로 보관하고, 삽입 및 삭제를 대수 시간으로 할 수 있다. 최대 M개의 자식을 가질 수 있는 B-트리를 M차 B-트리라고 한다. 노드는 최대 M개의 자식 노드를 가질 수 있다. ex) 3차 B-트리라면 최대 3개의 자식 노드를 가질 수 있다. 노드에는 최대 M-1개의 KEY를 가질 수 있다. ex) 3차 B-트리라면 최대 2개의 KEY를 가질 수 있다. 각 노드는 최소 ⌈M/2⌉개의 자식.. 2023. 10. 3.

레드 블랙 트리 (Red-Black Tree) 레드 블랙 트리 (Red-Black Tree) 이진 탐색 트리에서 트리의 모양이 균형을 이루지 못 할 경우가 있다. 균형이 깨질 경우 O(n)에 근접한 시간이 소요되는데, 균형을 잘 맞추기 위해 고안된 것이 레드-블랙 트리이다. 레드-블랙 트리는 자가 균형 이진 탐색 트리이다. 리프 노드가 개입될 때 특수 처리를 하지 않아도 된다는 편리함이 있다. 레드-블랙 트리는 다음과 같은 조건들을 만족한다. 1. 루트 노드는 검은색이다. 2. 모든 노드는 레드 혹은 블랙이다. 3. 모든 리프 노드(NIL)들은 검은색이다. (NIL : null, 자료를 갖지 않고 트리의 끝을 나타내는 노드) 4. 레드 노드의 자식은 블랙이다. (레드 노드가 연속으로 나올 수 없다) 5. 리프노드에서 루트 노드까지 가는 경로에서 만나.. 2023. 10. 2.

이진 탐색 트리 (BST : Binary Search Tree) 이진 탐색 트리 (BST : Binary Search Tree) 이진 탐색 트리(BST: Binary Search Tree)는 다음과 같은 속성이 있는 이진 트리 자료 구조이다. 1. 각 노드에 중복되지 않는 키(key)가 있다. 2. 최상위 레벨에 루트 노드가 있고, 각 노드는 최대 두개의 자식 노드를 갖는다. 3. 왼쪽 서브 트리는 부모 노드의 키보다 작은 키를 갖는다. 4. 오른쪽 서브 트리는 부모 노드의 키보다 큰 키를 갖는다. 이진 탐색 트리에서의 검색 1. 루트노드로 부터 시작한다. 2. 검색하려는 값이 현재 노드보다 작으면 왼쪽, 크면 오른쪽으로 가서 찾는다. 3. 노드를 비교하면서 내려가다가 일치하는 값이 나오면 해당 노드를 반환한다. 4. 더이상 비교할 노드가 없으면 검색이 실패했음을 알.. 2023. 10. 2.

선택 (Select) 알고리즘 선택 (Select) 알고리즘 정렬되지 않은 리스트나 배열에서 가장 작은 k번째 수를 찾는 알고리즘이다. 간단한 방법은 최소 숫자들을 오름차순으로 정렬한 후, k번째 숫자를 찾는 것이 있는데, 이러한 알고리즘은 O(nlogn)의 수행 시간이 걸린다. 이보다 효율적인 해결을 위하여 분할 정복 개념을 활용할 수 있다. 일부 과정이 퀵 정렬과 비슷하여 Quick-Select 알고리즘이라고도 한다. "평균"선형 시간 안에 k번째 작은 수를 찾을 수 있다. 부분문제의 크기가 일정하지 않은 크기가 감소하는 형태의 분할 정복 알고리즘이다. 만일 피봇이 입력을 너무 한 쪽으로 치우치게 분할하면, 알고리즘의 수행시간이 길어진다. 두 그룹 중 하나의 크기가 입력 크기의 3/4과 같거나 그보다 크면 bad 분할이고, 그 반.. 2023. 10. 2.

Sort 계수 정렬 (Counting Sort) 알고리즘 [Sort] 계수 정렬 (Counting Sort) 알고리즘 계수 정렬은 데이터의 키에 따라 객체를 수집 정렬 하는 정렬 알고리즘이다.비교 연산을 하지 않는 정렬 알고리즘이다.키의 다양성이 데이터의 수보다 상당히 크지 않은 상황에서 유용하다.O(n)의 시간 복잡도를 가진다.데이터 중 가장 작은 값과 가장 큰 값을 기준으로 하는 공간 크기가 필요하다. (1~10의 경우 10개의 공간이 필요하지만 1과 10000이 들어 있는 데이터에서는 10000의 배열 크기가 필요하다.)특정한 값이 몇번 등장했는지에 따라 정렬을 수행한다.계수를 다 카운팅 한 후에 앞에서 부터 차례대로 배열에 넣는다. 정렬 과정10000개의 공간에 1 ~ 10까지의 정수가 무작위로 들어가 있다고 가정한다.최솟값 최댓값을 알고 있을 때, 각.. 2023. 10. 1.

이전 1 2 3 4 ··· 6 다음

티스토리툴바