2JINISHAPPY 2JINISHAPPY

www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 삼성 A형 기출인 사다리 조작 문제 시간을 줄일 수 있는 분기가 많기에 백트래킹 연습에 좋은 문제라고 생각한다. 사다리는 0개~3개를 설치할 수 있다. 따라서 4번의 반복문을 통해 해당 탐색에서 놓을 총 사다리 수를 정하고 백트래킹 루틴을 돌려 주었다. 까다로웠던 점은 해당 stage에 사다리 설치를 완료한 뒤 중복 체크를 막기 위한 다음 stage 선정이 조금 어려웠다. 그래서 처음엔 행 - 열 순서로 검사..

programmers.co.kr/learn/courses/30/lessons/17683 코딩테스트 연습 - [3차] 방금그곡 방금그곡 라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다. 그럴 때 네오는 다음 포털의 '방금그곡' 서비스를 이용하곤 한다. 방금그곡에서는 TV, programmers.co.kr 이것도 시간을 활용한 문제 아직 코테를 그렇게 많이 보진 않았지만 대기업 코테에서는 시간을 문자열 처리할 수 있는지를 많이 보는 것 같다 그래서 C++이 그런 코테 스타일에는 적합하지 않다고 느꼈고, 파이썬의 datetime 모듈에 대한 연습을 하고 있다. datetime 모듈을 이용하면 문자열을 datetime 객체로 변환시킬 수 있고(strptime메소드), ..

1. Bubble Sort : 인접한 원소끼리 대소를 비교하고 swap시켜 unsorted part중 가장 작은(sort priority가) element를 sorted part의 직전에 위치시키는 정렬 bubbleSort(A[1 ... N], N): for i in [1 ... N]: for j in [1 ... N-i]: if A[j] > A[j+1]: swap A[j] and A[j+1] bubble sort의 validaity: i번째 stage 후에 Array에서 i번째로 큰 값은 항상 A[n-1-i]번째에 위치하게 된다(loof invariant). 즉, 정렬되어 위치해야 할 올바른 위치에 자리잡게 된다. time complexity: O(N²) i번째 stage에서 가장 큰 element를 ..

programmers.co.kr/learn/courses/30/lessons/17678 코딩테스트 연습 - [1차] 셔틀버스 10 60 45 [23:59,23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59] 18:00 programmers.co.kr 카카오의 문자열 문제 쿠팡의 코딩테스트에서도, 이 문제에서도 시간을 문자열로 받아서 스케줄링하는 문제가 자주 나오던 것 같다 그래서 꼭 정복해야 할 것 같은.... 문제............... 시간 문자열 너무너무 싫지만 ㅠㅠ 시간에 대한 모든 부분을 클래스로 구현해서 관리해줬다. 파이썬에는 datetime이라는 modul..

트리란 그래프 이론 상 Connected+Acyclic의 성질을 가지고 있는 그래프의 한 형태이다. 위와 같은 트리에서 edge(5,6)이 제거되면 모든 Vertex가 연결되어 있어야 한다는 Connected 성질을 만족하지 못한다. 또한 edge(4,6)이 추가된다면, 4-5-6 사이에 Cycle이 생겨 Acyclic 성질을 만족하지 못한다. 자료구조에서 구현하는 트리는 보통 Rooted Tree를 의미한다. Rooted Tree의 Non-Recursive한 정의 데이터를 지닌 노드와, 노드들을 연결해주는 Directed Edge의 집합으로 이루어진다. Edge의 방향은 Parent Node에서 Child Node로 향한다. Tree 상의 노드 중 In-degree가 0인 Node를 Root Node라..

처음에 풀었던 코드 #include #define INF 987654321 char map[10005][10005]; bool visit[10005][10005]; int n, m, ans,dx[] = { 1,1,1 }, dy[] = { -1,0,1 },k=INF,col[10005]; bool safe(int r, int c) { return r >= 0 && r = 0 && c < m; } bool pipe(int r,int c) { if (c == m-1) { visit[r][c] = true; return true; } for (int i = 0; i < 3; i++) { int nr = r + dy[i], nc = c + dx[i]; if (!safe(nr,nc)||map[nr]..

www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 이전의 풀이와는 조금 달라진 점이 있어서 다시 포스팅한다. 2년전에도 조합 구할 때 bound를 M인데 N으로 써놓고 삽질했는데.............. 2년이 지나도 똑같다 ㅎㅎ import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.FileInputStream; import java.io.IOException; import java.io..

그래프의 Vertex에는 순서가 있을까? 대학교의 전공 과목에는 선수 과목이라는 것이 존재한다. 특정 과목을 수강하기 위해서는 해당 과목의 선수 과목을 먼저 수강해야 하는 것이다. 이러한 관계를 이용해서, Topological Sort를 이용하면 올바른 수강 순서를 얻어낼 수 있다. 우리는 Vertex의 정렬 기준을 In-degree, Out-degree의 차수로 나타내어 Sorting Algorithm을 정의해볼 수 있다. Topological Sort: Directed(방향이 있는) Graph G에서 모든 Vertex를 정렬한 것. Vertex 정렬 기준: 임의의 vertex u, v가 있을 때 edge(u,v)가 존재할 경우 vertex u는 vertex v보다 순서가 앞이다. 오직 Cycle이 없..