본문 바로가기

분류 전체보기132

[백준] 1038 파이썬 - 감소하는 수 문제https://www.acmicpc.net/problem/1038 풀이진짜 너무 오래걸려서 풀었다. 첫번째 풀이감소하는 수의 입력 조건이 1,000,000 이하인줄 알고 for문을 돌며 감소하는 수인지 검사했다.문제를 푼 후 제출했을 때 31퍼센트에서 계속 '틀렸습니다'가 떠서 머리를 쥐어뜯었다.알고 보니, 감소하는 수 중 가장 큰 수인 9876543210까지 구해야 하는 거였다.입력 조건은 N번째 감소하는 수를 구할 때의 N의 조건이었다. (문제 좀 잘 읽자.. ) 두번째 풀이1부터 9876543210 사이 수를 for문으로 돌리고, 시간복잡도를 줄일 for문을 탈출하는 조건을 추가해야된다고 생각했다.사실 조건부터 시간복잡도가 말이 안된다. 이건 아닌 것 같았다.dp문제인가 싶었지만 부합하는 조건을.. 2024. 9. 20.
[백준] 23881 파이썬 - 선택 정렬 1 문제https://www.acmicpc.net/problem/23881 풀이선택정렬 알고리즘을 사용해서 문제를 풀면 된다. 선택 정렬이란?1. 주어진 리스트 값 중에 최소값을 찾는다.2. 그 값을 맨 앞에 위치한 값과 swap 한다.3. 위 작업을 반복한다. - 선택 정렬의 시간복잡도 : O(N^2)- 공간 복잡도: O(1)  코드n,k = map(int,input().split())numbers = list(map(int,input().split()))cnt = 0def selection(numbers): global cnt ans = [] for i in range(n-1, 0, -1): max,index = numbers[0],0 for j in range(.. 2024. 9. 17.
[백준] 2583 파이썬 - 영역 구하기 문제https://www.acmicpc.net/problem/2583 풀이입력에 따라 직사각형을 입력받고,bfs를 통해 영역을 판별하여 넓이를 구하면 되는 문제이다. 입력을 받을 때, 모눈종이의 왼쪽 아래 꼭짓점의 좌표가 (0,0)으로 선언되어있어 약간 헷갈렸으나우리가 아는 대로(왼쪽 위가 (0,0)좌표) 코드를 작성해도 답을 도출하는 데에는 전혀 문제가 없다. 코드from collections import dequerow, column, k = map(int,input().split())matrix = [[1 for _ in range(column)] for _ in range(row)]for _ in range(k): lx,ly,rx,ry = map(int,input().split()) f.. 2024. 9. 9.
[프로그래머스] 42890 파이썬 - 후보키 풀이문제에서 relation이라는 2차원 문자열 배열 안에 학생들의 인적사항이 주어진다.인적사항의 column(열) 속성들에 대해, 유일성과 최소성을 만족하는 "후보키"를 구하는 문제이다.  다음과 같이 컬럼의 길이는 최대 8로 주어진다.따라서 파이썬의 combinations를 사용하여 모든 컬럼의 조합을 구했다. (조합의 시간복잡도는 2 ^ 컬럼의 길이 = 256) 1. 모든 컬럼의 조합을 구한다.2. 각 조합에 대해 유일성을 검사한다    2-1. 집합(set()) 에 각 조합의 인덱스의 값들을 문자열로 변환한 값을 넣는다.    2-2. 만약 해당 집합의 길이가 row의 길이와 같으면 겹치는 값이 없는 것이므로 유일하다.3. 유일한 조합들을 모아놓은 candidate 리스트에 대해 최소성을 검사한다.. 2024. 9. 9.
[프로그래머스] 12978 파이썬 - 배달 풀이문제를 읽어보면 1번 마을에서 다른 마을까지 거리 중 최단 거리를 구하는 문제임을 알 수 있었다. 이때, 제한사항을 읽어보니 노드(마을의 개수)가 최대 50개임을 알 수 있었다.따라서 다익스트라 알고리즘을 사용하여 풀 수 있는 문제였다. 다익스트라 알고리즘 CT-Study/PART 2/Chapter 9, 최단 경로.md at master · JeongEunJi1127/CT-Study🔎 코딩테스트 공부 결과물 정리를 위한 저장소 . Contribute to JeongEunJi1127/CT-Study development by creating an account on GitHub.github.com- 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘- 가장 비용이 적은 노드를.. 2024. 9. 9.
[C++] c++ 공부.. 해야겠지? (1) 최근 NHN 코딩테스트에서 주력 언어인 Python을 사용할 수 없었다.앞으로도 이런 일이 반복될 수 있기도 하고, 언리얼 엔진이 c++을 사용하기 때문에 지금부터라도 차근차근 c++을 공부해보기로 했다.  1. c++이란?c++은 고급 언어로 0,1만 이해하는 기계어와 달리 인간이 비교적 이해하기 쉽게 만들어진 언어이다.더보기더보기자연어 - 인간이 이해하기 쉬운 High-Level 언어기계어 - Low-Level 언어  2. 주석1. 한 줄 주석// 주석주석주석주석/* 주석주석주석주석 */2. 두 줄 이상 주석// 주석// 주석/* 주석주석 */  3. 출력cout  cout와 endl은 iostream 안에 정의되어 있다. iostream이란?- input / output stream이라는 뜻의 헤더.. 2024. 9. 5.
[프로그래머스] 67256 파이썬 - 키패드 누르기 풀이키패드의 숫자와 각 숫자에 맞는 좌표를 미리 딕셔너리에 선언해두고 풀었다.나머지는 단순 구현이었다.if문을 사용해 조건만 잘 걸어주면 어렵지 않게 풀 수 있는 문제였다. 코드def solution(numbers, hand): answer = '' keypad = {'1':(0,0), '2':(0,1), '3':(0,2), '4':(1,0), '5':(1,1), '6':(1,2), '7':(2,0), '8':(2,1), '9':(2,2), '*':(3,0), '0':(3,1), '#':(3,2)} left = keypad['*'] right = keypad['#'] for number in numbers: .. 2024. 9. 5.
[백준] 15686번 파이썬 - 치킨 배달 문제https://www.acmicpc.net/problem/15686코드from itertools import combinationsimport sysinput = sys.stdin.readlinen,m = map(int,input().split())city = []chicken = []house = []def CalculateDistance(chicken): value= 0 for i in house: nx,ny = i distance = int(1e9) for j in chicken: x,y = j distance = min(distance,abs(nx-x) + abs(ny-y)) value += d.. 2024. 8. 30.
[백준] 18405번 파이썬 - 경쟁적 전염 문제 코드from collections import dequeimport sysinput = sys.stdin.readlinen,k = map(int,input().split())array = []virus = []# 배열 초기화for i in range(n): array.append(list(map(int,input().split()))) for j in range(n): if array[i][j] != 0: virus.append((array[i][j],0,i,j))virus.sort()queue = deque(virus)# s초 후에 (x,y) 위치에 바이러스 s,x,y = map(int,input().split())# 상하좌우dx = [0,0,-1,1]d.. 2024. 8. 27.

티스토리툴바