Problem Solving

이진 탐색 이진탐색은 정렬되어 있는 데이터에서 탐색범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 이진 탐색은 시작점, 끝점, 중간점의 위치 변수 3개를 이용한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다. 단계마다 탐색범위를 2로 나누어 시간복잡도는 O(logN) 이다. (log₂에 비례함) 이진탐색을 구현하는 방법은 재귀함수를 이용하거나, 반복문을 이용한다 이진탐색 문제는 탐색 범위가 큰 상황에서 탐색을 가정하는 문제가 많으므로 탐색범위가 2천만을 넘어가면 사용하는 것을 권장 이미지 출처 재귀함수로 구현 def binary_search(array, target, start, end): if start > end: return None mid = (s..

정렬(sorting) 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 선택정렬(Selection sort) 가장작은 데이터를 찾은 후에 맨 앞에 있는 데이터와 바꾸고, 그 다음으로 가장 작은 데이터를 찾은 후 두번째 데이터와 바꾼다. 가장 낮은 값이 맨 앞부터 정렬되며 전체 배열들이 정렬 될 때까지 이 과정을 계속 반복하여 정렬하는 과정을 선택정렬이라고 한다. 선택정렬은 구현이 간단하지만, 시간 복잡도가 (N^2 + N) / 2 이다. 즉 빅오표기법으로 O(N^2) 이다. 선택정렬은 기본 정렬 라이브러리를 포함해 다른 알고리즘과 비교했을 때 매우 비효율적이다. 선택 정렬 소스코드.py array = [22, 50, 17, 25, 18, 32, 33, 44, 29, 8] for i in range(le..

문제 문제링크 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 T = int(input()) for test_case in range(1, T + 1): s=input() for j in range(1,10): if s[:j]==s[j:2*j]: print(f'#{test_case} {j}') break 회문 문제랑 비슷한 유형의 느낌 문자열의 최대 길이는 30, 마디 최대의 길이는 10이므로 반복문을 0부터 9까지 반복후 문자열을 한 문자씩 리스트로 저장하여 처음 저장된 인덱스부터 j번 전까지 리스트 항목들과 j번 이후부터 2*j번까지 리스트 항목들을 비교하여 조건문이 같으면 같은 문자이므로 해당 문자열..

문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 제출한 풀이 from collections import deque n = int(input()) m = int(input()) graph = [[] for _ in range(n+1)] for i in range(m): a,b = map(int,input().split()) graph[a].append(b) graph[b].append(a) graph[a].sort() graph[b].sort()..

문제 https://level.goorm.io/exam/49094/%ED%83%9C%EB%AF%BC%EC%9D%B4%EC%9D%98-%EC%B7%A8%EB%AF%B8/quiz/1 구름LEVEL 코딩테스트에서 가장 높은 비중을 차지하는 알고리즘 문제를 제작하고 풀이할 수 있는 온라인 저지 서비스입니다. 기업에서 선호하는 C, C++, 파이썬(Python), 자바(Java), 자바스크립트(Javascript) 이 level.goorm.io 풀이 정육면체의 부피는 한변의 길이가 n일 때 n*n*n 이다 길이가 1부터 n까지의 정육면체의 부피들의 합을 구하는 문제인데 반복문을 이용하여 n을 세제곱 하여 합을 구하게 된다면 시간초과로 오답을 출력한다. 반복문으로 구하지말고 세제곱의 합 공식을 이용하여 풀면 된다...

문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net DFS-BFS 기초문제 풀이 # 1260 DFS/BFS from collections import deque # n: 정점의 개수, m: 간선의 개수, v:탐색을 시작할 정점의 번호 n, m, v = map(int,input().split()) graph = [[] for _ in range(n+1)] for i in range(m): a,b = map(..

문제 https://www.acmicpc.net/problem/2527 2527번: 직사각형 4개의 줄로 이루어져 있다. 각 줄에는 8개의 정수가 하나의 공백을 두고 나타나는데, 첫 4개의 정수는 첫 번째 직사각형을, 나머지 4개의 정수는 두 번째 직사각형을 각각 나타낸다. 단 입력 직사 www.acmicpc.net 처음 시도한 풀이(시간 초과) a를 체크할 때 반복문을 너무 많이 사용하여 시간초과가 발생함. x1,y1,p1,q1, x2,y2,p2,q2 = map(int,input().split()) board = [[0 for _ in range(10000)] for _ in range(10000)] def a_check(): area = (p1-x1)*(q1-y1) for i in range(x1,p..

문제 https://www.acmicpc.net/problem/16395 16395번: 파스칼의 삼각형 파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것인데, 블레즈 파스칼(1623-1662)을 따라 이름 붙여졌다. 단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다. N번째 행 www.acmicpc.net 제출한 풀이 n, k = map(int,input().split()) num_list = [[1],[1,1]] for i in range(2, n): t = [1] for j in range(1,i): t.append(num_list[i-1][j-1] + num_list[i-1][j]) t.append(1) num_list.append(t) print(num_list[n-1][k..

문제 - BOJ https://www.acmicpc.net/problem/17614 17614번: 369 민수는 같은 반 친구들과 369게임을 하고 있다. 369게임은 여러 명이 원형으로 둘러 앉아 시작 위치의 사람이 1을 외치며 시작된다. 이후 시계방향으로 돌아가며 2, 3, 4와 같이 1씩 증가된 수가 자 www.acmicpc.net 풀이 import sys input = sys.stdin.readline res = 0 for i in range(1, int(input())+1): res += str(i).count('3')+str(i).count('6')+str(i).count('9') print(res) 파이썬으로 실행하면 문자열이 아닌 정수형으로 다룬다면 시간초과가 발생하지 않을듯 pypy로 실..

문제 https://www.acmicpc.net/problem/2477 2477번: 참외밭 첫 번째 줄에 1m2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1 ≤ K ≤ 20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지 www.acmicpc.net 풀이 ( A넓이 - B넓이 ) X (면적당 참외 수) 하면 간단한 문제 B의 길이와 넓이를 구하면 문제를 쉽게 풀 수 있음 B의 길이와 넓이를 구하는 방법은 문제에서 방향, 거리 를 입력 받게 되는데 입력 리스트들 중에서 한 방향이 하나의 인덱스를 건너뛰고 또 나오게 된다면 (위의 그림에서 빨강, 파랑 부분) 그 중간의 인덱스가 가리키는 값이 B의 가로, 세로 길이가 됨. 이때 인덱스가 리..