Engineering Note

Link : https://www.acmicpc.net/problem/16198 Note 문제를 처음에 접근했을 당시에는 예시 입출력들을 가지고 규칙을 찾아본 결과, 그리디 과정으로 규칙이 찾아져서 코드를 제출했더니 틀렸다. 내가 처음에 풀이한 그리디 과정은 문제의 조건에 따라 i 구슬을 제거할때 i-1,i+1의 에너지 구슬로 모은 에너지 값이 최대가 되는 구슬로 정하였다. 첫 번째 예시의 경우 [1,2,3,4]에서 3을 골랐을때 8(2*4)가 가장 크기 때문에 3을 제거해주고 남은 2를 제거해줄 때 에너지는 4가 되어 총 에너지 합은 12가 된다. [100,2,1,3,100]의 경우 100(2) (에너지(제거숫자)), 6(1), 100(3)에서 큰 값 100이 같은 경우 제거 숫자는 작은 경우, [10..

Link : https://www.acmicpc.net/problem/15649 Note 문제를 잘 읽고 이해하면 쉽게 풀 수 있는 문제다. 1부터 N까지의 자연수 중에서 중복 없이 M개를 고른 수열을 출력하는 프로그램을 작성하면 된다. 예를 들면 N이 4고 M이 2라면 1부터 4까지 자연수 중에서 중복 없이 2개를 고른 수열을 구하면 된다. nums = [1,2,3,4] 수가 있고 2개를 고르는 방법을 나타내면 다음과 같다. 1부터 N에서 수를 하나 추출하고 다시 중복 없이 1부터 N에서 수를 하나 추출하는 과정을 재귀적으로 구현하면된다. 1번의 과정은 추출한 수가 M개가 될때까지 반복 수행한다. Code import sys def choose(set_nums): global answers,n,m if..

Link : https://www.acmicpc.net/problem/1463 Note 문제풀이과정 회고 처음에는 정수 별 특징으로 수를 분류가 가능할 것으로 생각하였다. 예를 들면 2의 배수, 3의 배수, 혹은 3의 배수가 아닌 홀수로 분류하고, 문제에 주어진 대로 짝수라면 2로 나누고 홀수라면 3으로 나누어 떨어지는지 확인하고 나누어 떨어지면 나누고, 아니라면 -1을 하는 식으로 연산을 수행해보았다. 하지만 이 방식에서는 예외 사항들이 많았다. 예를 들면 10의 경우 짝수이기 때문에 처음에 2로 나누어 진행하면 5가 된다. 그리고 그 다음 과정을 진행하면 다음과 같다. '10 -> 5 -> 4 -> 2 -> 1' 하지만 이 방식은 최소 연산 사용이 아니다. '10 -> 9 -> 3 -> 1'이라는 더..

Link : https://www.acmicpc.net/problem/1325 Note 프로그래머스의 전력망 나누기 문제를 풀다가 트리,그래프 자료구조관련 문제 연습이 필요하다고 느껴 풀이한 문제다. python3에서 BFS, 재귀 DFS로 풀이하면 시간초과가 발생, pypy3에서 재귀 DFS 로 풀이하면 메모리초과 발생하지만 pypy3에서 파이썬의 list를 스택으로 이용하여 DFS로 트리 탐색 또는, BFS 탐색을 하면 해결된다. A가 B를 신뢰하는 경우 B를 해킹하면 A도 해킹하는 컴퓨터 시스템이 있다. 입력은 첫 째줄에 전체 컴퓨터의 수 n, 연결 상태 m이 주어지고 다음 m번 줄에 걸쳐 A, B가 입력으로 주어진다. 입력 값을 통해 방향그래프를 만들고, 방향그래프를 탐색하면서 탐색가능한 노드의 ..

Link : https://programmers.co.kr/learn/courses/30/lessons/86971 Note 자료구조, 알고리즘의 개념에 대해 다시 생각해보게 해주는 문제였다. 쉬운 문제만 풀었을 때는 문제를 잘 이해하고 구현하는 과정에만 집중하면 된다고 생각했다. 하지만 역시 기본개념이 중요하다. 이 문제를 풀면서 트리, 트리 탐색에 대해서 다시 복습하는 기회가 되었다. 개념이 부족할 때는 무작정 완전탐색으로만 문제를 해결하려고 하는 경향이 많았다. 이 문제에서도 처음에는 완전탐색으로 문제를 해결했다. 답은 나오지만 좋은 방법은 아니다. 자료구조, 알고리즘의 개념이 더 정확하게 쌓여있었다면 더 효율적인 코드를 작성할 수 있다. wires의 최대값이 100이기 때문에 송전탑 연결상태를 하나..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/49189 문제 요약 및 해설 n개의 노드가 있는 그래프가 있다. 각 노드는 1번부터 n까지 번호가 적혀있다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하면된다. 가장 멀리떨어진 노드란 최단경로로 이동했을 때 가넌의 개수가 가장 많은 노드들을 의미한다. 입력 정보는 노드의 개수(n)과 간선 정보(vertex), vertex[a][b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미이다. * 문제 해결 방법 1. vertex로부터 그래프 자료구조를 표현한다. 인접행렬 또는 인접리스트 방식으로 만든다. 2. 1에서 만든 그래프를 1번 노드부터 그래프를 탐색하면서 각 노드마다 1번노드로 부터 최..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42883?language=python3 문제 요약 및 해설 가장 큰 자리수에, 위치로 말하면 가장 왼쪽에 9,8,7,6,5,4,3,2,1 순으로 숫자가 위치해야 한다. 1. 문제에 주어진 숫자를 i 인덱스에서 하나씩 꺼내 현재 숫자 변수에 넣는다. (최초의 i 인덱스는 0이다. 마지막 인덱스는 문자열 길이-1이다.) 2. (k 값이 0보다 크고 가장 마지막에 삽입한 숫자 < 현재 숫자) 라면 3 번으로 아니면 4번으로 간다. 3. 가장 마지막에 삽입한 숫자를 제거하고 k 값을 하나 줄이고 다시 2번으로 간다. 4. stack에 현재 숫자를 푸시한다. i 인덱스를 하나 증가한다. 1번으로 간다. 5...

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42586 문제 요약 및 해설 배포 순서와 현재 진행 상태가 적힌 배열, 각 기능의 개발 속도가 적힌 배열이 주어 질때 각 배포 마다 몇 개의 기능이 배포 되는지 return 하도록 하는 solution 함수를 완성 이때, 각 기능은 100%일 때 배포가 가능하고, 뒤에 기능이 먼저 개발된다고 하더라도 배포 순서에 따라 앞에 기능이 완료되지 않았다면 배포 할 수 없다. 배포는 하루에 한 번만 이루어지며 하루의 끝에 이루어 진다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 첫 날에는 99% 둘 째날에는 100%를 달성할 수 있다. 즉 2일 뒤에 배포가 이루어진다. 알고리즘 1. 모..