tempcru 삽질기록

외판원 순회 풀이 - JAVA https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 설명 TSP 라고 외판원 순회라는 유명한 문제이다 N 개의 도시가 있고, 외판원은 도시를 순회한다 방문한 마을을 다시 방문할 수 없고 모든 도시를 방문하고 시작도시로 돌아와야한다 순회시 최단 코스트를 구하라 문제풀이 시작지점을 고정한다 시작마을은 고정해도 된다 어짜피 순회 할 것이기 때문이다 A -> B -> C -> A 순..

[백준1802] 종이접기 - JAVA 풀이 https://www.acmicpc.net/problem/1802 1802번: 종이 접기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 1000보다 작거나 같은 자연수이다. 둘째 줄부터 T개의 줄에 각각의 종이가 어떻게 접혀있는지가 주어진다. 종이의 정보는 문자열로 주어지며, 1 www.acmicpc.net 문제요약 비트문자열이 T개 주어진다 비트문자열은 0, 1로 이루어져있고 길이는 홀수이다 0, 1이 의미하는 것은 종이를 접은 흔적이다 비트문자열은 길이가 1이 될때까지 N/2 -1 이 되도록 절반씩 접었다가 편자국이다. 종이를 절반씩 접었다가 폈으므로 두번 접었다면 001, 011, 100, 110 등 중앙 bit를 제외하고 좌우는 bit가 서로 다르..

[백준16937] 두 스티커 문제풀이 - JAVA https://www.acmicpc.net/problem/16937 16937번: 두 스티커 첫째 줄에 모눈종이의 크기 H, W, 둘째 줄에 스티커의 수 N이 주어진다. 다음 N개의 줄에는 스티커의 크기 Ri, Ci가 주어진다. www.acmicpc.net 1. 문제 요약 H * W 공간에 N개의 사각스티커중 2개를 골라서 붙인다 스티커는 겹칠 수 없고 H * W 공간을 넘어가서는 안된다 스티커를 회전하는 것은 가능하다. 스티커 2개를 붙일 수 없으면 0, 있다면 최대 스티커 넓이를 출력 2. 문제 풀이 최대 H * W는 100 * 100 이다 스티커를 어떻게 붙이던 중요하진않고 붙일 수 있냐 없냐만 중요하다 스티커는 겹칠 수 없으므로 스티커 넓이 연산은..

[백준11332] 시간초과 문제 풀이 - JAVA https://www.acmicpc.net/problem/11332 11332번: 시간초과 각 테스트 케이스들에 대하여 시간 초과가 나면 "TLE!", 시간 초과가 나지 않으면 "May Pass." 를 출력한다. www.acmicpc.net 문제 유빈이는 코딩을 하다가 시간 초과가 났다. 그래서 시간 복잡도를 계산하기로 했다. 채점 시스템은 1초에 100000000(10^8)가지 동작을 할 수 있다. 여러분들은 유빈이를 도와 시간초과가 나는지 확인하는 프로그램을 작성하라. 입력 입력의 첫 번째 줄에는 테스트 케이스들의 수 C가 주어진다. 그 다음 C개의 줄에는 시간 복잡도를 나타내는 문자열 S, 각 테스트 케이스마다 입력의 최대 범위 N, 테스트 케이스의..

[백준1720] 타일코드 문제 풀이 - JAVA https://www.acmicpc.net/problem/1720 1720번: 타일 코드 2×N 크기의 넓은 판을 1×2 (또는 2×1) 크기와 2×2 크기의 타일로 채우려고 한다. 여러 가지 경우가 있을 수 있으므로, 각각을 하나의 코드로 대응시켜서 암호화에 이용하려고 한다. 그런데 문제가 www.acmicpc.net 타일 코드 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 128 MB 3367 1401 1118 42.574% 문제 2×N 크기의 넓은 판을 1×2 (또는 2×1) 크기와 2×2 크기의 타일로 채우려고 한다. 여러 가지 경우가 있을 수 있으므로, 각각을 하나의 코드로 대응시켜서 암호화에 이용하려고 한다. 그런데 문제가 생겼다. 넓은 ..

백준3078 좋은 친구 문제 풀이 - JAVA https://www.acmicpc.net/problem/3078 3078번: 좋은 친구 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다. www.acmicpc.net 좋은 친구 문제 상근이는 환갑을 바라보던 나이에 수능 시험을 다시보고 교대에 입학했고, 초등학교 선생님으로 취직했다. 상근: 요즘 애들은 친구를 사귀지 않나봐. 내가 앞에서 보고 있으면, 친구가 있는 학생이 별로 없는 것 같아. ??: 오빠! 오빠는 말콤의 친구와 성적이라는 책 안 읽어 봤어? 이 책에는 성적과 친구가 무슨 관계가 ..

백준13417 카드문자열 풀이 https://www.acmicpc.net/problem/13417 13417번: 카드 문자열 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 처 www.acmicpc.net 카드 문자열 성공 문제 N장의 카드가 일렬로 놓여있다. 각 카드에는 알파벳이 하나씩 적혀있다. 태욱이는 가장 왼쪽에 있는 카드부터 차례대로 한 장씩 가져올 수 있다. 가장 처음에 가져온 카드는 자신의 앞에 놓는다. 그다음부터는 가져온 카드를 자신의 앞에 놓인 카드들의 가장 왼쪽, 또는 가장 오른쪽에 놓는다. 태욱이는 모든 카드를 다 가져온 후에 자신의 앞에 놓인 카드..

백준1461 도서관 문제 풀이 - java https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 도서관 성공 문제 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 계산하는 프로그램을 작성하시오. 세준이는 한 걸음에 좌표 1칸씩 가며, ..

[백준17124] 두개의 배열 문제 풀이, java https://www.acmicpc.net/problem/17124 17124번: 두 개의 배열 정수 배열 A 와 B가 있다. A는 총 n개의 서로 다른 양의 정수를 포함하고 B는 총 m개의 서로 다른 양의 정수를 포함한다. A, B를 이용해서 길이가 n인 새로운 배열 C를 만들어보자. C[i] 는 배열 B에 있 www.acmicpc.net 문제 정수 배열 A 와 B가 있다. A는 총 n개의 서로 다른 양의 정수를 포함하고 B는 총 m개의 서로 다른 양의 정수를 포함한다. A, B를 이용해서 길이가 n인 새로운 배열 C를 만들어보자. C[i] 는 배열 B에 있는 값 중 A[i] 에 가장 가까운 값 (절대값 차이가 가장 작은 값)으로 정의 된다. 만약 이..

유클리드 호제법이란? - 유클리드가 집필한 '유클리드 원론'에 나오는 최대공약수를 찾는 기법이다. - 호제법 의미, 互(서로호), 除 (덜 제)를 사용한 단어로 두 숫자를 상호 나누거나 빼서 "최대공약수"를 찾는다. 1. 호제법의 이해 (1) 호제법을 어떤 function 이나 Method 라고 생각해본다 input : 임의의 숫자 2개 (각 a, b 라고 가정) output : 두수의 최대공약수 숫자 1개 (x 라고 가정) // 코드로 표현하면 이런식 public int gcd(int a, int b) { return 최대공약수; } (2) input, output을 어떻게 정의해야할지 고민해본다 (3) input a, b는 자연수가 입력되어야한다. input a, b는 int로 정의했다. (숫자기만 ..