Algorithm

문제 풀이 설명:1번 컴퓨터가 바이러스에 감염되었을 때, 연결된 다른 컴퓨터들에게 바이러스가 퍼진다.이때 1번 컴퓨터를 제외하고 감염된 컴퓨터의 수를 구하는 문제이다.컴퓨터의 연결 정보에서 연결된 컴퓨터들을 탐색해서 바이러스가 퍼지는 과정을 구현해야 한다. 분석:첫째 줄은 컴퓨터의 수 node둘째 줄은 연결된 컴퓨터들의 간선 line그 후에 연결된 컴퓨터 쌍들이 주어진다. 1 2 라면 1번 컴퓨터와 2번 컴퓨터가 연결된다.1번 컴퓨터를 제외한 감염된 컴퓨터의 수를 출력해야 한다. 해결 과정 전에 풀었던 DFS 문제가 오버랩되었다. 노드와 간선이 있으니 인접행렬로 문제를 풀면 된다. BufferedReader br = new BufferedReader(new InputStreamReader(Sy..

문제 풀이 문제 이해하기 설명:주어진 그래프에서 DFS와 BFS 탐색 결과를 구하라.탐색 시 노드 번호가 작은 순서부터 방문한다.입력 조건:노드의 수, 간선의 수, 시작 노드를 입력해야 한다.간선은 양방향이다.출력 조건:DFS 결과와 BFS 결과를 출력한다. DFS와 BFS 간단 설명 DFS는 깊이 우선 탐색이며 한 노드를 방문한 후 그 노드와 연결된 노드를 재귀적으로 탐색한다. 재귀 호출 또는 스택을 사용하여 구현 가능하다. BFS는 너비 우선 탐색이며 한 노드를 방문한 후 연결된 모든 노드를 큐에 넣어 순차적으로 탐색한다. 큐를 사용하여 구현 가능하다. 코드 구조 입력 처리: 노드,간선 정보를 입력받아 인접 행렬을 생성한다. DFS 구현: 재귀 호출을 사용하여 깊이 우선으로 탐..

자바로 개발을 공부하는 김에 오늘부터 그냥 자바로 알고리즘을 하기로 결정했다. 백준 1157번 문제를 풀어보면서 자바로 익숙하게 해보겠다. 문제 풀이 과정 문제를 풀면서 문자열을 배열에 어떤 식으로 넣고 처리해야 할지 고민이 있었다. 대문자는 아스키 코드로 65부터 시작하기 때문에 이것을 활용하여 해결했다. 먼저 입력받은 문자열을 charAt 메서드를 사용해 하나씩 문자로 가져오고 대문자 A를 기준으로 그 문자와의 차이를 계산하여 배열의 인덱스로 사용했다. 각 문자의 빈도를 배열에 저장하고 배열을 알파벳의 숫자인 26만큼 순회하면서 maxCount를 이용하여 가장 빈도가 높은 값을 찾아냈다. 이렇게 최다 빈도 문자를 출력하거나 빈도가 같은 경우 물음표를 출력하도록 구현하였다. import..

문제 : https://www.acmicpc.net/problem/28278 풀이 이 문제는 스택과 관련된 문제이다. 스택을 구현하면서 특정 명령을 처리하는 것이다.예전에 자료구조를 했던 기억이 있어서 거기서 따로 함수별로 나눠서 명령을 처리하던 것이 기억나 그대로 수행하였다. import sysinput = sys.stdin.readlinen = int(input().strip())stack = []def push(x): stack.append(x)def pop(): if stack: print(stack.pop()) else: print(-1)def size(): print(len(stack))def empty(): if sta..

파이썬에서 스택과 큐는 모두 리스트로 구현한다.   스택(Stack) 자료구조 후입 선출 자료구조. ex) 총의 탄창, 급식판 등  스택은 뭔가를 쌓는다는 이미지를 떠올리면 된다. 파이썬에선 리스트를 활용하여 스택을 구현할 건데, 파이썬 리스트를 90도 회전해서 돌린 이미지를 상상하면 된다.   스택은 나중에 들어온 데이터가 먼저 빠져나가게 된다. 중요한 점은, 데이터의 삽입과 추출이 모두 리스트의 뒷부분에서 일어난다는 것이다. 신규 데이터의 삽입은 append()를 활용하며 데이터의 추출은 pop()을 활용하여 메서드로 자연스럽게 스택 자료구조를 구현할 수 있다. 예시 코드로 구현해보겠다.   ▶ 웹 서핑을 하다가 뒤로 가는 경우를 구현visits = [] # 방문 기록지#1. 처음으로 구글에 방문vi..

함수   💡 1. 함수는 def 함수이름(파라미터) 구조로 선언하며, namespace에 등록된다.        2. sum, list 등 built-in예약어(고유한 이름을 가진 예약어) 를 덮어 씌우지 않도록 주의한다.        3. return 이 없다면 반환값이 존재하지 않는다. # 들어온 인자를 리스트로 묶어 반환하는 함수 선언def some_func(pa1, pa2): return [pa1, pa2] print(some_func(1,2)) # [1,2] 실행  # 리턴문 없는 경우는?def some_func(pa1, pa2): my_list = [pa1,pa2] print(some_func(1,2)) # -> NONE 반환print(my_list) # 에러가 뜰 것이다. 지역 ..

간단히 어떤 것들을 필수적으로 알면 좋을지 설명하겠다.  a = 1e9라 하면print(a) 할 대 1000000000.0이 된다그런데 int 붙이면 .0이 사라진다  a = 75.25e1print(a) → 752.5  a = 3954e-3print(a) → 3.954   실수 값을 제대로 비교하지 못해서 원하는 결과를 얻지 못할 수도 있다round()함수를 이용하면 된다 ex) 123.456 을 소수 셋 째 자리까지round(123.456, 2) → 123.46  파이썬에서 기본적으로 나누면 실수형으로 반환한다다양한 로직 설계할 때 나머지 연산자 이용해야 할 경우 많음 %. ex) 짝수 홀수몫만 얻을려면 //          리스트 자료형여러 개의 데이터를 연속적으로 담아 처리하기 위해 사용하는 자료형..

복잡도는 알고리즘의 성능을 나타내는 척도이다.    시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석   동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다.  소스코드가 길고 많은 모듈이 있는 경우 코드가 복잡하다고 할 수 있는데 여기서 단순히 코드가 복잡한건 복잡도가 아니다. 성능적인 부분이 중요한 것임.  시간복잡도가 낮으면 더 빠르게 실행 가능한 것.공간복잡도 낮으면 더 적은 메모리로 실행 가능한 것.빅오 표기법사진 출처: 유튜브 동빈나 가장 빠르게 증가하는 항만을 고려하는 표기법. 빅오 표기법에서는 차수가 가장 큰 항만 남긴다. 최고차항을 보는 것.   일반적으로 빅오..