HyunMaru Self_Study

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 본 문제는 자료구조 Tree의 3가지 순회를 구현하는 문제이다. C언어 라면 pointer를 활용해서 쉽게 풀 수 있을것이라 생각했지만, 주로 사용하는 Python으로 구현연습이 필요하다고 생각하여 python으로 문제를 풀게 되었다. Python은 주소를 다루는 것에 대한 방법이 없으므로, Dictionary와 Node Class를 활용하기로 하였다. 기본적으로 연결리스트로 만들어진 ..

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 본 문제는 0부터 9999까지의 숫자가 두개 들어오는데, 이 두 숫자를 A, B라고 하자. A에서 B로 바꾸는데 연산 4개를 이용하여 최소 연산 수를 구하는 것이다. 결국 D, S, L, R 이 4를 통한 최소 경로를 구하는 문제이므로, BFS를 통해 풀 수 있을 것이다. 다만 본 문제는 좀 애먹은 부분이 있다면, 시간초과 문제이다. L과 R 연산 같은 경우 예를 들어 1234를 L ..

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 문제는 다음과 같다. P(1)부터 P(10)까지의 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 로 정삼각형의 변의 길이를 나타낸다. 이는 수열 형태이므로, Dynamic Programming을 활용하여 문제를 풀고자하면 된다. DP이긴 하지만, 본래의 DP처럼 생각하고 점화식을 굳이 안세워도 이미 주어진 파도반 수열이 있기에 어렵지 않게 풀 수 있었다. Padovan sequence(파도..

https://www.acmicpc.net/problem/20529 20529번: 가장 가까운 세 사람의 심리적 거리 각 테스트 케이스에 대한 답을 정수 형태로 한 줄에 하나씩 출력한다. www.acmicpc.net 본 문제는 브루트포스 알고리즘과 비둘기집 원리를 이용해서 푸는 문제이다. 실버1인 이유는 비둘기집 원리에 대한 이해도가 있으면 바로 풀 수 있기 때문이다. 반대로 나는 비둘기집 원리를 까먹고있어서(2년전 이산구조때 배움) 왜 자꾸 틀리는지 모르고 있었다. 비둘기집 원리를 알고 있었으면 틀린 내 코드에 단 코드 두줄 추가로 문제를 맞출 수 있었다... 일단, 어떻게 풀었는지 설명해보겠다. 총 입력받은 개수들에 대해 조합을 이용하여 3개씩 묶어 가장 적은 심리적 거리를 위한 후보들을 만들었다. ..

https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 본 문제는 가중치 없는 방향 그래프 G가 주어졌을때, 모든 정점에 대해 경로가 있는지 없는지 구하는 프로그램을 만들어야한다. 모든 정점에 대한 경로 유무를 탐색해야하므로, 그래프 탐색 알고리즘 플로이드 와샬을 써야한다. 플로이드 와샬은 시간복잡도 O(n^3)의 비용이 들정도로 다익스트라에 비해 비효율적이지만, 모든 정점에 대한 최소 비용을 알 수 있기때문에 많이 채택되는 알고리즘이다. 비효율적이지만, 코드 짜기가 매우 쉽다. 단순히 for..

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 본 문제를 위한 알고리즘은 bfs인것은 확실하다. 문제 내용부터 모든 지점에 대해서 목표지점까지의 거리를 구하라고 하기 때문이다. 하지만, 목표지점이 모든 예제에 대해서 일정한게 아닌 다른 목표지점이 되기때문에 갑자기 생각이 복잡해졌다. 막상, 풀고보니 굳이 복잡하게 안해도 bfs가 강력해서 알아서 다 해줬다. 복잡한 이유는 원래대로의 bfs 풀때는 왼..

https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 말그대로 nCm 를 출력하는 문제이다. but, 정말 그 값들을 모두 출력하라는게 아니라 총 "개수" 를 구하라는 문제이다. 아무생각없이 파이썬의 from itertools import combinations를 했다가는 시간초과 뜰거같았다. 예제로 나오는 100 6을 입력했을때, 1192052400개의 조합 경우의 수를 모두 구하는건 매우 오래걸릴 수 있는 문제이기때문이다. 역시 파이썬이 세상 편안한 언어라고 새삼 느꼈던 게, 본 문제를 단 한줄로 풀 수 있게 라이브러리를 제공해준다. math 라이브러리에서 ma..

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 본 문제는 제목에서 말하듯이 구간합 이라는 알고리즘을 이용해야한다. 특정 숫자가 [5, 4, 3, 2, 1]이 들어왔을 때, 각 요소별로 구간합을 미리 구해놓는다. 즉, [5, 5 + 4, 5 + 4 + 3, 5 + 4 + 3 + 2, 5 + 4 + 3 + 2 + 1] => [5, 9, 12, 14, 15]가 나오게 된다. 이후, 특정 구간의 합을 구하라고 하면, 그 구간만..

ahttps://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 실버까지는 그래프 탐색 문제가 참 쉽다. 어째, Class 3에서 bfs, dfs 문제가 참 많이 나오는 것도 여기서 꿀빨라는것 같았다. 거두절미하고, 본 문제는 입력으로 받는 N을 통해 N*N 정사각형 내 0 또는 1의 값이 채워져있다. 여기서 1은 집이 있는 곳을 의미하며, 0은 집이 없는 곳을 의미한다. 이때, 연결된 집의 모임인 단지를 정의하면서 이 단지가 몇개가 있고, 각 단지별 집이 몇..

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리 라는 방법이 있다. 휜 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상에서 같은 숫자의 점들이 한 곳에 많이 몰려 있으면 쿼드 트리에서는 이를 압축하여 간단히 표현한다. 즉, 이 문제에서는 2의 n승 * 2의 n승의 정사각형들에 대해 분석하는 문제이다. 8 * 8 에서 0 또는 1로만 이루어졌는지 판단한 뒤, 왼쪽 위..