어읽로꾸거

백준 1854 링크 https://www.acmicpc.net/problem/1854 문제 풀이 dp[현재위치][k번째로 빨리 도착함]배열을 이용해 풀었습니다. 어제 푼 문제인 도로포장 과 상당히 비슷한 문제라는 생각이 드네요 BOJ 1162 도로포장 백준 1162 도로포장 링크 https://www.acmicpc.net/problem/1162 1162번: 도로포장 문제 준영이는 매일 서울에서 포천까지 출퇴근을 한다. 하지만 잠이 많은 준영이는 늦잠을 자 포천에 늦게 도착하기 일쑤다. 돈.. postbarca.tistory.com 파이썬으로 문제를 풀다보니까 Cpp랑 다른점이 많이 있네요 input=__import__('sys').stdin.readline 이 한줄이 없으면 시간초과 때문에 Python3..

백준 1743 링크 https://www.acmicpc.net/problem/1743 문제풀이 파이썬으로 dfs등의 재귀함수를 이용할때 주의해야 할 점은 파이썬은 재귀를 1000번 까지만 허용합니다. 그래서 이 문제같이 최대 100*100 = 10000번을 재귀로 돌아서 1000번 이상 재귀를 돌 경우에선 import sys sys.setrecursionlimit(100000) 를 입력해주어 재귀의 제한을 풀어줘야 합니다. 코드에선 10만번정도로 제한을 늘려놓았습니다. 이걸 몰라서 런타임에러를 계속 두드려맞았네요. 코드 import sys sys.setrecursionlimit(100000) def dfs(y,x,result): result=result+1 M[y][x]=0 for _ in range(0..

백준 1162 도로포장 링크 https://www.acmicpc.net/problem/1162 1162번: 도로포장 문제 준영이는 매일 서울에서 포천까지 출퇴근을 한다. 하지만 잠이 많은 준영이는 늦잠을 자 포천에 늦게 도착하기 일쑤다. 돈이 많은 준영이는 고민 끝에 K개의 도로를 포장하여 서울에서 포천까지 가는 시간을 단축하려 한다. 문제는 N개의 도시가 주어지고 그 사이 도로들과 이 도로를 통과할 때 걸리는 시간이 주어졌을 때 최소 시간이 걸리도록 하는 K개의 이하의 도로를 포장하는 것이다. 여기서 도로를 포장하게 되면 도로를 지나는데 걸리는 시간이 0이라 하자. www.acmicpc.net 문제풀이 dp[지금도시위치][도로 포장한 회수] 배열을 만들어 비교하였습니다. 큐에서 꺼낼때 지금 갈 도로가 ..

백준 1068 링크 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다. www.acmicpc.net 문제 풀이 python 으로 풀었습니다. 끔찍한 실력 map[시작노드] 에 (도착노드)를 append 시켜주고 삭제될 노드를 입력 받은 후에 다시 삭제될 노드인 도착노드들을 다 없애줍니다. dfs로 탐색을 할 수 있도록 find() 함수로 탐색을 시작합니다. 만약 루트 노드가 삭제됬다면 탐색을 하지 않고 끝냅니다. 코드 def ..

백준 링크 https://www.acmicpc.net/problem/16785 16785번: ソーシャルゲーム JOI 君が少なくとも C 枚のコインを得るためにログインしなければならない回数の最小値を出力せよ． www.acmicpc.net 문제 해석(?) JOI는 내일부터 새롭게 소셜 게임을 시작하기로 했다. 이 소셜 게임에는 하루에 한번만 로그인을 할 수가 있다. 로그인을 할때마다 A개의 코인을 얻을 수 있다. 그리고 월요일부터 일요일까지 7일 연속으로 로그인을 하면, 그때마다, 추가로 B개의 코인을 얻을 수 있다. 이거 이외의 수단으로 코인을 얻는 수단은 없다. 내일은 월요일이다. JOI가 최소 C개의 코인을 얻기 위해 해야하는 로그인 회수의 최소치를 구하시오. 입력은 이하의 형태로 표준입력에게서 주어진다. J..

트리란? 트리는 데이터 사이의 계층 관계를 나타내는 자료구조입니다. 루트는 트리의 가장 위쪽에 있는 노드입니다. 하나의 트리에는 하나의 루트가 있습니다. 그림을 거꾸로 보면 나무처럼 생겼죠? 리프는 트리의 가장 아랫부분에 있는 노드를 리프라고 합니다. 엄밀히 말하면 해당 노드가 더 이상 아래로 뻗어 나갈 수 없으면 리프노드입니다. external node 라고도 합니다. 레벨은 루트로 부터 얼마나 떨어져 있는가를 나타냅니다. 루트의 레벨은 0이고 루트부터 가지가 하나씩 뻗어 나갈때 마다 레벨이 1씩 늡니다. 차수는 노드가 갖는 자식의 수를 차수라고 합니다. 예를 들어 위 루트의 차수는 2입니다. 모든 노드의 자식 수가 2개 이하인 경우는 특별히 이진트리 라고 합니다. 트리의 특징중 하나는 임의의 두 노드..

선형 리스트란? 그냥 리스트 즉 배열과 다른 점은 아마도 데이터를 다루는데 있어서 더 효율적이므로 선형 리스트를 사용하겠죠? 아마 그냥 배열(vector)에 비해서 자료를 중간에 끼워넣거나 할때 더 빠르기 때문입니다. 그냥 배열은 다음과 같은 문제를 갖게됩니다. 😥 쌓이는 데이터의 크기를 알아야 합니다. 데이터의 삽입, 삭제에 따라 데이터를 모두 옮겨야 하기 때문에 효율이 좋지 않습니다.(한칸씩 앞당겨지거나 뒤로 밀리는거는 시간이 O(n) 나옴) 리스트는 자료를 줄지어 나열한 자료구조를 의미합니다. 가장 단순한 구조인 선형 리스트(linear list) 또는 연결 리스트(linked list)는 다음과 같이 생겼습니다. 이때 각각의 데이터를 노드(node) 또는 요소(element)라고 합니다. 각각의 ..

백준 5397 링크 https://www.acmicpc.net/problem/5397 풀이 방법 스택 2개를 구성하여 왼쪽 스택, 오른쪽 스택을 구성합니다 한 글자씩 입력을 받아 왼쪽 스택에 넣어주고, 방향이나 백 스페이스 기호는 따로 처리하여 줍니다. 1. '' 의 경우엔 오른쪽의 스택에서 빼서 왼쪽의 스택에 넣어줍니다. 3. '-' 의 경우엔 왼쪽의 스택에서 하나 빼줍니다. 입력이 끝나면 왼쪽의 스택에서 모두 빼서 오른쪽에 넣어줍니다. 그리고 오른쪽에서 하나씩 빼면서 출력해주면 끝! 😎 Linked List를 이용한 풀이 : https://chika.tk/14 코드 #include #include using namespace std; int main() { //freopen("input.txt", "..