Hee's Story

문제 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오. 길이가 짧은 것부터 길이가 같으면 사전 순으로 https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1≤N≤20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 입력 첫째 줄에 단어의 개수 N이 주어진다. (1≤N≤20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. 출력 조건에 따라 정렬하여 단어들을..

Binary Search : lower bound & upper bound Binary Search (이진 탐색) 이진 탐색은 정렬이 된 데이터에서 어떠한 특정 값이 존재하는지 검색하는 알고리즘이다. 기준 값을 구해서 그 값을 기준으로 데이터를 나눠서 검색하는 방법이다. 특정 값을 찾을 때는 기본 이진 탐색으로 쉽게 구할 수 있다. 하지만 중복된 데이터에서 탐색할 때는 조금 더 응용된 방법을 사용해야한다. (예를 들어, 중복 된 데이터에서 특정 데이터가 몇 개가 존재하는지 등) 따라서 lower bound와 upper bound를 구해야한다. Lower bound는 데이터 내에서 특정 값보다 같거나 큰 값이 처음 나오는 위치를 리턴해준다. High Bound는 특정 값보다 처음으로 큰 값이나 나오는 위치..

문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GOPPaAeMDFAXB&categoryId=AV7GOPPaAeMDFAXB&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀기 전 생각 DFS를 사용해서 풀어야겠다. 무한루프에 빠지지 않기 위해 방문한 노드들을 확인한다. 이 때, 다음에 돌 때를 위해 방문한 노드들을 다시 false로 만들어준다. 예를 들어 아래의 경우 노드 2를 방문하고 난 후 노드 3으로 갈 때 방문표시를 false로 하지 않으면 1->2->3->4으로 끝나버린..

문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GKs06AU0DFAXB&categoryId=AV7GKs06AU0DFAXB&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com N-Queen은 백 트래킹 문제의 대표이다. 백 트래킹 설명 : https://hee96-story.tistory.com/57?category=827781 [알고리즘] Backtracking (백 트래킹) Backtracking (백 트래킹) 모든 경우의 수를 전부 고려하는 알고리즘이다. 즉, 조합 알고리즘 문제..

Backtracking (백 트래킹) 모든 경우의 수를 전부 고려하는 알고리즘이다. 즉, 조합 알고리즘 문제에 대해 어떤 조건을 만족할 때 모든 가능한 해를 나열한 것이다. 일종의 트리 탐색 알고리즘으로 DFS, BFS 등의 방식을 사용한다. DFS 모든 경우의 수를 고려해야 하는 문제일 때 주로 사용한다. 하지만 트리의 깊이가 무한대가 될 때는 절대 사용하면 안된다. (무한루프에 빠짐) -> 이 때, 중복검사를 따로 해야 함 BFS 최단거리를 구할 때 주로 사용한다. Backtraking의 대표적인 예제로 N-Queen이 있다.

문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 주어진 제약 사항 1 ≤ N ≤ 4 2 ≤ W ≤ 12 2 ≤ H ≤ 15 풀기 전 생각 Q. 어디서 구슬을 떨어트려야 최대로 벽돌이 깨지는가? -> 그럼 어디서 구슬을 떨어트려야 하는가?? => 어디서 최대로 벽돌이 깨지는지 모르니까 하나씩 해보자!! -> 구슬은 최대 4개까지 떨어지고 W는 최대 12이다. 최악일 경우 12^4 = 20,736번 케이스를 돌아야 한다. -> 이 정도는 ..