민규의 흔적

2024년 6월 7일문제 링크 : 프로그래머스 - 스킬트리 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  문제 접근 스킬을 배우는 순서가 CBD라면, C를 배워야 B를 배우고 B를 배워야 D를 배울 수 있다. 딕셔너리를 선언하여 스킬을 key, 배우는 순서를 value로 지정하였다.이게 가능한 이유는 스킬이 중복되지 않기 때문.  검증해보는 스킬트리를 앞에서부터 탐색하며 딕셔너리의 배우는 순서와 비교해본다.아직 배울 수 있는 순서가 아닌데 스킬을 배우려고 한다면 가차 없이 탐색을 종료하고, 스킬트리의 맨 마지막 스킬까지 탐색하여 유효함이 검증된다면 가능한 ..

2024년 6월 7일문제 링크 : 프로그래머스 - 2개 이하로 다른 비트 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 접근 주어진 10진수 x와 x보다 큰 모든 수들 중, 2진수로 변환했을 때 비트가 1~2개 다른 수 중 가장 작은 수를 구하는 문제이다. 예를 들어, x가 4일 때, 이를 2진수로 바꾸면 100⑵이며, x보다 큰 수는  5, 6, 7 ... 등등 많지만각각 2진수로 변환하면 101⑵, 110⑵, 111⑵ ... 와 같다. 이러한 x보다 큰 수들 중, 2진수로 변환했을 때 x의 2진수 변환 수보다 비트가 2개 이하로 다른 수 중 가장 작..

2024년 5월 28일문제 링크 : 백준 18352번 - 특정 거리의 도시 찾기  문제 어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.  이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다.  2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.입력첫째 줄에 도시의 개..

2024년 5월 22일다익스트라( 데이크스트라, Dijkstra ) 다익스트라 알고리즘은 그래프의 한 정점에서 모든 정점까지의 최단 경로를 각각 구하는 알고리즘으로, 에츠허르 다익스트라가 고안한 알고리즘이다. 다이나믹 프로그래밍을 활용해 중복 연산을 방지하며 최단 경로를 구한다는 특징을 지니고 있다. 플로이드-워셜 알고리즘과는 다르게, 다익스트라 알고리즘은 그래프 내에 음의 가중치를 가진 간선이 존재한다면 사용할 수 없다. 추가로 둘의 차이점이라면 다익스트라 알고리즘은 하나의 노드로부터 최단 경로(one - to - all)를 구하는 알고리즘인 반면, 플로이드-워셜 알고리즘은 가능한 모든 노드쌍들에 대한 최단 경로(all - to - all)를 구하는 알고리즘이라는 점이다. (플로이드-워셜 알고리즘에 대..

2024년 5월 16일 0-1 냅색 문제를 풀어보며 해당 이론에 대해 알아보도록 하겠다.  문제 링크 : SWEA 3282번 - 0/1 Knapsack SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com   문제 접근 제목에서 친절하게 0-1 냅색 문제임을 알려주었다. Knapsack 문제는 배낭 문제라고도 하며, 0-1 Knapsack 문제와 Fractional(분할 가능한) Knapsack 문제가 존재한다. 둘의 차이점은 다음의 예시를 보며 설명하겠다. 민규는 고향으로 내려가기 전, 배낭에 선물을 담아 가져갈 것이다.선물을 무한정 담으면 좋겠지만, 배낭의 한계 무게 W를 초과하면 배낭이 찢어진다.민규는 각각의 선물..

2024년 5월 16일문제 링크 : SWEA 5607번 -  [Professional] 조합  SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com  문제 접근 문제 자체는 간단하다. N Combination R을 1234567891로 나눈 나머지 값을 구하면 되는 문제. N combination R을 구하는 수식은 다음과 같다. N! / R! * (N - R)! 단순히 계산을 통해 정답을 구하려하면 계산 과정에 도출되는 값들이 너무 커질 뿐더러 ( N의 최대값은 1,000,000, 1,000,000!은 상상도 하기 싫은 큰 수이다), 1234567891로 나누기 직전에 도출되는 값은 최대 1,000,000 C 500,..

2024년 5월 14일문제 링크 : [Python 파이썬] SWEA 1215번 - [S/W 문제해결 기본] 3일차 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com  문제 접근 전형적인 패턴매칭 알고리즘 문제이다.전체 문자열 S가 주어지고 부분 문자열 P가 주어졌을 때, S 안에 P가 몇 개 존재하는지 알아내면 되는 문제이다. 문자열 S의 맨 앞에서부터 문자를 하나씩 선택하며, 해당 문자를 시작으로 P의 길이만큼 슬라이싱하여 이 것이 패턴 P와 같은지 확인하기엔 너무 불필요한 연산이 많아진다. 그래서 나는 S의 각 문자가 P의 첫 번째 글자와 같은지 확인 후 같다면 해당 문자부터 P 길이만큼 슬라이싱하여 P와 대조해..

2024년 5월 14일문제 링크 : SWEA 11315번 - 오목 판정 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com   문제 접근 N x N 사이즈의 판이 주어지고, 돌이 놓아진 곳은 o , 아닌 곳은 . 문자를 표기한다. 우리가 아는 오목과 같이 가로, 세로, 대각선 중 하나의 방향으로 다섯 개 이상 연속한 돌이 있는지 판정하면 되는 문제이다.  먼저 가로, 세로, 대각선 방향으로 한 칸씩 전진하며 탐색해야 하기에 다음과 같이 8방향을 탐색하기 위한 두 배열을 선언해주어야 한다. # 동, 남동, 남, 남서, 서, 북서, 북, 북동d_row = [0, 1, 1, 1, 0, -1, -1, -1]d_col = [1..