본문 바로가기

CS46

[백준] 11725: 트리의 부모 찾기 python 구현 / DFS 문제 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오 사실 처음에는 문제가 잘 이해가 가지 않아 tree 구조를 손으로 그려보니 이해가 편했다. 2번 노드부터 순서대로 부모노드를 출력하는 것 풀이 DFS로 구현하였다. vst에 1로 방문처리를 하는게 아니라 부모노드(current node)를 표시하며 방문 처리를 진행했다. 이번 문제에서도 재귀의 깊이를 확장해주었어야 했다. 또한 같은 코드로 pypy3으로 제출하였을 때 메모리 에러가 나는 것을 보면,, pyhon3보다 메모리 관리는 부족한가보다 CODE import sys sys.setrecursionlimit(10**7) n = int(input()) adj_list = [[] fo.. 2023. 3. 13.
[백준] 1987: 알파벳 python 구현 / DFS, 시간초과(pypy3, python3) 글을 쓰기에 앞서,, pypy3으로 돌리면 해결될 문제를 1시간 동안 붙잡았던 건에 대하여,,, Python3 vs PyPy3 python3 : 메모리 및 속도 측에서 우세 pypy3: 복잡한 코드(반복)을 사용하는 경우 우세 PyPy3에서 사용하는 JIT(just in time) 컴파일이란 프로그램을 실행하기 전에 컴파일 하는 대신, 프로그램을 실행하는 시점에서 필요한 부분들을 즉석으로 컴파일 하는 방식이고 보통 인터프리터 언어의 성능 향상을 목적으로 도입하는 경우가 많다. 인터프리트 하면서 자주 쓰이는 코드를 캐싱하기 때문에 인터 프리터의 느린 실행속도를 개선할 수 있다. JVM에서도 바이트 코드를 기계어로 번역할 때 JIT 컴파일러를 사용한다고... Link에서 이해할 수 있었습니다,, 더 자세한 .. 2023. 3. 3.
[백준] 10026: 적록색약 python 구현 / BFS 첫 골드로 진입 ! 문제 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다) 적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1) 그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오. 풀이 나는 그냥 color map을 만들어 사용하였다. 해당 색.. 2023. 3. 2.
[백준] 2468: 안전 영역 python 구현 / BFS 한 번에 맞췄다 !!! 나름 기념적이라 기록 문제 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다. 이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을 회색으로 표시하면 다음과 같다. 물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다). 풀이 BFS로 풀었다 ! 해당 문제에 노트.. 2023. 3. 2.

티스토리툴바