기록장

문제https://www.acmicpc.net/problem/1707완전탐색 활용 문제 너무 어려워..! 근데 구현 아이디어를 알고 나니까 코드 짜는 건 좀 재밌었다풀이🥹 처음 아이디어노드를 두 그룹으로 나눌 때, 같은 그룹 끼리는 간선이 없어야 함 이 개념만 가지고 노드를 두 그룹으로 어떻게 나눠야 할까 생각했다. 1. 간선이 있으면 다른 그룹으로 나누는 작업을 반복 -> 끝까지 진행 후 총 2그룹이면 YES  -> 고민: 같은 그룹인지 어떻게 구분함..?   -> 그룹이 뭔지 저장하는 group[v+1]을 만들고 노드 1부터 순차 탐색, 인접하지 않은 노드를 발견하면 다 같은 그룹으로 표시하기  -> 근데 이 방법은 시간 복잡도가 O(V^2)이기 때문에 틀린 풀이 (제한 시간 2초, V2. 단, 어..

문제https://www.acmicpc.net/problem/2178풀이이차원 배열 matrix에 0과 1을 저장하고 (0,0)부터 bfs 탐색한다.각 좌표를 노드 객체로 표현한다. 노드 객체는 행, 열, (0,0)부터 현재 좌표까지 도달하는 데 필요한 거리값을 가지고 있다.큐에서 좌표 하나를 꺼내서 다시 그 좌표의 인접 좌표들을 큐에 다시 넣는데, 이 작업을 할 때 노드의 w값을 현재 좌표의 w값+1로 증가시켜준다.큐에서 꺼낸 값이 (n-1,m-1)노드이면 그 w값을 출력한다.코드import java.io.*;import java.util.*;public class Main { static int n, m; static boolean[][] visited; static int[][] m..

@TagAPI 그룹 지정. Tag에 설정된 name이 같은 것끼리 하나의 API 그룹으로 묶는다. Controller 또는 Controller의 메서드 영역에 설정한다. REST API의 엔드포인트는 컨트롤러에 있으므로, 컨트롤러 클래스 위에 @Tag어노테이션을 붙여서 API 그룹을 설정할 수 있다. Target - ANNOTATION_TYPE, METHOD, TYPEname : 태그 이름description : 태그 설명@Tag(name="User", description="사용자 API")@RestController@RequestMapping("/users")public class UserApiController { //Post, Get, Patch, ... 에 해당하는 메서드들} @Operat..

Swagger을 설치하다가 내 애플리케이션이 single-page application(SPA)이면 swagger-ui를 쓰고, 그게 아니면 swagger-ui-dist를 쓰라는 말이 있길래, SPA를 찾아보다가 서블릿까지 와버렸다!MPA (Multi Page Application)SPA가 한 개의 페이지로 구성된 애플리케이션이라면 MPA는 그 반대! 여러 페이지로 구성된 애플리케이션이다. 그러니까 그게 무슨 말이나면. 클라이언트가 페이지를 접속할 때마다 HTTP Request로 서버에게 페이지 접속 요청을 보낸다는 사실은 이미 다 알 것이다. 예전에는 클라이언트의 요청이 있을 때마다 서버에서 페이지를 매번 새로 보내줬었다. 예를 들어 동적 요청이 있다면 서버는 요청에 맞게 데이터베이스에서 데이터를 꺼..

API 문서를 작성해보자. 나는 HTTP 프로토콜을 사용하는 REST API를 사용할 것이기 때문에 먼저 HTTP 프로토콜의 주요 개념과 REST API가 어떻게 동작하는지 먼저 간단히 정리하고 Swagger 설치하는 법을 알아보도록 하겠다. REST APIREST API 설계 원칙REST는 HTTP 기반으로 클라이언트가 서버의 리소스에 접근하는 방식을 규정한 아키텍처이다. REST한 방식으로 API를 설계하려면 원칙이 있다. 자원(URI), 행위(HTTP request method), 표현(payload)를 사용하기URI는 리소스를 표현리소스에 대한 행위는 HTTP request method로 표현. URI로 표헌하지 않기이런 이론적인 얘기를 먼저 하면 당연히 안 와닿을테니 예시를 보자. 회원 관리 시..

문제https://www.acmicpc.net/problem/5639이진 검색 트리를 전위 순회한 결과를 보고 후위 순회한 결과를 구하는 문제이다.풀이파이썬 EOF 입력 처리?eof (end of file) : 파일 입출력 시 끝날 때까지 읽어들이는 readline()과 같은 내장 함수를 쓸 때 사용되는 개념sys.stdin.readline()함수는 eof를 만났을 때 except가 아니라 빈 문자열("")을 반환함파이썬 내장 함수 input()은 eof를 만났을 때 except를 반환함입력값에 입력 종결 규칙이 없을 때, 아무 것도 입력하지 않은 경우 빠져나와야 하므로 readline()은 빈 문자열이 들어올 때, input()은 except가 발생했을 때 break 처리를 해주면 됨while True..

문제https://www.acmicpc.net/problem/1197풀이크루스칼 알고리즘을 사용해 최소 스패닝 트리를 만들었다. 시간 초과 원인?가중치가 가장 큰 간선에서 비로소 스패닝 트리가 만들어질 수도 있으므로, 어차피 최악의 경우에는 모든 간선을 확인해야 함시간 초과의 근본적인 원인은 union-find에 어떤 최적화도 적용되어 있지 않아 높이가 아주 높은 트리가 만들어질 수 있기 때문 해결 방법union 함수에서 parent 합치기# 시간 초과def union(a, b): a_ = find(a) b_ = find(b) if a_>b_: p[a_]=b_ else: p[b_]=a_rank = [1] * (v+1) # 트리의 랭크(높이) 저장def un..

전위, 중위, 후위 순회를 재귀로 푸는 문제이다.처음에 left, right 노드 저장 방식을 잘못 받아서 구현하는 데 애를 먹다가 옆자리 동료분한테 물어봤는데 정석 풀이가 있었다.root 노드를 아스키 코드로 변경한 숫자를 인덱스로 하는 곳에 left, right 노드를 저장하는 방법이다.해당 노드의 왼쪽 자식을 저장하는 l, 오른쪽 자식을 저장하는 r 리스트를 사용하면 재귀로 쉽게 풀 수 있다.import sysn = int(sys.stdin.readline())l = [None]*26r = [None]*26for _ in range(n): node, left, right = map(str, sys.stdin.readline().split()) if left != '.': l[ord(nod..

최소 스패닝 트리신장 트리 (Spanning Tree)그래프에서 일부 간선을 선택해 만든 트리최소 연결로 이루어짐 즉, 모든 노드가 가장 적은 간선 수로 이어져있는 경우에 해당정점이 n개일 때 간선이 n-1개이면 스패닝 트리BFS, DFS로 신장 트리 찾기 가능 (탐색 도중 사용한 간선을 모으면 됨)최소 비용 신장 트리 (Minimum Spanning Tree, MST)스패닝 트리 중 사용된 간선들의 가중치 합이 최소인 트리각 간선의 가중치가 동일하지 않을 경우, 단순히 적은 간선을 쓴다고 최소비용이 되는 건 아님사이클이 없어야 함구현 방법으로는 Kruskal, Prime 알고리즘이 있는데 둘 다 그리디한 방법임Kruskal Algorithm간선을 비용이 낮은 것부터 v-1개 선택하며 떨어져있던 노드를 ..