CS/Algorithm 문제
[BaekJoon] 백준 2606번 바이러스
[BaekJoon] 백준 2606번 바이러스 문제: https://www.acmicpc.net/problem/2606 내코드 간단하게 bfs로 풀 수 있는 탐색문제였다. dfs로도 풀 수 있을 것 같은데 다음에는 dfs로도 풀어봐야겠다. # BaekJoon2606.py from collections import deque def solution(N, M): link = [[] for _ in range(N)] visited = [False for _ in range(N)] for i in range(M): a, b = map(int, input().split()) link[a - 1].append(b - 1) link[b - 1].append(a - 1) qu = deque([0]) visited[0] ..
[BaekJoon] 백준 17626번 Four Squares
[BaekJoon] 백준 17626번 Four Squares 문제: https://www.acmicpc.net/problem/17626 내코드 문제 내용은 간결했지만 어떤식으로 풀어야 할지 생각이 필요했던 문제다. 더군다가 시간도 0.5초로 짧은 편이라서 무작정 구현하기에는 무리였다. 문제에서 가장 중요한 조건은 결국 어떤 수든 답은 1, 2, 3, 4 중에 하나라는 의미이다. 즉, 주어진 수가 정수의 제곱수면 1, 어떤 정수 i에 대해 n - i^2의 제곱근이 정수면 2, 어떤 정수 i, j에 대해 n - i^2 - j^2의 제곱근이 정수면 3, 그외의 경우는 모두 4라는 의미이다. # BaekJoon17626.py def solution(n): # n이 제곱근이 정수라면 답은 1 if int(n**0..
[BaekJoon] 백준 1931번 회의실 배정
[BaekJoon] 백준 1931번 회의실 배정 문제: https://www.acmicpc.net/problem/1931 내코드 처음에는 이해하기 어려워서 고민하다가 다른 분들은 어떻게 풀었는지 참고해서 풀었다. 핵심은 빨리 끝나는 순으로 정렬 후 끝나는 시간이 같다면 빨리 시작하는 순으로 정렬하는 것! 어쨌건 현재 상황에서 가장 최선의 선택(빨리 끝나는 순으로 정렬)을 한다는 점에서 그리디 알고리즘이라고 볼 수 있다. 코드에서 파이썬의 sort함수를 사용해 줬고, 그 안에 lamda라는 인자가 있는데 처음엔 처음 보는 lamda라서 뭔지 찾아보고 구현했다. 아래와 같이 써주면 e라는 배열을 정렬할건데, 0번째 값을 우선으로 오름차순으로 나열하고, 이후에 1번째 값을 기준으로 내림차순으로 구현한다는 의미..
[BaekJoon] 백준 1927번 최소 힙
[BaekJoon] 백준 1927번 최소 힙 문제: https://www.acmicpc.net/problem/1927 내코드 우선 순위큐에서 힙을 이용해 푸는 문제다. 파이썬에는 힙 모듈이 있어 이를 이용해서 풀었다. # BaekJoon1927.py import sys import heapq input = sys.stdin.readline number = int(input()) heap = [] for _ in range(number): num = int(input()) if num != 0: heapq.heappush(heap, num) else: try: print(heapq.heappop(heap)) except: print(0)
[BaekJoon] 백준 11659번 구간 합 구하기 4
[BaekJoon] 백준 11659번 구간 합 구하기 4 문제: https://www.acmicpc.net/problem/11659 내코드 우선 문제를 처음 봤을 때 주어진 숫자를 가지고 정직하게 풀었을 때 시간이 부족할 것이라는 생각이 들었다. N개의 숫자들 중에서 특정 구간을 M번 더해야 하는 경우를 생각해보면, 최악의 경우 100,000(처음부터 끝까지 모든 수(N의 최대값)를 더했을 때 덧셈의 횟수) X 100,000(합을 구해야 하는 횟수 M의 최대값)은 1억을 넘어가고 1억을 약 1초라고 했을 때 한참 넘어가기 때문이다. 그래서 생각한 방식이 첫번째 수부터 n번째 수까지 더한게 f(n)이라고 하면 i번째~j번째 구간의 합은 f(j) - f(i - 1)로 계산하자는 것이다. 이 방식으로 하면 위..
[BaekJoon] 백준 1992번 쿼드트리
[BaekJoon] 백준 1992번 쿼드트리 문제: https://www.acmicpc.net/problem/1992 내코드 문제를 이해하는게 제일 어려웠다. 주어진 설명으로 이해가 가지 않았다. 다른분들이 써놓은 걸로 문제를 이해 했는데, 배열이 주어지면 모두 같은 수 인지 확인하고 맞으면 해당 수를 넣고, 아니면 4등분해서 각각 같은 수 인지 확인하고.. 반복하는 것이다. 간단하게 재귀로 풀었다. 4등분으로 나누고 다시 4등분으로 나누고.. 이렇게 반복하는 과정에서 재귀가 떠올랐다. 다만 재귀로 풀 때에는 조건에 맞게 종료해주는게 중요하다. 특정 조건에 충족했을 때 맞는 값을 반환하는 것이 그나마 제일 까다로웠다. # BaekJoon 1992.py def solution(arr, pos, x, y, ..
[BaekJoon] 백준 1541번 잃어버린 괄호
[BaekJoon] 백준 1541번 잃어버린 괄호 문제: https://www.acmicpc.net/problem/1541 괄호를 쳐서 최소값이 나오게 만들라는 문제였다. 예시를 보면 55-50+40 의 경우 (55-50+40)이면 45이지만 55-(50+40)이면 -35이다. 이렇게 괄호 위치에 따라 값이 달라질 수 있다. 우선 별다른 알고리즘이 생각나지 않아 규칙을 생각해보았다. 식이 주어졌을 때, - 뒤의 계산값이 크면 클수록 좋고, - 앞의 계산값은 작으면 작을 수록 우리가 원하는 값이 나온다. 두가지로 경우를 나눌 수 있다. (연속으로 같은 연산자가 나올 수 없기 때문) 먼저 -가 먼저 나올 경우 80-30+20-30 이와 같이 나오면 80-(30+20)-(30) 이와 같이 괄호를 치면 모두 음..
[BaekJoon] 백준 1389번 케빈 베이컨의 6단계 법칙
[BaekJoon] 백준 1389번 케빈 베이컨의 6단계 법칙 문제: https://www.acmicpc.net/problem/1389 문제를 보고 친구 관계가 연결되어 있고, 관계를 하나하나 따라 들어가 몇단계인지 찾는다는 부분에서 이거 뭔가 탐색 문제일 것 같은데..! 라는 생각이 들었다. 이어서 최단 경로의 단계를 찾는다는 부분에서 이건 bfs다 라는 생각으로 이어졌다. 어떤 유형의 문제인지 알았으니 이제 입력 받은 데이터를 어떻게 넣어서 bfs를 통해 풀면 될것 같은데, 어떤 자료구조로 넣지? 생각하다가 그래프의 두가지 표현 방식인 1) 인접 리스트(1: 2, 4, 5 / 2: 1, 5 / ...) 2) 인접 행렬(arr[i][j]로 표현)이 떠올랐다. 그중에서 나는 특정 점에 연결된 점들을 찾는..