※사용언어 : 파이썬 ※ ▼ 문제 링크 ▼ https://school.programmers.co.kr/learn/courses/30/lessons/87391 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 ◇ 문제를 간단히 요약하자면 다음과 같습니다. ▶ 주어진 쿼리 문에 맞춰 공을 움직여, 주어진 x, y 에 공이 도착할 수 있는 시작 위치를 찾는 문제입니다. ◇ n행 m열의 격자의 최대 크기가 10의 9승입니다. 그러므로 모든 격자의 칸에서 쿼리를 돌려 x, y에 도착하는지 확인하는 완전 탐색으로 풀기에는 시간이 부족합니다. 그러므로 도착점을..

※ 사용언어: 파이썬 ※ 트라이 알고리즘 설명 아래 16934 게임닉네임 백준 파이썬 풀이 코드가 있습니다. 개념 문자열을 효율적으로 탐색하기 위해, 문자열을 트리형태로 저장한 자료구조이다. 다른 이름으로는 radix tree 혹은 prefix tree가 있다. Trie 알고리즘은 크게 문자열을 트리형태로 저장하는 삽입과 문자열을 검색이라는 두 부분으로 나눌 수 있다. Trie 알고리즘 - 삽입 "apple, car, chat"이라는 문자열이 있다고 가정하겠다. 해당 문자열을 트리 구조로 표현하면 다음과 같다. (여기서 "head"는 트리의 root 노드라고 생각하면 된다.) 해당 트리 구조를 기억하기 위해서는 각 노드들은 3가지의 변숫값을 기억하고 있어야 한다. key: 현재 노드 data: 최종 문자..

※ 사용언어: 파이썬 개념 Union-Find 연산은 서로소 집합 자료구조를 조작하는 연산이다. 서로소 집합 자료 구조란, 서로소 부분 집합(공통 원소가 없는 두 집합)들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다. Union는 같은 집합에 소속될 원소들을 구하는 연산이며, Find를 통해 특정 원소가 어떤 집합에 소속되어 있는지 찾는 연산이다. Union 알고리즘 로직은 다음과 같다. 1. 노드들의 루트 노드를 저장할 테이블(리스트)를 생성한다. 2. 서로 연결된 A,B를 확인하여, A와 B의 루트(부모) 노드를 찾습니다. 3. 루트 노드를 찾은 후, A의 루트 노드와 B의 루트 노드 중 번호가 작은 쪽이 A, B의 루트 노드가 된다. # 1. 루트 배열 만들기 # (노드가 1부터 시작할 ..

※ 사용언어 : 파이썬 ※ ▼ 문제 링크 ▼ https://www.acmicpc.net/problem/1322 1322번: X와 K 첫째 줄에 X와 K가 주어진다. X와 K는 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 접근 ◇ X와 K의 범위가 20억보다 작거나 같은 자연수로 상당히 범위가 큽니다. 해당 수의 범위를 생각하면 시간 복잡도에 N이 들어가면 2초 안에 문제를 풀기는 거의 불가능하다고 볼 수 있습니다. 그러므로 상수 시간 내에 문제를 해결할 수 있는 방안을 모색해야 합니다. ◇ int형의 표현 범위는 대략적으로 21억 정도입니다. 즉 X와 K는 int형 범위 내의 수라는 것을 알 수 있습니다. 또한, int형은 4byte=32bit이므로, X와 K는..

※사용언어 : 파이썬 ※ ▼ 문제 링크 ▼ https://school.programmers.co.kr/learn/courses/30/lessons/138475 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제설명 ◇ 문제를 요약하자면 다음과 같습니다. ▶ 구구단 같이, 억 X 억을 곱해둔 단이 존재합니다. 그리고 해당 억억단에서 s 부터 e까지의 수 중 가장 많이 나온 수를 찾고 출력합니다. 단, s 부터 e까지의 수 중 가장 많이 나온 수가 여러 개이면 가장 작은 수를 출력합니다. (여기서 s는 starts 배열 안의 수다.) ◇ 풀이 방법을 간단하게..

※사용언어 : 파이썬 ※ ▼ 문제 링크 ▼ 0주 차 챌린지 goorm 구름은 클라우드 기술을 이용하여 누구나 코딩을 배우고, 실력을 평가하고, 소프트웨어를 개발할 수 있는 클라우드 소프트웨어 생태계입니다. goorm.co 문제 접근 해당 문제는 구름 측에서 해설지를 제공하고있다. 그럼에도 불구하고 포스팅을 한 이유는 단순히 해설지에 파이썬 코드가 없기 때문이었다. 그냥 넘어가긴 조금 아쉬운 감이 있으니 해설지 내용을 간략하게 압축하여 서술하겠다. 해당 문제는 그리디로 접근이 가능하다. 그 이유는 사람의 순번이 작을수록 그 사람이 교환할 수 있는 카드 중 가장 작은 수를 선택해야 하기 때문이다. 예를 들어, 순번이 2, 5, 6 인 사람끼리 카드 교환이 가능하다고 가정하겠습니다. 그리고 세 명의 사람이 가..