본문 바로가기

CodingTest/백준알고리즘BOJ

백준알고리즘python_오큰수_스택 # https://www.acmicpc.net/problem/17298 import sys sys.stdin = open("input.txt", "rt") from collections import deque sys.setrecursionlimit(10000) ''' 이 문제는 스택을 사용한다. 특이한 점은, 스택에 일반적인 경우와 같이 값을 저장하는 것이 아니라, idx를 저장한다는 것이다. 최종적인 답. 인 result 배열을 선언해준다. 오큰수가 없는 idx 값을 위해 모든 원소를 -1로 초기화해준다 stack에는 idx가 들어간다고 했다. 우리는 stack의 맨 위 값, 즉 stack 맨위에 저장된 idx, 그 idx에 위치한 값과, 현재 우리가 보고 있는 nums[i]라는 값을 비교한다. 우리는.. 더보기
백준알고리즘python_연결요소의 개수_ 그래프 # https://www.acmicpc.net/problem/11724 # 1번째 풀이 : 그래프의 인접기반 리스트 구현 --------------------------------------------------------------- import sys sys.stdin = open("input.txt", "rt") from collections import deque sys.setrecursionlimit(10000) def dfs(node) : visited[node] = True # 해당 요소의 인접기반 연결리스트 순회, 방문 안된 노드 방문 . 즉, 방문하게 되면, 현재 node랑 같은 연결요소에 속하게 된다. for x in adj[node] : if not visited[x] : dfs( x.. 더보기
백준알고리즘JS_피자배달거리DFS function solve(){ var fs = require('fs'); // var input = fs.readFileSync('/dev/stdin').toString().trim().split('\n'); var input = fs.readFileSync('js/test.txt').toString().trim().split('\r\n'); var board = [] var minPzLenTotal = 1219999 let hs = [] let pz = [] let pzNum = 0 // 테스트 케이스 갯수 정보 받아들이기 var n = parseInt(input[0].split(' ').shift()) var m = parseInt(input[0].split(' ').shift()) console... 더보기
백준알고리즘JS_유기농배추(DFS) // https://bitwise.tistory.com/70 dx = [-1,0,1,0] dy = [0,1,0,-1] function solve(){ var fs = require('fs'); // var input = fs.readFileSync('/dev/stdin').toString().trim().split('\n'); var input = fs.readFileSync('js/test.txt').toString().trim().split('\n'); // 테스트 케이스 갯수 정보 받아들이기 var t = parseInt(input[0]) input.shift() // 테스트케이스 갯수 정보 삭제 var count = 0 var i = 1 var answer = [] let cabbageLocati.. 더보기
백준알고리즘python_N과M(12) import sys from collections import deque sys.stdin = open("input.txt", "rt") # input 내용을 파일에서 가져온다 # 중복 조합 def DFS(L, val): if L == m : for x in res : print( x , end = ' ' ) print() else: # n 이 아니라 len(arr) 이라는 것이 중요. 우리는 중복을 제거한 배열에 대해 적용하는 것이므로 # 또한 중복 조합이므로, 별도의 check list 배열이 필요 없 for i in range(val,len(arr)): # 값 넣기 res[L] = arr[i] # DFS DFS( L + 1, i) if __name__ == "__main__" : n , m = ma.. 더보기
백준알고리즘python_N과M(9) def DFS(L, val): if L == m : print(' '.join(map(str,res))) return else: # 같은 DFS 레벨 상에서, 같은 값이 들어가는 것을 방지 ex. 1, 9 이후, 또 1,9 가 들어가는 것 방지 # arr은 sort되어 있다. 즉, 앞에서부터 1, 7, 9, 9 이런식으로 arr이 들어온다 # 만약 앞의 9가 한번 쓰였고, 그 다음 9에 접근할 때, overlap != arr[i] 에 걸려서 넘어가게 된다 # ( 질문 : 1 9 7 9 > 이런식이면 overlap은 의미없는 거잖아 ??? > 그래서 아래서 arr.sort() 해준 거라고 ;;) overlap = 0 for i in range( n ): # 체크 안된애만 들어간다 if ch[i] == 0 .. 더보기
백준알고리즘python_피보나치01횟수 # https://www.acmicpc.net/problem/1003 # 기본 원리 : 각 숫자에 대한 0,1 출력 횟수도 피보나치 수열을 따른다 import sys from collections import deque sys.stdin = open("input.txt", "rt") num = int(input()) zero = [1,0,1] one = [0,1,1] def cal(k): length = len(zero) if k >= length: for i in range(length, k + 1): zero.append( zero[i-1] + zero[i-2] ) one.append( one[i-1] + one[i-2] ) print(zero[k], one[k]) for i in range(num).. 더보기
백준알고리즘python_정수삼각형 # https://www.acmicpc.net/problem/1932 # Bottom_Up import sys from collections import deque if __name__ == "__main__" : n = int(input()) board = [ ] for i in range(n): board.append(list(map(int,input().split()))) dy = [ [0] * n for _ in range(n) ] maxL = 0 dy[0][0] = board[0][0] # 왼쪽 아래, 오른쪽 아래 for i in range(1, n): dy[i][0] = dy[i-1][0] + board[i][0] dy[i][i] = dy[i-1][i-1] + board[i][i] # 그외 f.. 더보기