차곡차곡

https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도 LV 3 문제 설명 시작 단어 begin, 도착 단어 target이 주어지고 변환할 수 있는 단어의 배열 words가 주어진다. 변환할 수 있는 조건은 한번에 한 개의 알파벳만 바꿀 수 있고, words안에 있는 단어로만 변경이 가능하다. 최소 몇단개에 걸쳐 begin의 단어를 target으로 변환 가능한지 Retrun해준다. 만약 변환할 수 없는 경우 0을 Retrun 해준다. 해결법 d..

https://school.programmers.co.kr/learn/courses/30/lessons/12927 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도 LV 3 문제 설명 해야할 일이 works 배열에 각 일에 대한 필요 작업량이 저장되어 있다. 1시간에 작업량 1만큼을 할 수 있다. 퇴근 시간까지 남은시간 n 이 주어진다. 야근피로도는 퇴근 시간 이후 각 일의 남은 작업량의 제곱의 합이다. 가장 적은 야근 피로도를 계산해서 Return 해야한다. 접근 법 야근 피로도를 가장 낮추는 방법은 모든 일의 작업량을 균등하게 낮추는 것이다. 남은..

https://school.programmers.co.kr/learn/courses/30/lessons/12938 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도 LV 3 문제 설명 자연수 n개로 이루어진 집합이 있다. 집합 원소들의 합은 s와 동일하다. 이때 가능한 집합 중 각 원소의 곱이 최대가 되도록 하는 집합을 Return해주어야 한다. 만약 집합이 존재하지 않는 경우에는 [-1]을 Return 한다. 접근법 우선 집합이 존재하지 않는경우는 집합 원소의 수(n)가 원소의 합 (s)보다 크면 집합이 없다. (원소가 자연수이기 때문에 각 원소의 ..

https://school.programmers.co.kr/learn/courses/30/lessons/42628?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도 LV 3 문제 설명 I 숫자 형태일때는 큐에 해당 숫자를 삽입한다. D 1 형태일때에는 큐에서 최댓값을 삭제한다. D -1 형태일때에는 큐에서 최솟값을 삭제한다. 만약 큐가 비어있다면 [0,0] 출력 아니라면 [최대값, 최소값] return 해준다. 접근법 시간을 최대한 줄이기 위해 항상 맨 앞이 최소가 되는 heapq를 사용한다. 파이썬은 문자열에 문자를 인..

https://school.programmers.co.kr/learn/courses/30/lessons/43105?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도 LV3 문제 설명 삼각형 모양으로 꼭대기에서 바닥까지 이어지는 경로 중 숫자의 합이 최대가 되는 경우의 합을 Return해준다. 아래칸으로 이동할때 대각선 방향으로 한칸 오른쪽 왼쪽 으로만 이동 가능하다. 접근법 삼각형 꼭대기 한칸 아래에서부터 위에서 내려올 수 있는 경우에 대해 최대 값을 더해준다. 만약 양끝에 있는 경우에는 가능한 값이 하나밖에 없으므로 별..

https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도 LV3 문제 설명 [출발지,도착지] 형태로 적힌 항공권 정보 List가 주어진다. 출발지는 항상 ICN 공항에서 출발하며 모든 항공권을 사용해야 한다. 이를 만족하는 경로를 Return하고 만약 만족하는 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 Return한다. 접근법 스택에 ICN을 넣어준다. 출발지와 도착지 정보가 담긴 dictionary 배열의 key(출발지) 와 valu..

너비 우선 탐색 (BFS, Breadth First Search) 한 노드에서 시작한 후 시작 노드의 인접한 노드부터 탐색하는 방법이다. 가까운 노드부터 탐색하는 알고리즘 이다. 시작 노드로부터 가까운 정점을 먼저 방문하고 멀리 있는 노드는 마지막에 방문하는 방식이다. 넓게 탐색하는 방식이다. 일반적으로 선입선출 방식인 큐 자료구조를 활용한다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 먼저 들어온 것이 먼저 나가게 되어 가까운 노드부터 탐색이 이루어진다. 특징 여러 갈래중 무한한 길이를 가지는 경로가 존재하고 탐색 목표가 다른 경로에 존재하는 경우에는 DFS는 무한루프에 빠져 종료되지 못하지만, BFS는 동시에 탐색이 진행되기때문에 탐색이 완료될 수 있다. 모든길을 한번씩 탐색하기 때문에..

https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도 LV 3 문제 설명 n개의 노드가 주어지고 1번 노드로 부터 가장 먼 노드의 갯수를 구해서 Return 해주어야 한다. 이때 가장 멀리 떨어진 노드란 최단 경로로 이동했을 때 간선의 갯수가 가장 많은 노드를 의미한다. 접근법 그래프 이론 알고리즘의 인접 리스트 방식으로 주어진 입력을 변환해준다. 거리(간선 개수)를 저장 해줄 리스트를 만들고 BFS를 사용해 최단 경로의 간선 개수를 센후 저..

https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 난이도 골드5 문제 설명 n*n크기의 교실에 n^2 명의 학생이 있다. 학생들을 일정한 조건에 따라 교실에 배치해야한다. 조건 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 ..

구현 문제에 대한 알고리즘을 소스코드로 만드는 과정이 구현이다. 어떤 문제를 풀든 간에 소스코드를 작성하는 과정은 필수적이므로 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다. 구형 유형의 문제는 풀이는 떠올리는 것은 쉽지만 그것을 소스코드로 옮기는 과정이 어려운 문제를 의미한다. 구현 유형 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례로 직접 수행 구현 문제 풀이시 생각해야 될 점 메모리 제약 사항 채점 환경 접근 방법 파이썬의 경우 1초에 2*10^7(2000만번)의 연산을 수행한다. pypy3 지원시 사용하면 1초에 1억번의 연산을 수행할 수 있다. pypy3의 속도는 c/c++에 견줄만큼 빠르기 ..