SoU 개발일지

문제외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한..

문제45656이란 수를 보자.이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.N이 주어질 때, 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. 0으로 시작하는 수는 계단수가 아니다.https://www.acmicpc.net/problem/1562       난이도골드 1      코드import sysn = int(sys.stdin.readline())dp = [[[0 for _ in range(2**10)] for _ in range(10)] for _ in range(n+1)]answer = 0mod = 1000000000for j in range(1,10) : dp[1][j][1 0 : ..

문제서양 장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. 과 같은 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 O로 표시된 칸에 있는 다른 말을 잡을 수 있다. 그런데 체스판 위에는 비숍이 놓일 수 없는 곳이 있다. 에서 체스판에 색칠된 부분은 비숍이 놓일 수 없다고 하자. 이와 같은 체스판에 서로가 서로를 잡을 수 없도록 하면서 비숍을 놓는다면 과 같이 최대 7개의 비숍을 놓을 수 있다. 색칠된 부분에는 비숍이 놓일 수 없지만 지나갈 수는 있다.  정사각형 체스판의 한 변에 놓인 칸의 개수를 체스판의 크기라고 한다. 체스판의 크기와 체스판 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 주어질 때, 서로가 서로를 잡을 수 없는..

문제세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다.분할의 개수의 최솟값을 출력하는 프로그램을 작성하시오.https://www.acmicpc.net/problem/1509      난이도골드 1        코드import sysdef palin() : for i in range(n) : isPal[i][i] = True for i in range(2,n) : ii = i for j in range(1,n+1-i) : if x[ii] == x[j] : ..

제너릭자바에서 클래스나 메서드가 사용할 데이터 타입을 미리 지정하지 않고, 나중에 사용할 때 타입을 지정할 수 있도록 하는 기능     제너릭을 사용하는 이유타입 안전성제너릭을 사용하면 컴파일 시점에 타입 체크가 이루어진다. 이를 통해 잘못된 타입의 데이터를 사용하는 것을 방지할 수 있으며 런타임에서 발생할 수 있는 ClassCastException 같은 오류를 예방할 수 있다.코드 재사용성제너릭을 사용하면 다양한 데이터 타입에 대해 하나의 코드로 처리할 수 있으므로 코드의 재사용성을 높일 수 있다. 예를 들어 Integer나 String 같은 다른 타입을 처리하는 로직을 따로 만들 필요 없이 제너릭을 사용하면 하나의 로직으로 처리할 수 있다.         Generic 메서드 사용 배열 출력 예제pu..

컬렉션(Collection)여러 개의 객체를 효율적으로 저장하고 처리하기 위한 객체의 그룹자바 컬렉션 프레임워크는 이러한 컬렉션들을 다루기 위한 표준화된 API를 제공한다.이를 통해 데이터의 저장, 검색, 삭제, 정렬 등의 작업을 편리하게 수행할 수 있다.인터페이스 - "이런 기능을 해야 한다" 라는 규칙만 정의한 틀구현 클래스 - 인터페이스에서 정의한 기능을 실제로 구현한 클래스유틸리티 클래스 - 공통적인 기능(정렬, 검색 등)을 모아 놓은 클래스     주요 인터페이스Collection 인터페이스모든 컬렉션의 기본이 되는 인터페이스하위 인터페이스들과 그 구현체들이 지켜야 하는 기본적인 메서드들 정의 List순서가 있는 데이터의 집합중복된 요소를 혀용하며 인덱스를 통해 요소에 접근할 수 있다.구현 클래..

java.util 패키지자바에서 매우 중요한 클래스들을 모아놓은 패키지데이터 구조, 날짜 및 시간 관련 클래스, 랜덤 숫자 생성, 컬렉션 프레임워크 등 다양한 유틸리티 기능 제공컬렉션 프레임워크 (Collection Framework) - 리스트, 집합, 맵날짜와 시간 클래스 - Date, Calendar, TimeZone, GregorianCalendar랜덤 숫자 생성 클래스 - Random 유틸리티 클래스 - Arrays, Collections스택과 벡터 클래스 - Stack, VectorProperties 클래스Observer 패턴 관련 클래스UUID 클래스 Comparator 인터페이스Scanner 클래스Timer 클래스       Random 클래스자바에서 난수(랜덤 숫자)를 생성하기 위해 사용..

java.lang 패키지란?자바 프로그래밍의 핵심이 되는 기본 클래스들을 포함하고 있으며, 별도의 import 없이 사용할 수 있는 표준 패키지이다.ex ) Object 클래스, String 클래스, Math 클래시, System 클래스, Class 클래스, Wrapper 클래스 등등     Object 클래스자바에서 모든 클래스의 최상위 클래스모든 객체는 기본적으로 Object 클래스를 상속받는다.주요 메서드 : equals(), hashCode(), toString(), clone()     Class 클래스클래스의 메타데이터에 접근하거나 동적으로 객체를 생성하는 등의 작업을 할 수 있다.주요 메서드 : getName(), newInstance(), forName()     래퍼(Wrapper) 클래..

프로그래을 실행하는 도중에 논리적인 오류나 예기치 못한 시스템 오류들을 접하게 된다. 시스템 오류  - 갑자기 수행을 멈추거나 디스크오류 등의 시스템과 관련된 오류로서 해결이 불가능하다.논리적 오류 - 구문적으로는 올바르지만 개발자가 의도한 대로 동작하지 않는 경우비정상적인 오류(Exception) - 시스템 오류나 논리적 오류가 아닌 오류비정상적인 예외인 경우 프로그램에서 오류를 미리 예측하고 대비하여 적절한 처리를 한 다음 프로그램 수행을 계속하여 정상적인 종료가 되도록 한다.(exception handling)     예외처리 종류Array Index Out Of Bounds Exception배열의 크기를 초과하여 인덱스 지정한 경우ArithmeticException나눗셈에서 0으로 나눈 경우 발생..

문제2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다.L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다.https://www.acmicpc.net/problem/17387     난이도골드 2     코드import sysdef CCW(a1,b1,a2,b2,a3,b3) : ccw = (a2-a1) * (b3-b1) - (b2-b1) * (a3-a1) return ccwx1,y1,x2,y2 = map(int,sys.stdin.readline().split())x3,y3,x4,y4 = map(int,sys.stdi..