전체 글171 [백준] 11052 카드 구매하기 11052번: 카드 구매하기 (acmicpc.net) 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제 요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다. PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다. 전설카드 레드카드 오렌지카드 퍼플카드 블루카드 청록카드 그린카드 그레이카드 카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된.. TIL/SW&백준 문제 리뷰 2021. 7. 28. [백준] 9663 N-Queen 9663번: N-Queen (acmicpc.net) 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 내 풀이 처음 이 문제를 접했을 때는 N * N 배열에서 되는 곳과 아닌곳을 체크해나가면서 해결하였었지만 비효율적이였다. 그 당시에 배웠던 다른 방법으로 다시 풀어본 내용이다 복습한 내용 import java.io.BufferedReader; imp.. TIL/SW&백준 문제 리뷰 2021. 7. 22. [백준] 14888 연산자 끼워넣기 14888번: 연산자 끼워넣기 (acmicpc.net) 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다. 예를 들어,.. TIL/SW&백준 문제 리뷰 2021. 7. 22. OS1 OS 역활 : 유저에게 서비스 제공, Memory 랑 I/O Device 관리 OS 요소 I/O Process Main Memory (휘발성 - 전기로 유지) System Bus (연결다리) 주 기억장치 - 보조 기억장치 ( ex 하드 디스크, 데이터 영구(?) 보관) PC = Program counter : 다음에 수행할 명령어 주소 저장 IR = Instruction register : 현재 실행 중인 명령어 저장 MAR = Memory address register : 읽기와 쓰기 연산을 수행할 주 기억장치 주소 저장 MBR = Memory buffer register : 주 기억장치에서 읽어온 데이터 or 저장할 데이터 임시 저장 AC = Accumulator : 연산 결과 임시 저장 I/O AR.. 미가공 필기(운영 체제) 2021. 7. 20. [백준] 14889 스타트와 링크 14889번: 스타트와 링크 (acmicpc.net) 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제 오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에.. TIL/SW&백준 문제 리뷰 2021. 7. 20. 210716 21년도 SCPC 참가 후기 올해 초부터 많이는 아니고 친구들과 매주 백준이나 삼성 소프트웨어 아카데미에서 문제 풀다 보니 어느정도 그래도 할수 있겠다 라는 생각을 갖고 참가했다. 이 대회를 위해 준비를 한 것이 아니라 그냥 코테를 위한 공부였지만 그래도 잘하면 예선 1차 정도는 통과할 수 있지 않을까 싶었지만, 생각보다 내가 더 못했다.... 1학기 기말고사 준비쯔음 부터 계절학기까지 풀로 달려오면서 문제 푸는 것을 소홀히한 영향인지... 특이한 점은 보통 봐왔던 코테는 3~4시간 정도 주고 그 시간내에 풀고 제출인데 이 대회의 경우 24시간 하루를 통으로 주고 그 시간내에 풀어내는 것이였다. 서실 원래 계획은 문제 그래도 깔끔하게 풀어서 1차 예선 통과하고 블로그에 훈장처럼 박제해두려고 했는데 동기부여만 잔뜩 해버렸다 ㅎㅎ;; .. 주저리주저리 2021. 7. 17. 210713 NP vs P Polynomial problems(P) : 다형식 시간으로 해결되는 문제 ex) 정렬 : O(nlog n) , O(n^2) , 등등 Exponential problems(E) : 지수 부분이 n에 따라 무한대로 증가하는 문제 ex) n^n , n^(n^2), 2^n Interactable (Non - Computable) Problems (I) -> 결정할 수 없는 문제 ex) Halting (어떤 프로 그램이 무한 루프에 빠지는지 알아내는 알고리즘) 알고리즘에서 핵심적인 문제 : Exponential 문제를 푸는 법은 아는데 이것을 polynomial time에서 해결하는 방법, 애초에 할 수 있는지를 모름 Ex) 0/1 Knapsack -> O(nW) -> O(2^n) 되면 Exponential 이.. 미가공 필기(알고리즘) 2021. 7. 13. 210712 Matrix Multiplication , 플로이드-와샬(Floyd-Warshall 알고리즘) 모든 쌍의 최단 경로(All Pairs Shortest Path, ASP)의 대표적인 알고리즘 Matrix Multiplication 예시 플로이드-와샬(Floyd-Warshall 알고리즘) 거처가는 정점을 기준으로 최단 거리를 구하는 것 다익스트라,벨만-포드의 경우는 간선 하나씩 늘어나면서 계산, 반면 플로이드-와샬은 경유하는 정점이 하나씩 늘어나면서 계산 D : 그래프의 가중치를 담은 인접행렬 , 모든 쌍의 최단경로 비용 표시 π : 선행자 인접행렬 , 최단 경로 그 자체를 구할 때 사용 k 정점을 거쳤을 때 거리가 그대로거나 더 크다면 그대로 , 작아졌다면 값을 갱신 하는 과정 pseudo code 시간 복잡도 : O(n^3) 공간 복잡도 : O(n^2) 예시 정점의 개수 4 까지 하여 나온 행렬들.. 미가공 필기(알고리즘) 2021. 7. 13. 210709 벨만-포드(Bellman-Ford), 다익스트라(Dijkstra) 최단 경로(Shortest Path)를 찾는 대표적인 알고리즘들 중 일부 벨만-포드(Bellman-Ford) 벨만포드는 가중치가 음수일 경우에도 사용가능 ( 다익스트라와의 차이점 ) 초기화 : 간선 검사 순서 임의로 정하는 등등 앞서 정한 순서대로 모든 간선 확인하며 Relax ( 정점에 기존 보다 더 낮은 가중치로 도달할 수 있으면 값 갱신 == 최단거리 값 갱신) 해줌 정점의 개수 - 1 번 만큼 반복 시간복잡도 : ( 간선의 개수 ) * ( 정점의 개수 -1 ) => O ( 간선의 개수 * 정점의 개수 ) 다익스트라(Dijkstra) Greedy 알고리즘이라고 할 수 있음 그래프 내의 특정 정점에서 갈 수 있는 모든 정점들까지의 최단경로를 구하는 알고리즘 효율적, 실생활에서 많이 사용됨 ex) gp.. 미가공 필기(알고리즘) 2021. 7. 13. 210708 최소 신장 트리 with Kruskal, Prim 알고리 최소 신장 트리 (Minimum Spannig Tree, MST) 신장 트리(spanning Tree) 중에서 사용된 간선들의 가중치 합이 최소인 트리 //신장 트리(spanning Tree) : 모든 정점을 포함하고, 정점 간 서로 연결이 되며 사이클이 존재하지 않는 그래프 Kruskal, Prim 알고리즘은 최소 신장 트리를 구하기 위한 알고리즘 Kruskal 모든 간선들 중에서 가중치가 가장 낮은 간선부터 선택하는 방식 단, 선택하는 과정에서 사이클이 만들어지는 경우에는 선택하지 않는다 n개의 정점을 가지는 그래프일 경우, n-1 개의 간선 선택하면 종료 시간복잡도 : 간선을 오름차순으로 정렬하는 것에 수행시간 좌우되기에 최선의 선택을 한다고 가정하면, O((간선의 수) * log_2 (간선의 수).. 미가공 필기(알고리즘) 2021. 7. 10. 210708 너비 우선 탐색(BFS) & 깊이 우선 탐색(DFS) 너비 우선 탐색(BFS, Breadth - First Search) 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법 즉 깊게 보다 넓게를 우선시한 탐색 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 활용함 BFS의 과정 시작 정점 방문 깊이 1인 모든 노드 방문 깊이 2인 모든 노드 방문.... (반복) 더 이상 방문할 곳 없으면 탐색 마침 노드 방문 세부 과정은 (큐에서 꺼낸) 노드를 방문하였을 경우 큐에서 꺼낸 노드 방문 큐에서 꺼낸 노드와 인접한 노드들 모두 방문 방문한 노드들 큐에 삽입, 더 이상 없다면 큐에서 노드 꺼냄 이런 과정을 반복한다 예시 시간복잡도 : 인접 행렬 사용시 : O(노드수 +간선수) 인접 리스트 사용시 : O(노드수^2) 깊이 우선 탐색(DFS, Dep.. 미가공 필기(알고리즘) 2021. 7. 9. 210707 DP - 배낭 문제 (Knapsack Problem) 배낭 문제 (0/1 Knapsack Problem) 배낭 문제란 배낭에 담을 수 있는 무게의 최대값이 정해져 있고, 일정한 가치와 무게가 정해져있는 짐들을 배낭에 닮을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 0/1 knapsack = 물건 못 쪼갬 Fraction knapsack = 물건 쪼갤 수 있는 문제 사실 kanpsack 문제는 dp에 있어야... 예시 문제 해결법 시간 복잡도 , 공간복잡도 미가공 필기(알고리즘) 2021. 7. 8. 이전 1 ··· 10 11 12 13 14 15 다음 반응형