본문 바로가기

ps

 (8)
프로그래머스 레벨 1 ALL SOLVED, 오답정리 요약 1. 문자열 선언할 때 오타 ex) string arr[10] = {"zer","one", "two", "thr", "fou", "fiv", "six", "sen", "eig", "nin"}; 2. string 띄어쓰기 단위로 분류 https://chbuljumeok1997.tistory.com/42 3. 시간복잡도, 공간복잡도 계산 4. 전체적인 구성 생각 후 코딩 5. 중간 중간 생각대로 코딩됐는지 cout 등으로 찍어보기 6. 중간 계산값이 int형 범위를 넘는 경우 7. 문자열 변환 실수 ex) int n = 12; (char)(n +'0') 8. 테스트 케이스 추가하기 ex) 답이 없을 경우, 최솟값, 최댓값, 전부 같은 경우, 전부 다른 경우, 전부 답인 경우, 전부 답이 아닌 경우 한 ..
알고리즘 문제풀이 메모장 보호되어 있는 글입니다.
스택 문제 풀이2(16909, 카드 구매하기3)[Stack PS] 스택 가장 큰 특징 : LIFO 마지막에 넣은 게 가장 먼저 나온다 문제를 풀이하면서 가장 중요한 건 스택을 어떤 용도로 사용하고. 어떤 경우에 push를 하고, 어떤 경우에 pop을 해야 할까? 를 생각해야 된다. 문제풀이 11052 - 카드 구매하기 (실버1) : https://www.acmicpc.net/problem/11052 풀이 : N개의 카드를 구매하기 위해 지불할 수 있는 금액의 최댓값을 구하는 문제. 전형적인 dp(다이나믹 프로그래밍) 문제이며, N의 범위가 10^3으로 시간복잡도가 O(N^2)일 때 10^6으로 제한시간 내에 충분히 가능하다. 가장 쉬운 방법으로는 가능한 모든 경우의 수를 구하여 값 중 최댓값을 구하는 것이다. 하지만 같은 카드를 구매하는 경우에서 굳이 적은 비용을 낼 ..
스택 중간난이도 문제 풀이(Stack PS) 스택 가장 큰 특징 : LIFO 마지막에 넣은 게 가장 먼저 나온다 문제를 풀이하면서 가장 중요한 건 스택을 어떤 용도로 사용하고. 어떤 경우에 push를 하고, 어떤 경우에 pop을 해야 할까? 를 생각해야 된다. 문제풀이 9935 문자열 폭팔 : https://www.acmicpc.net/problem/9935 가장 쉽게 생각하는 방법 : 배열에 문자를 저장해서 폭발이 없을 때까지 포문 돌리기 O(N*N), N = 백만이므로 불가능 stack 사용 -> 문자열이 폭파하였을 때, 폭파 가능한 이전 문자열을 O(1)만에 찾을 수 있다. (서로 다른 문자 이므로 가능, 중복이 될 경우 첫 번째 문자인지 마지막 문자인지 구별이 안됨에 따라서 스택 알고리즘 적용이 어렵다.) 폭파 대상을 저장하는 stack 1..
이분탐색 문제 풀이[Binary Seach PS] 1. 이분탐색 문제 푸는 방법 2. 이분탐색 문제 풀이 1. 이분탐색 문제 푸는 방법 이분탐색을 이용하여 풀 수 있는 문제는 어떤 유형이고 문제를 해결하기 위해서는 어떻게 이분탐색을 이용할까? -> 정답을 구할 수 없지만, X가 가능한지 아닌지 알아내는 것은 가능한 문제들이 있다. 1. 정답을 구하는 문제(최적해 문제) A에서 B까지 가는 가장 빠른 시간을 구하는 것 2. 가능한지 살펴보는 문제(Yes/No 문제) A에서 B까지 X라는 시간으로 이동할 수 있나? 1.를 풀 수 있으면 2 또한 풀 수 있다. 2를 풀 수 있을때, 1을 풀 수 있을까? 풀 수 있다. X라는 시간에 작은 것부터 순서대로 대입하면 No가 계속 나오다. Yes가 나오는 시점이 해가 된다. =어느 한 기점을 기준으로 yes와 no가..
그리디 알고리즘(Greedy Algorithm) 그리디 알고리즘(Greedy Algorithm) 어떤 걸 결정해야 될 때, 그 순간 가장 좋다고 생각하는 것을 계속 선택해나가는 알고리즘 그때그때는 최적일지도 있지만, 최종적으로는 답이 최적이 아닐 수도 있다. 동적 프로그래밍과 같이 쓰이며 서로를 보완한다. 그리디 알고리즘의 정의 그리디 알고리즘의 특징 그리디 알고리즘 문제 풀이 전략 그리디 알고리즘 문제 풀이 그리디 알고리즘의 정의 greedy = 탐욕 = 그리디, 욕심쟁이 알고리즘 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지고 있으며, 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다. 그리디 알고리즘의 특징 1. 전..
너비 우선 탐색(BFS, Breadth First Search) 너비 우선 탐색(Breadth First Search) breadth: 폭, 너비(=width)(->length) 그래프 전체를 탐색하는 방법 중 깊이 있게 먼저 탐색하는 DFS와 달리 깊이가 같은 너비를 먼저 탐색하는 BFS BFS의 정의 BFS의 특징 BFS와 DFS 과정 비교 BFS 구현 BFS 문제 풀이 BFS의 개념 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법. 시작 정점으로 부터 가까운 정점(height가 낮은 곳부터)을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회함으로써 노드를 넓게(wide) 탐색한다. BFS는 두 노드 사이의 최소 경로를 구하는 성질이 있어, 주로 '최단 경로', '최소 몇 번', '최소 이동 횟수', '최소 연산 횟수..
[서평]대체 뭐가 문제야(Are Your Lights On?) - Gerald Marvin Weinberg 대체 뭐가 문제야? 라는 책이름에서도 알 수 있듯이 문제에 대해서 좀 더 생각하게 하는 에피소드를 담은 책이다. 에피소드는 어떤 문제 상황에 대해서 정리함씨가 문제에 대해서 여러방면으로 생각하며 해결하는 방식이다. 180쪽 밖에 되지 않고 그림도 종종 있어서 가볍게 읽을 만한 책이였다. 무언가 명확한 답변을 주기보다는 에피소드를 통해서 책을 읽으면서 경험을 하게하고 생각에 잠기며 '아 이럴수도 있겠구나' 라는 생각이 들었다. 문제에 대해서 경험을 대신해주며 교훈을 주는 책이였다. 무엇이 문제인가? 문제는 무엇이고, 누구의 문제이고, 당신의 문제의 핵심은 무엇인가? 문제에 대해서 여러방면의 '왜?'를 계속 던져본다. 성급하게 해결안을 찾아내다보면 실제 현안과 동떨어지는 경우가 많다. 실제로 자연스러운 일상..

티스토리툴바