개발바닥 꼬순내

🥈백준 1966 프린터 큐 python 풀이 / 딕셔너리 큐를 사용한 풀이

🥈백준 1966 프린터 큐 python 풀이 / 딕셔너리 큐를 사용한 풀이

🥈백준 1966 프린터 큐 python 풀이 / 딕셔너리 큐를 사용한 풀이

문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다. 예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 ..

[Python] 🥈백준 트리의 부모 찾기 - 11725 /DFS 알고리즘

[Python] 🥈백준 트리의 부모 찾기 - 11725 /DFS 알고리즘

[Python] 🥈백준 트리의 부모 찾기 - 11725 /DFS 알고리즘

예제 입력 1 7 1 6 6 3 3 5 4 1 2 4 4 7 예제 출력 1 4 6 1 3 1 4 아이디어 생각하기 그래프를 만들고, 방문여부를 체크하는 배열 visited를 선언한다. 루트 v를 dfs() 인수로 넘겨 V와 연결된 다른 노드를 재귀적으로 방문한다. for문으로 그래프를 도는데, 만약 visited[v]가 비어있다면, visited했다는 의미의 True가 아닌, 탐색을 시작한 값 즉, 부모를 넣어준다. 그리고 다시 재귀한다. 결국, dfs를 기존 그대로구현하고, visited에는 방문여부대신, v를 넣어주면 된다! 기존의 로직을 헷갈릴 것 같아서 변수명은 그대로 visited로 냅두고 진행하겠다 원한다면 father, parents 등으로 바꿔보자.... 주의사항 graph = [[0] *..

[Python] 🥈백준 2667 단지 번호붙이기 /DFS를 활용하여 연결요소 구하기

[Python] 🥈백준 2667 단지 번호붙이기 /DFS를 활용하여 연결요소 구하기

[Python] 🥈백준 2667 단지 번호붙이기 /DFS를 활용하여 연결요소 구하기

예제 입력 1 7 0110100 0110101 1110101 0000111 0100000 0111110 0111000 예제 출력 1 3 7 8 9 아이디어 생각하기 연결요소 문제는 풀어도 풀어도 뇌리에 안 박혀서 이렇게 블로그를 쓰고자 한다.... 로직순서 변수설명 map: 지도, home: 각각 단지내 집의 수, nums: 각각 단지내 집의 수를 담는 리스트 (1) 단지 지도 생성 (2) dfs 알고리즘을 돌며, ⓐ 범위를 벗어날 때 ⓑ집이 있을 때 ⓒ집이 없을 때 경우를 나눈다. ⓐ ⓒ는 return False (3) ⓑ 집이 있을 때의 경우, home +=1 집을 1개 추가하고 maps[x][y] = 0 #숫자를 세고 0으로 집을 없앰 다시 못 돌게 집을 없애버린다 dfs(x-1,y) #상하좌우 재..

[Python] 백준 1991번 트리 순회 / 재귀함수와 딕셔너리 이용하기

[Python] 백준 1991번 트리 순회 / 재귀함수와 딕셔너리 이용하기

[Python] 백준 1991번 트리 순회 / 재귀함수와 딕셔너리 이용하기

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오. 예를 들어 위와 같은 이진 트리가 입력되면, 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식) 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식) 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트) 가 된다. 입력 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파..

[ Python] 백준 10819번 차이를 최대로 / 브루트포스 그림 풀이

[ Python] 백준 10819번 차이를 최대로 / 브루트포스 그림 풀이

[ Python] 백준 10819번 차이를 최대로 / 브루트포스 그림 풀이

문제 N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오. |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| 입력 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. 출력 첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다. 예제 입력 1 6 20 1 15 8 4 10 예제 출력 1 62 아이디어 생각하기 대체 최대값이 왜 62나 나오지? 라고 생각했다... (최대값 - 최소값) + (2번째 최대값 + 2..

[Python] 이진 탐색 기초/ 백준 2110번 공유기 설치 파이썬 풀이

[Python] 이진 탐색 기초/ 백준 2110번 공유기 설치 파이썬 풀이

[Python] 이진 탐색 기초/ 백준 2110번 공유기 설치 파이썬 풀이

이진탐색: 배열 내부의 데이터가 정렬되어 있을 때 시작점, 끝점, 중간점을 이용하여 원하는 값을 찾는 탐색법 시작점을 start 중간점을 mid, 끝점을 end라고 부르겠다 이진탐색은 주어진 범위가 엄청 클 때 사용할 수 있고, 배열의 원소들은 오름차순으로 정리되어야 한다. 코드 작성 순서 (1) 이진탐색의 시작점과 끝점을 설정 start= 0 end = 배열에서 가장 큰 수, 혹은 주어진 최대값 (2) 이진탐색 수행 while(start

[Python] 백준 파이썬 풀이 11724/연결 요소의 개수

[Python] 백준 파이썬 풀이 11724/연결 요소의 개수

[Python] 백준 파이썬 풀이 11724/연결 요소의 개수

문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 출력 첫째 줄에 연결 요소의 개수를 출력한다. 예제 입력 1 6 5 1 2 2 5 5 1 3 4 4 6 예제 출력 1 2 import sys input = sys.stdin.readline sys.setrecursionlimit(1000000) #재귀 최대깊이, dfs 사용 시 오류 방지 n, m = map(int, inp..

[Python] 백준 11652번 풀이 / 카드 / sorted()에서의 key lambda 사용하기

[Python] 백준 11652번 풀이 / 카드 / sorted()에서의 key lambda 사용하기

[Python] 백준 11652번 풀이 / 카드 / sorted()에서의 key lambda 사용하기

문제 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지고 있는 정수를 구하는 프로그램을 작성하시오. 만약, 가장 많이 가지고 있는 정수가 여러 가지라면, 작은 것을 출력한다. 입력 첫째 줄에 준규가 가지고 있는 숫자 카드의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 출력 첫째 줄에 준규가 가장 많이 가지고 있는 정수를 출력한다. 예제 입력 1 5 1 2 1 2 1 예제 출력 1 1 틀렸던 코드 import sys input = sys.stdin.readline n = int(inp..

[Python] 퀵 정렬 알고리즘/ 이것이 코딩테스트다 정렬편

[Python] 퀵 정렬 알고리즘/ 이것이 코딩테스트다 정렬편

[Python] 퀵 정렬 알고리즘/ 이것이 코딩테스트다 정렬편

퀵 정렬 "기준을 정하고 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 정렬" 우리는 정렬할 배열의 0번째 인덱스를 기준으로 삼을 것이다. 이 기준을 피벗이라고 부른다. 퀵 정렬을 사용하여 리스트 [5,7,9,0,3,1,6,4,8]을 오름차순으로 정리해보도록 하자 (1) 리스트의 왼쪽부터 피벗보다 큰 값을 찾고, 오른쪽부터는 피벗보다 큰 값을 찾은 후, 둘의 위치를 바꿔준다 (2) 다시 왼쪽부터 탐색하여 피벗(5)보다 큰 수(9), 작은 수(3)의 위치를 바꿔주자 (3) 위 과정을 반복하게 되면 작은 수와 큰 수가 엇갈리게 되어 바꿀 수 없는 상황이 온다 !! (4) 이럴 땐 작은 수와 피벗의 위치를 바꾼다 (5) 이렇게 되면 피벗의 왼쪽은 피벗보다 작은 수 오른쪽은 큰 수가 정렬된다. (6) 각각 ..

[Python] 백준 10989번 수 정렬하기 3 /메모리 초과 오류 해결

[Python] 백준 10989번 수 정렬하기 3 /메모리 초과 오류 해결

[Python] 백준 10989번 수 정렬하기 3 /메모리 초과 오류 해결

import sys input = sys.stdin.readline n = int(input()) arr = [] for i in range(n): arr.append(int(input())) arr.sort() for i in arr: print(i) 입력받은 값을 빈 배열 arr에 append 후, sort()함수로 오름차순하여 출력하는 형식을 생각했다 하지만 메모리 초과 발생...! 메모리 제한이 8MB로 굉장히 작은데, 많은 메모리를 소요하는 파이썬으로 실행하니 쉬운 문제임에도 불구하고 오래 걸렸다.... 메모리 초과 발생 이유 (1) sort,sorted를 사용 (2) sys.stdin.readline이 아닌 그냥 input()를 사용 (3) for 문 안에 append를 작성 따라서 이 문제는..

[Python] DFS/BFS 알고리즘 / 백준 1260 그림 풀이 /

[Python] DFS/BFS 알고리즘 / 백준 1260 그림 풀이 /

[Python] DFS/BFS 알고리즘 / 백준 1260 그림 풀이 /

개요 그래프에서 노드(정점)와 간선으로 표현된다. 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 두 노드가 간선으로 연결되어 있다면 인접하다. 라고 표현한다. DFS (깊이 우선 탐색) 그래프에서 깊은 부분을 우선적으로 탐색한다. BFS 알고리즘 (너비우선탐색) 노드에서 갈 수 있는 모든 노드를 다 방문한다. 말 그대로 너비에서 연결된 모든 곳을 일단 큐에 담는다 (1) 시작 노드를 큐에 append한 후 방문처리 (2) 큐에서 노드를 POP, 인접 노드 중 방문하지 않은 노드를 모두 큐에 append (3) 2번 과정을 q가 빌 때까지 반복한다. 주의사항 from collections import deque q= deque([v]) q.popleft() q.pop대신 im..

[Python] DP(Dynamic Programming) 알고리즘이 뭘까?/ 개미전사 풀이 / 백준 1463번 1로 만들기 풀이

[Python] DP(Dynamic Programming) 알고리즘이 뭘까?/ 개미전사 풀이 / 백준 1463번 1로 만들기 풀이

[Python] DP(Dynamic Programming) 알고리즘이 뭘까?/ 개미전사 풀이 / 백준 1463번 1로 만들기 풀이

다이나믹 프로그래밍이란? 앞에서 계산한 식을 배열에 미리 저장하여 연산속도를 증가시키는 프로그래밍 계산한 건 다시 계산하지 않는 게 중요하다 DP의 예: 피보나치 수열 DP = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ] DP[2] == DP[0] + DP[1] 2 DP[3]== DP[1] + DP[2] 3 즉, 앞에서 이미 계산된 값을 더해서 수열의 값을 알 수 있다. 피보나치 수열의 특징 1번째 인덱스와 2번째 인덱스의 값을 알 때, 3번째 값은 앞에 두 값을 더하면 된다 a[i] = a[i-1] + a[i-2] def fibo(x) : if x == 1 or x==2: return 1 #첫번째와 두번째 수열은 1이므로 1을 return return fibo(x -1) + ..

티스토리툴바