본문 바로가기

분류 전체보기

 (224)
[java] HashSet() HashSet() Set 인터페이스에서 지원하는 구현 클래스 순서대로 입력되지 않음 null 요소를 허용 중복을 허용하지 않음 HashSet() 변수 선언 HashSet set = new HashSet();//integer 형의 hashmap 데이터 HashSet set2 = new HashSet();//string 형의 hashmap 데이터 HashSet() 메서드 - .add(value) : hashset에 데이터를 추가한다. - .remove(value) : hashset의 데이터를 삭제한다. - .clear() : 모든 데이터를 삭제한다. - .size() : hashset의 길이를 출력한다. - .contains(value) : value값이 있는지 확인하고 있으면 true, 없으면 false를..
[TIL] 백트래킹 - N-Queen 문제 백트래킹(Backtracking) 제약 조건 만족 문제에서 해를 찾기 위한 전략 해를 찾기 위해 답이 될 수 있는 후보군의 제약 조건을 체크하다가 만족할 수 없는 경우 즉시 backtrack하고 다른 후보군으로 넘어간다. 고려할 수 있는 경우의 수를 상태공간트리(State Space Tree)를 통해 표현한다. DFS 방식으로 확인한다. promising (해당 루트가 조건에 맞는지를 검사하는 기법) pruning(가지치기 : 조건에 맞지 않으면 포기하고 다른 루트로 돌아서서 탐색의 시간을 절약하는 기법) N-Queen 문제 백트래킹의 대표적인 문제 - N*N 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치한다. - 퀸은 수직, 수평, 대각선으로 이동 가능하다. ex)N이 4일 경우 다음과 같이..
[TIL] 최단 경로 알고리즘 - 벨만 포드 알고리즘 벨만 포드 알고리즘 최단 경로 알고리즘 중 하나로 가중치가 음수인 경우 적용 가능하다. 다익스트라보다 시간복잡도가 느리다. 음수 사이클 존재의 여부를 파악할 수 있다. 관련문제 11657번: 타임머신 (acmicpc.net) 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 처음 문제를 접근 할 때 벨만 포드 알고리즘을 몰랐기 때문에 다익스트라 알고리즘으로 접근하였다. 3개의 테스트 케이스를 분석한 뒤에 나름대로(?) 가중치가 음수인 경우를 따로 분리하..
[TIL] - 유클리드 호제 - 최소공배수와 최대공약수 유클리드 호제 (Euclidean algorithm) - 2개의 자연수 혹은 정식의 최대공약수(gcd)를 구하는 알고리즘의 하나이다. - 2개의 자연수 a,b에 대하여 r을 a%b (a>b) 라고 할 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. - 결론적으로 b%r 인 r'를 구하고 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대 공약수가 된다. - 최소공배수는 두 자연수 (a*b)/gcd(a,b) 이다. 관련 문제 코딩테스트 연습 - N개의 최소공배수 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기..
[java] toCharArray() toCharArray() - String 문자열을 char 형 배열로 반환해주는 메서드 package programmers_java; public class lv2_7 { public static void main(String[] args) { // TODO Auto-generated method stub String arr = "asdfg"; // 문자열에서 한 글자씩 접근 for(char i : arr.toCharArray()) { System.out.println(i); } //char형 배열로 만들어 배열 출력 char[] arr2 = arr.toCharArray(); System.out.println(Arrays.toString(arr2)); } } /* a s d f g */ /* [a, s,..
[java/python] 프로그래머스 Lv2. - JadenCase 문자열 만들기 코딩테스트 연습 - JadenCase 문자열 만들기 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 파이썬으로 코드를 짤 때 처음에는 isupper, islower 등의 함수를 이용하여 짰는데 풀이코드를 참고하던 중 간단한 함수가 있어 기록하려 한다. [python] def solution(s): answer='' s=s.split(" ") for i in range(len(s)): s[i] = s[i].capitalize() answer =' '.join(s) return answer capital..
패스트캠퍼스 Python 개발자 취업 합격 패스 with 코딩테스트, 기술면접 강의 4주차 강의 한 달 후기 패스트캠퍼스의 python 개발자 취업 합격패스 패키지 강의는 정말 다양하게 수록이 되어있다. 기본 자료구조와 알고리즘 그리고 이를 활용한 코딩테스트 문제 풀이와 기술면접까지 굉장히 방대한 양을 무제한으로 수강 가능해서 취업을 준비하며 유용하고 사용하고 있는 강의이다. 특히 자료구조와 알고리즘 부분이 가장 부족한 부분이었는데 이번 강의를 통해 순서대로 알고리즘을 학습할 수 있어서 기초를 다지는데 굉장히 도움을 많이 받았다. 자료구조와 알고리즘을 모두 학습하였고 기본기를 바탕으로 코딩테스트 기초 문제풀이부터 시작하였다. 최근 한 달 동안은 코딩 테스트 연습을 하며 나동빈 강사님이 해설해주시는 코딩테스트 강의를 중심으로 학습하였다. 백준 문제 2-3개의 코딩테스트 연습문제를 학습한 뒤 해설해 주시는데 문제별..
[TIL] 플로이드-워셜 - Floyd-Warshall 플로이드-워셜 알고리즘(Floyd-warshall) 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산하는 알고리즘 2차원 테이블에 최단 거리 정보를 저장한다. 다이나믹 프로그래밍 유형에 속한다. 각 단계마다 특정 노드 k를 거쳐 가는 경우를 확인하여 a-b의 최단 거리보다 a-k-b가 짧은지 검사한다. 플로이드-워셜 알고리즘 문제 1956번: 운동 (acmicpc.net) 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net import sys #플로이드 워셜 input ..
728x90

티스토리툴바