구빙그르르르

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 한줄 이해 -노드들의 부모트리 찾기 생각난 풀이 1번째 방법: 노드들의 연결 정보를 인접행렬로 나타내 bfs 탐색을 통해 확인 하려 했다. 이때 큐에 연결된노드와 현재 노드를 같이 넘겨주고 꺼낼때마다 visited에 방문을 표시할겸 부모노드의 번호로 바꿔줬다. import sys from collections import deque n = int(sys.stdin.readline()) visited = [0] * (n+1) graph = [[0 for i..

https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제 한줄 이해 -주어진 N개의 숫자 중에서 M개를 뽑을때 이미 선택된 숫자를 뽑아되는 경우에서 겹치지 않는 수열 구하기 생각난 풀이 1번째 방법: 이전 N과 M의 문제와 아이디어는 같지만 추가된 조건이 있다. 1부터 N까지 숫자가 아닌 주어진 N개의 숫자 중에서 M개를 뽑아야 하는점, 비내림차순으로 출력해야하는 점 백트래킹이 생각나 재귀를 통한 DFS를 사용했다. 일단 기본적인 아이디어..

https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 한줄 이해 -1부터 N까지의 숫자 중에서 M개를 뽑아 겹치지 않는 수열 출력 생각난 풀이 1번째 방법: 백트래킹이 생각나 재귀를 통한 DFS를 사용했다. 이때 재귀함수를 실행할때 인자를 현재 i값을 통해 넘어줬다. -> why? 문제에서 우선 같은 수를 여러번 골라도 된다고 한다. 그렇다는건 현재 선택된 수가 다시 담겨도 된다는 뜻이기 때문이다. 예를 들어 4 2 예제일때 함수실행 순서는 ..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제 한줄 이해 -5가지 테트리스에서 사용되는 모양들을 그래프에 위치 시켰을때 놓여진 부분들의 합이 제일 큰경우를 구하기 생각난 풀이 1번째 방법: 먼저 도형들의 규칙성을 찾으려고 노력했다. 각 점의 기준에서 상하좌우로 움직이면서 DFS로 탐색을 진행하면 원하는 모양을 만들 수 있는 것이다! 근데 ㅜ 이 모양은 DFS로 탐색을 진행한다고 해서 만들어 질 수 없는 모양이라 따로 처리를 해줘야한다고 ..

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 문제 한줄 이해 -D S L R의 각 명령어를 수행해 A 숫자가 B가 되기 위해 필요한 최소한의 명령어 구하기 생각난 풀이 1번째 방법: 각각의 명령어를 수행해 큐에 담아서 탐색하는 BFS가 떠올랐고 이미 방문한 숫자에 대해 다시 탐색하지 않게 visited처리를 해주었다. 이때 123에 R명령어를 수행하면 312가 되는것이 아니고 3012가 되는 점을 유의하기! import sys ..

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 한줄 이해 -R, G, B로 이루어진 그래프가 있을때 적록색약을 가지고 있는 사람은 R과 G를 차이를 거의 느끼지 못해 그래프를 볼때 같은 구역이라 생각한다. 이때 적록색약이 있는 사람과 없는 사람이 그래프를 볼때 나뉘어지는 구역 수 출력 생각난 풀이 1번째 방법: 그래프를 BFS를 통해 구역을 나누면서 탐색하는 방법이 떠올랐다. 적록색약이 없는 경우 단순히 탐색을 진행 적록색약이 있..

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 문제 한줄 이해 -상자에 익은 토마토와 익지 않은 토마토가 담겨있고 아무것도 담기지 않은 공간이 있을때 익은 토마트는 하루가 지나면 익지 않은 토마토를 익게 만들때 토마토를 모두 익은 상태로 만들기 위한 날짜 구하기 생각난 풀이 1번째 방법: 먼저 그래프에 익은 토마토를 먼저 큐에 담아주고 BFS를 통해 값 구하기 2차원 그래프로 선언, BFS탐색, 위층 아래층은 현재 위..

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 문제 한줄 이해 -리모콘의 숫자가 망가져 있을 수도 있고 아닐 수도 있는 상황에서 N채널로 가기위한 최소 버튼 입력 수 구하기 생각난 풀이 1번째 방법: 백트래킹을 통해 N채널 자릿수와 자릿수 +1, 자릿수 -1 의 경우의 수를 담아 값을 갱신했다. 자리수 -1 과 자릿수 +1 을 해주는 이유는 간단한 예를 들면 999 채널로 가려고 할때 망가진 숫자가 9가 망가졌다고 치자. 그..

https://www.acmicpc.net/problem/20529 20529번: 가장 가까운 세 사람의 심리적 거리 각 테스트 케이스에 대한 답을 정수 형태로 한 줄에 하나씩 출력한다. www.acmicpc.net 문제 한줄 이해 -요즘 유행하는 MBTI로 사람간의 심리적 거리를 계산한다. ENFJ와 ISFP가 있을때 심리적 거리는 3! 이때 주어진 사람들 중 3명의 값이 제일 작은 경우 구하기 생각난 풀이 1번째 방법: 리스트에 사람들을 담아 백트래킹을 통해 심리적 거리를 갱신 해주자! 이때 mbti의 갯수는 총 16개 그렇다면 사람이 33명이 들어오면 무조건 심리적 거리는 0임을 생각하자 why? 최악의 경우를 생각하면 32 명안에 2,2,2,2,2,2.... 이렇게 mbti가 같은 사람이 구성 될..

https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 문제 한줄 이해 -목표 지점에서 다른 지점까지의 거리 계산하기 생각난 풀이 1번째 방법: 먼저 그래프에서 목표 지점을 찾고 해당 지점에 대해서 BFS 탐색을 한 뒤 예외처리를 해주었다. import sys from collections import deque n, m = map(int,sys.stdin.readline().split()) graph = ..