전체 글76 암호 만들기(BJ_G5_1759) 1. 문제 링크 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 2. 나의 코드 메모리: 14712kb 시간: 136ms 코드 길이: 1402B 설명: 순열을 사용해서 모든 경우의 수를 구한다. 시간복잡도 : O(N!) 하지만 만약 그 전의 알파벳과 비교해 정렬이 되지 않은 문자가 있으면 백트래킹을 한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputSt.. 2024. 2. 21. 제목(사이트_난이도_문제번호) 1. 문제 링크 2. 나의 코드 메모리: kb 시간: ms 코드 길이: B 시간 복잡도 : 설명: /* 코드 넣는 곳 */ 3. 정답 코드 /* 정답 코드1 */ /* 정답 코드2 */ 4. 배운 점 2024. 2. 21. 그래프 1. 그래프의 종류 - 정점 중심으로 해결 : 인접 행렬, 인접 리스트 >> 최소 신장트리 : 프림, 최단 경로 : 다익스트라 - 간선 중심으로 해결 : 간선 리스트 >> 최소 신장 트리 : 크루스칼, 최단 경로 : 벨만포드 ※ 선형 자료구조(1 : 1), 비선형 자료구조(1 : N or N : N) 2. 그래프 - 정점 : 그래프의 구성요소로 하나의 연결점 - 간선 : 두 정점을 연결하는 선 - 차수 : 정점에 연결된 간선의 수 (인접 정점의 수) - 트리도 그래프이다. - 종류 3. 인접 행렬 - V x V 정방 행렬 - 행 번호와 열 번호는 그래프의 정점에 대응 - 두 정점이 인접되어 있으면 1, 그렇지 않으면 0으로 표현 - 보통 2차원 배열로 생성 - 메모리 초과 위험 4. 인접 리스트 - Ar.. 2024. 2. 15. 그리디 알고리즘(탐욕법) 1. 그리디 알고리즘 - 최적 해를 구하는 데 사용되는 근시안적인 방법 - 여러 경우 중 하나를 선택 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식 - 각 선택 시점에서 이루어지는 결정은 지역적으로 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없다. - 한번 선택된 것은 번복하지 않는다. 2. 그리디 vs 다이나믹 프로그래밍 분류 그리디 알고리즘(Greedy Algorithm) 동적 계획법(DP: Dynamic Programming) 설명 각 단계에서 최적의 선택을 하는 방식으로 문제를 해결하는 방식 작은 문제의 해를 메모이제이션하여 중복 계산을 피하고, 이를 이용하여 큰 문제를 해결하는 방식 성립 조건 1. 탐욕 선택 속성(Gre.. 2024. 2. 13. 완전탐색 응용, Next Permutation 1. 비트마스킹 순열 package com.algo.day9; import java.util.Arrays; import java.util.Scanner; public class BitmaskingPermutationTest { static int N, R, input[], numbers[]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); R = sc.nextInt(); input = new int[N];// 입력 수 배열 numbers = new int[R];// 순열 저장 배열 for (int i = 0; i < N; i++) { input[i] = sc.nextInt(); } .. 2024. 2. 8. DFS, 우선 순위 큐 1. DFS 1) DFS란 - 깊이 우선 탐색 - 루트 노드에서 출발하여 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 노드로 되돌아와서 다른 방향의 노드로 탐색을 계속 반복하여 결국 모든 노드를 방문하는 순회방법 - 스택을 사용 2. 이진트리 순회 1) 순회 방법 - 전위 순회 : VLR - 중위 순회 : LVR - 후위 순회 : LRV public void dfsByPreorder() { if (isEmpty()) { System.out.println("==========preorder========"); dfsByPreorder(1); System.out.println(); } } private void dfs.. 2024. 2. 7. CS 면접 준비 자료 https://github.com/WeareSoft/tech-interview GitHub - WeareSoft/tech-interview: :loudspeaker:🙍 tech interview:loudspeaker:🙍 tech interview. Contribute to WeareSoft/tech-interview development by creating an account on GitHub.github.com https://github.com/brave-people/brave-tech-interview GitHub - brave-people/brave-tech-interview: 🙋 핵심을 질문하다. 그리고 용감하게 대답하다. 국내 IT기업부🙋 핵심을 질문하다. 그리고 용감하게 대답하다. 국.. 2024. 2. 6. Tree, BFS 1. 트리 1) 트리의 개념 - 비선형 구조 - 원소들 간에 1:N 관계를 가지는 자료구조 - 원소들 간에 계층관계를 가지는 계층형 자료구조 - 상위 원소에서 하위 원소로 내려가면서 확장되는 트리모양의 구조 2) 트리의 용어 - 노드 : 트리의 원소 - 루트 : 최상위 노드 - 형제 노드 : 같은 부모 노드의 자식 노드들 - 조상 노드 : 산선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들 - 서브 트리 : 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리 - 자손 노드 : 서브 트리에 있는 하위 레벨의 노드들 - 노드의 차수 : 노드에 연결된 자식 노드의 수 - 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값 - 단말 노드 : 차수가 0인 노드 - 노드의 높이 : 루트에서 노드에 .. 2024. 2. 6. LinkedList 1. 리스트 1) 리스트란? - 순서를 가지는 데이터의 집합 - 값의 중복을 허용한다. - 순차 리스트와 연결 리스트로 나뉜다. 2) 순차 리스트 - 1차원 배열에 항목들을 순서대로 저장한다. - 데이터의 종류와 구조에 따라 구조화된 자료구조를 만들어 배열에 저장할 수도 있다. - 배열의 인덱스를 이용해 원하는 위치의 데이터에 접근할 수 있다. - 삽입 삭제 연산의 최악의 시간복잡도는 O(n) - 메모리 낭비, 새로운 배열 생성등의 문제가 있다. 3) 연결 리스트 - 개별적으로 위치하고 있는 각 원소를 연결하여 하느의 전체적인 자료구조를 이룬다. - 자료구조의 크기를 동적으로 조정 가능, 메모리의 효율적인 사용이 가능 - 삽입, 삭제 연산에 유리, 조회 연산은 불리 2. 연결 리스트 1) 기본 구조 - .. 2024. 2. 5. 이전 1 ··· 3 4 5 6 7 8 9 다음
