본문 바로가기

분류 전체보기464

[백준] 1300번 K번째 수 사용 언어 - Python3 1300번: K번째 수 (골드2, 이분 탐색) 문제 ★이분 탐색 문제★ 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 정답 i*j 배열의 규칙을 알아내는 이분탐색 문제!! 1~k 범위를 줄여가며 검색한다. (코드 풀이) 1. 변수 선언 n 배열의 크기 k b의 인덱스 2. 이분 탐색 정의 몇 번째인지 인덱스를 구해야하므로 k의 범위를 이분 탐색한다. 배열은 항상 1*1로 시작하기 때문에, start =1로 한다. end = k까지만 진행해서 더이상의.. 2023. 1. 21.
[백준] 2110번 공유기 설치 사용 언어 - PyPy3 2110번: 공유기 설치 (골드4, 이분 탐색) 문제 ★이분 탐색 문제★ 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net python3으로는 시간 초과로 오답이지만, pypy3으로는 정답! 이분탐색은 while문으로 돌아가서 python보다 빠른 pypy3으로 했을 때만 정답이 나올 수 있다. 정답 집 좌표값의 차이를 start/end/mid 값을 지정하는 이분탐색 문제 !! (코드 풀이) 1. 변수 선언 n 집의 개수 c 공유기의 .. 2023. 1. 21.
[백준] 2805번 나무 자르기 사용 언어 - Python3 2805번: 나무 자르기 (실버2, 이분 탐색) 문제 ★이분 탐색 문제★ 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 정답 시작/끝/중간값을 선언하여 중간값과 같을때까지 범위를 줄이는 이분탐색 문제 !! (코드 풀이) 1. 변수 선언 나무의 수 n개 나무의 길이 m개 tree는 정렬된 상태로 입력받기 2. 이분 탐색 정의 높이가 1 이상, max(tree) 이하 여야 자를 수 있기 때문에, 시작점은 1 , 끝점은 max(tree)로 선언한.. 2023. 1. 21.
[백준] 10816번 숫자 카드 2 사용 언어 - Python3 10816번: 숫자 카드 2 (실버4, 이분 탐색) 문제 ★이분 탐색 문제★ 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 정답 시작/끝/중간값을 선언하여 중간값과 같을때까지 범위를 줄이는 이분탐색 문제 !! (코드 풀이) 1. 리스트 원소별 개수 구하기 mycard를 sorted 정렬하여 입력받는다. 정렬한 내카드를 한개씩 확인하면서 개수를 센다. count = {} 딕셔너리를 만들어서 여러개일 경우 중복 개수를 세준다. list_1 = [1, .. 2023. 1. 21.
[백준] 1920번 수 찾기 사용 언어 - Python3 1920번: 수 찾기 (실버4, 이분 탐색) 문제 ★이분 탐색 문제★ 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 정답 시작/끝/중간값을 선언하여 중간값과 같을때까지 범위를 줄이는 이분탐색 문제 !! (코드 풀이) 0. 이분 탐색 전 정렬하기 이분 탐색을 하기 위해선 탐색 기준이 정렬되어 있어야한다. a를 정렬한 후 arr과 비교해야 a의 탐색 범위를 줄이는 의미가 있기 때문이다. 1. 시작/끝/중간 값 선언 n 범위 안에서 ar.. 2023. 1. 21.
[백준] 1874번 스택 수열 사용 언어 - Python3 1874번: 스택 수열 (실버2, 스택) 문제 ★스택 문제★ 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 정답 스택 문제 !! (코드 풀이) 1. stack 쌓기 cur 변수를 이용해서 입력값인 num과 같아질때까지 1씩 증가시키며 빈 리스트 stack에 append해준다. cur == num 인 경우, stack의 마지막 원소인 stack[-1]은 num과 같아질 것 이고, 이 때 pop을 진행.. 2023. 1. 20.
[백준] 9012번 괄호 사용 언어 - Python3 9012번: 괄호 (실버4, 스택) 문제 ★스택 문제★ 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 정답 간단한 스택 문제 !! (내 코드 풀이) 열린 괄호를 스택에 넣어, 닫힌 괄호가 있으면 열린 괄호 한개를 빼주는 형태. 열린 괄호인 경우, 스택에 append / 닫힌 괄호인 경우, 스택에 pop 닫혔으나 스택에 아무것도 없는 경우 ans = False로 하여, 더이상의 for문을 진행하지 않고 break. 최종적으로 스택에 아무것도 안남아있고.. 2023. 1. 20.
[백준] 10773번 제로 사용 언어 - Python3 10773번: 제로 (실버4, 스택) 문제 ★스택 문제★ 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 정답 간단한 스택 문제 !! 스택을 활용해야 한다는 것을 알고, 문제를 풀어서 너무 쉽게 맞췄어요. 문제에 대해 아무런 정보가 없는 상태에서도 스택을 사용해야한다고 알게 될 때까지 열심히 파이팅! :) (내 코드 풀이) 스택의 "선입후출" 구조만 이해하면 되는 문제 # 정답 k = int(input()) stack = [] for i in ran.. 2023. 1. 20.
[백준] 10828번 스택 사용 언어 - Python3 10828번: 스택 (실버4, 스택) 문제 ★스택 문제★ 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 정답 간단한 스택 문제 !! 이제 스택은 마스터한것 같아서 기분이 매우 좋네요 :) (내 코드 풀이) 스택의 "선입후출" 구조만 이해하면 되는 문제 빈 리스트 stack을 선언한다. 리스트의 append(추가), pop(가장 마지막으로 들어온 원소 삭제)을 이용해서 각각의 명령문에 대한 코드를 작성한다. # 정답 n = int(input()) command = .. 2023. 1. 20.
[백준] 14889번 스타트와 링크 사용 언어 - Python3 14889번: 스타트와 링크 (실버2, DFS 백트래킹 문제) 문제 ★백트래킹 문제, 삼성 SW 역량 테스트 기출 문제 ★ 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 정답 DFS 백트래킹 재귀함수 조합 문제 !! 다른 분들 답중에 가장 좋다고 생각하는 풀이법 2가지로 공부했습니다. 맨 아래에 링크를 올립니다! 1. 방문 여부에 따라 팀 지정하는 방법 1팀은 2팀이 방문하지 않은 곳, 2팀은 1팀이 방문하지 않은 곳으로 생각한다. visited[i]를 순차적으로 방문해서 visited를 True로 해.. 2023. 1. 20.

티스토리툴바