본문 바로가기

알고리즘15

[2024 정처기 실기 2회] 정보처리기사 2회 실기 해설 및 설명 1. 다음은 Java 코드에 대한 문제이다. 아래 코드를 확인하여 알맞는 출력값을 작성하시오. class Main { public static void main(String[] args) { int[] a = new int[]{1, 2, 3, 4}; int[] b = new int[]{1, 2, 3, 4}; int[] c = new int[]{1, 2, 3}; // 첫 번째 비교: a와 b check(a, b); // 결과: N // 두 번째 비교: a와 c check(a, c); // 결과: N // 세 번째 비교: b와 c check(b,.. 2024. 9. 14.
정보처리기사 실기 코딩 알고리즘 C언어 최신 문제 정리 해설 - 24년 대비 공부를 하며 정보처리기사 실기 코딩 알고리즘 문제 중 긴가 민가했던 부분만 개인 확인용으로 정리하였습니다. 혹시 보시는 분이 있을지는 모르겠지만 문제가 있을 경우도 있어 꼭 믿지 않으셨으면 좋겠습니다.  C언어 문제 1년간 비중20년 : 4문제21년 : 5문제22년 : 7문제23년 : 15문제  20년도 문제 1회 14번#include main() { int c=1; switch(3){ case 1:c+=3; case 2:c++; case 3:c=0; case 4:c+=3; case 5:c-=10; default : c--; }printf("%d",c); } 저는 순간 break; 가 없다는 걸 생각없이 풀었습니다.이 코드에서 switch 문은 3과 매치됩.. 2024. 4. 19.
그래프 용어, 종류와 트리와의 차이점 1. 그래프(Graph) 실제 세계의 현상이나 사물의 정점(Vertex) 또는 노드(Node)와 간선(Edge)으로 표현하기 위해 사 2. 그래프 관련 용어 노드(node) : 위치, 정점이라고 함 간선(edge) : 위치간의 관계를 표현한 선으로 노드를 연결한 선(link 또는 Branch라고도 함) 인접 정점(adjacent vertex) : 간선으로 직접 연결된 정점(또는 노드) 3. 그래프의 종류 3-1. 무방향 그래프 방향이 없는 그래프 간선을 통해, 노드를 양뱡향으로 갈 수 있음 3-2. 방향 그래프 간선에 방향이 있는 그래프 보통 노드 A, B가 A -> B로 가는 간선으로 연결되어 있는 경우 로 표기(와 는 다름 3-3. 가중치 그래프 간선에 비용 또는 가중치가 할당된 그래프 3-4. 연결.. 2023. 2. 23.
Python 자료구조&알고리즘 - 순차 탐색, 이진 탐색 1. 순차 탐색(Sequential Search) 탐색은 여러 데이터 중에서 원하는 데이터를 찾아내는 것을 의미 데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법 1. 이진 탐색(Binary Search) 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방 1-1. 이진 탐색과 순차 탐색의 비교 2. 분할 정복 알고리즘과 이진 탐색 분할 정복 알고리즘 divide : 문제를 하나 또는 둘 이상으로 나눔 conquer : 나눠진 문제가 충분히 작고 해결이 가능하면 해결하고, 그렇지 않으면 다시 나눔 이진 탐색 divide : 리스트를 두 개의 서브 리스트로 나눔 conquer : 검색할 숫자 > 증가값 : 뒷 부분의 서브 리스트에서 검색힐 숫자를 찾음 검색할 .. 2023. 2. 22.
Python 자료구조&알고리즘 - 분할 정복 1. 분할 정복(Division Conquer) 문제를 나눌 수 없을 떄까지 나누어서 각각을 풀면서 다시 병합하여 문제의 답을 얻는 알고리즘 하향식 접근방법으로 상위의 해당을 구하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식(재귀함구로 구현) 문제를 잘게 쪼갤때 부분 문제는 서로 중복되지 않음 Memorization 기법을 사용하지 않음 2. 대표적인 분할 정복 알고리즘 : 퀵 정렬(quick sort 정렬 알고리즘의 꽃(고급 알고리즘) 기준점(pivot)을 정해서 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수를 작성 각 왼쪽, 오른쪽은 재귀용법으로 사용해 다시 동일 함수로 호출하여 위 작업을 반복함 2-1. 퀵 정렬 알고리즘 구현 리스트 개수가 1개면 해당 리스트를 리턴 리.. 2023. 2. 22.
Python 자료구조&알고리즘 - 동적 계획법, 백준 11726번 1. 동적 계획법(Dynamic Programming) 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분의 값을 활용해서 보다 큰 크기의 부분 문제를 해결함 상향식 접근법(최하위 해답을 구한 후 해당 결과를 이용해서 상위 문제를 풀어가는 방식) 프로그램 실행 시 이전의 계산한 값을 저장하여 다시 계산하지 않도록 전체 실행 속도를 빠르게 하는 기술(메모이제이션 : Memoization)을 사용 문제를 잘게 쪼갤 때, 부분 문제는 중복되기 때문에 재활용 2. 동적 계획법 알고리즘 피보나치 수열 n을 입력받아서 아래와 같이 계산 피보나치 수열 함수흫 '피보나치' fibonacci(0) : 0 fibonacci(1) : 1 fibonacci(2) : 1 fibonacci(3) : 2 fibonacci(4).. 2023. 2. 21.
Python 자료구조 & 알고리즘 - 재귀호출 1. 재귀호출(recusive call) 함수 안에서 동일한 함수를 호출하는 형태 여러 알고리즘, 고급 정렬 알고히즘 작성시 자주 사용됨 1-1. 재귀 호출 분석 2! = 1 * 2 3! = 1 * 2 * 3 4! = 1 * 2 * 3 * 4 = 3! * 4 1-2. 규칙 n! = n * (n-1)! 함수로 만들어 보자 함수(n)은 n=1 함수(n)은 n>1 이면 return n*함수(n-1) 1-3. 검증 2! 함수(2)이면 2>1 이므로 2 * 함수(1) 함수(1)은 1이므로 return 2 * 1, 답은 2 3! 함수(3)이면 3>1 이므로 3 * 함수(2) 함수(2)는 위 계산에 의해 2! 이므로 return 2*1 = 2 3 * 함수(2) = 3 * 2 = 3 * 2 * 1, 답은 6 4! 함수.. 2023. 2. 21.
Python 자료구조 & 알고리즘 - 정렬(버블, 삽입, 선택) 1. 정렬 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것 프로그램 개발 시 빈번하게 정렬을 필요로 함 다양한 알고리즘이 고안되었으며 알고리즘 학습의 필수사항 2. 버블 정렬(bubble sort) 두 인접한 데이터를 비교해서 앞에있는 데이터가 뒤에 있는 데이터보다 크면 (작으면) 자리를 바꾸는 정렬 알고리즘 3. 삽입 정렬(insertion sort) 인덱스(key)앞에 있는 데이터(A)부터 비교해서 key가 더 작으면(크면) 데이터(A)값을 뒤 인덱스로 복사 key가 더 큰 데이터를 만날 때까지 반복 큰 데이터를 만난 위치 바로 뒤에 key를 이동 4. 선택 정렬(selection sort) 주어진 데이터 중, 최소값을 찾음 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함 맨 앞의 위.. 2023. 2. 21.
Python 자료구조 & 알고리즘 - 복잡도 1. 알고리즘 복잡도 표현방법 1-1. 알고리즘 복잡도 계산이 필요한 이유 하나의 문제를 푸는 알고리즘은 다양함 * 정수의 절대값을 구하는 방법 * 방법1 : 값이 음수인지 확인해서 0보다 작은 음수일 때 -1을 곱하기 * 방법2 : 정수값을 재곱한 값에 루트를 씌우기 디양한 알고리즘 중 어떤 알고리즘이 더 좋은지 분석하기 위해 복잡도를 정의하고 계산함 1-2. 알고리즘 복잡도 계산 항목 공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈 시간 복잡도 : 알고리즘 실행 속도 1-3. 알고리즘 성능 표기법 오메가 표기법 알고리즘 최상의 실행 시간을 표기 세타 표기법 알고리즘 평균 실행시간을 표기 빅오 표기법 최악의 실행 시간을 표기 아무리 최악의 상황이라도 이 정도의 성능은 보장함을 의미 가장 많이 사용 1.. 2023. 2. 20.

티스토리툴바