https://www.acmicpc.net/problem/14675 14675번: 단절점과 단절선 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 트리의 정점 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 트리의 정점은 1번부터 n번까지 존재한다. 다음 줄부터 N-1개의 줄에 걸쳐 간선의 정 www.acmicpc.net # 트리문제이다. # 우선 입력으로 주어지는 정보는 트리임이 보장된다고 했으므로 모든 간선은 단절선이 된다! # 또한, 정점중에서 리프노드가 아닌 정점들은 모두 단절점이 된다. 따라서 입력받을때 정점들을 graph배열에 넣고 확인하려는 정점 k의 graph[k]의 길이가 1이하라면 리프노드이므로 no를 출력해주고 아니면 yes를 출력해준다. import sys input..
https://www.acmicpc.net/problem/1913 1913번: 달팽이 N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 www.acmicpc.net # 단순 구현 문제이다. # 가끔 구현문제중에 이러한 형태의 배열을 사용하는 문제들이 나와 포스팅해본다. N = int(input()) target = int(input()) # 상, 우, 하, 좌 dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1] # 처음 1의 위치 x, y에 넣어줌 if N % 2 == 1: x, y = N//2, N//2 else: x, y = N//2, N/..
https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net # 기본적인 트리문제이다. # 일반적인 대학생들이라면, 자료구조 시간에 트리에 대해서 배웠을 텐데, 나는 자료구조수업을 듣지 않은 채로 독학해서 알고리즘을 공부했고 트리를 대충 보고 넘어가서 아직은 낯선 주제이다. # 그래도 그림그려가며 dfs, 재귀로 풀어보니 그렇게 어렵지는 않았다. 1. delete노드를 지웠을때 남는 Leaf 노드의 개수를 출력하는 문제이다. 2. tree에 각 노드의..
https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net # 백트래킹 문제중에 가장 대표적인 문제이다. (well-known) 1. 우선 한 행마다 하나씩 Queen을 놓음으로써 같은 행을 확인하는 작업은 하지 않아도 된다. N을 입력받고 col_set, diag_set1, diag_set2을 set으로 선언해준다. col_set은 Queen이 놓여져있는 열을 나타내고 diag_set1은 Queen이 놓여져있는 왼쪽대각선을 나타내고 diag_set2는 Queen이 놓여..
https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net # 스터디에서 구현문제 위주로 매일 문제를 올려주신다길래 풀어보고 있다! # 구현,시뮬레이션 문제는 아이디어가 어렵고 복잡하지 않지만, 말그대로 구현이 복잡하고 어렵다 (약간 무지성으로 풀기 딱 좋은?? 문제들인듯) (물론 어렵게 bfs랑 같이 섞어 나온다면 아이디어 떠올리는 것도 힘들다 ex: 삼성기출문제) # 이 문제는 문제에서 요구하는대로 그냥 그대로 구현해주면 풀린다. 1. 우..
https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net # 2016년 하반기 삼성 SW역량테스트문제이다. # 제목은 Easy인데, 전혀 Easy하지 않다.. # 보드의 크기가 최대 20이고 최대 5번이동할 수 있으므로 각각 상하좌우로 5번 시뮬레이션 돌려도 20 * 20 * 4^5 = 40만번이므로 시간초과가 나지 않을 것이라 생각했다. # 우선 구현하는 데 있어서 중요한 과정 몇가지가 있다. * 한 번 이동할때 모든 블록..
https://www.acmicpc.net/problem/3649 3649번: 로봇 프로젝트 각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2) 정답이 여러 개인 경우에 www.acmicpc.net # 문제푸는 것보다 입출력받는게 더 까다로웠다.. 입력이 여러 테스트 케이스로 이루어져 있는데, 테스트케이스가 몇개인지 알려주지 않는다. 따라서 '그대로 출력하기'문제처럼 try, except구문을 통해 EOF가 나올때까지 입력을 계속 받아야한다. 1. while True를 통해 EOF가 입력될때까지 계속 try문을 실행해준다. x를 입력받아서 1000만을 곱해준다. (1..
https://www.acmicpc.net/problem/1561 1561번: 놀이 공원 첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 www.acmicpc.net # N이 20억이고 M이 1000이므로 이분탐색을 사용해야 한다는 것을 알 수 있다. 이분탐색을 사용하는 문제는 '이분탐색' 자체로 후보수를 매우 극단적으로 줄일 수 있기 때문에 풀이 자체는 naive한 경우가 많았다. 특히 매개변수 탐색 문제를 여러개 풀어보면서 느꼈다. 이 문제 역시 이분탐색이란 걸 생각한 뒤, naive한 방법을 생각했는데 그게 맞았다. ..
모르는 사이에 조금씩 조금씩..
