Do you believe in you?

문제) 코딩테스트 연습 - 숫자 문자열과 영단어 네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다. 다음은 숫자의 일부 자 programmers.co.kr 문제설명) 숫자+문자로 주어지는 string 을 모두 숫자로 치환하여 출력해야 한다. 문제풀이) 입출력 예를 보면, "one4sevennight" 을 1478로 바꿔서 출력했다. 즉, 문자는 숫자로 변환해야하고 숫자는 그대로 출력하면 된다. 따라서, string s 를 i번째부터 탐색해서 숫자가 나오면 새로운 문자열인 string numString에 넣고, 문자가 나오면 해당 문자가 zero ~ nine 중에 어떤 숫자인지를 알아내서 numSt..

[문제] 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr [문제조건] 대기실은 5개이며, 각 대기실은 5x5 크기입니다. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리가 2 이하로 앉지 말아 주세요. 단 응시자가 앉아있는 자리 사이가 파티션..

두 점 사이의 거리를 구할 때 사용하는 '유클리디안 거리'공식 ! 두 점 (x1, y1), (x2, y2)이 주어졌을 때, 두 점 사이의 거리는 다음 공식으로 구할 수 있다. #include #include // sqrt()와 pow() 함수를 사용하기 위해 using namespace std; int main(){ int x1, y1, x2, y2; double distance; cin >> x1 >> y1 >> x2 >> x2; distance = sqrt(pow(x2-x1,2) + pow(y2 - y1, 2)); cout

[문제] 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net [설명] ★이 문제가 DP 인 이유: 현재 값을 구할 때 이전 결과값을 이용할 수 있는 모양이 나오기 때문 포도주가 1잔 일 때, 1잔 모두를 선택해야 최대이다. 포도주가 2잔 일 때, 2잔 모두를 선택해야 최대이다. 포도주가 3잔 일 때, 3번째 잔을 선택할 경우와 선택하지 않을 경우로 나눌 수 있다. 이 때, 3번째 잔을 선택하지 않을 경우는 포도주가 2잔 이었을 때 구한 최대값과 같다. 3번째 잔을 선택했다면, 2번째 잔을 선택하고 1번째 잔을 선택..

백트래킹(Back Tracking) - 완전 탐색에서 불필요한 분기(Branch)를 가지치기(Pruning) - 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법 즉, Backtracking이란, 간단하게 말해 brute-force(전부 일일히 다 해보는 것)방법을 수행하지만 한정 함수(bounding function)을 이용해 경우의 수를 줄여나가는 방법을 말한다. [관련문제] 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net [풀이] 1차원 행열 int queen_col[15] 을 이용해서 퀸의 위..

2차원 행열을 2차원 벡터를 활용해서 표현해보고, 그 값을 초기화해보자. vector visited_map(4, vector(3, false)); 뜻은 2차원 행열과 같은 역할을 하는 4 X 3 짜리 2차원 벡터를 생성과 동시에 false로 초기화한다는 말이다. 그럼 아래와 같은 데이터 공간이 만들어지게찌~ false false false false false false false false false false false false 참고로 1차원 벡터의 생성과 초기화는 다음 구문으로 표현할 수 있다. vector v(4,0); 뜻은 4열짜리 벡터를 만들고 0으로 초기화 해준다는 말~ 0 0 0 0 #2차원 벡터 동적할당 및 해제 방법! #include int main(){ //동적할당 생성 vector..

▶ 다익스트라(Dijkstra) 알고리즘이란? 다이나믹 프로그래밍(DP)를 활용한 최단 경로(Shortest Path) 탐색 알고리즘. 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 구현은 Greedy 알고리즘이나 DP 알고리즘을 사용하는데, Greedy 알고리즘을 사용할 수 있는 이유는 인접한 노드들 중 가장 작은 비용을 갖고 있는 노드를 선택하여 탐색을 진행하기 때문이다. DP 알고리즘을 활용할 수 있는 이유는 "최단 거리는 여러 개의 최단 거리들"로 이루어져있기 때문이다. (최단 거리 = 최단 거리 정보들의 합) 위의 그림은 a(1)와 b(5)사이의 최단 경로를 찾는 다익스트라 알고리즘의 흐름을 보여준다. 가장 낮은 값을 가진 방문하지 않은 꼭짓점을 선택하고, 방문하지 않은 각 인..

=> map과 unordered_map의 차이는 구현방식이다. map은 균형 이진트리(Red-black tree)로 구현되고, unordered_map(hash_map)은 hash 방식(hash table)으로 구현된다. 즉, map에 들어가는 element 들은 key에 따라 정렬되어 저장되고, unordered_map은 key의 hash값에 따라서 저장된다. => 데이터가 적은 경우는 map > unordered_map, 데이터가 많은 경우는 map < unordered_map 성능이 더 좋다. map의 데이터들은 정렬되어 저장되므로 O(logN)의 탐색 속도를 보장하고, key값으로 탐색하는 unordered_map의 경우 O(1)의 탐색속도를 갖기 때문이다. 참고로 map의 경우 데이터 추가, 삭..

#1. 데이터 형식의 구분 - string: 1) 사용하기: string str = ""; (#include 헤더를 써줘야 사용가능하다. "" 큰 따옴표 사용!) 2) 입력받기: cin>>str; 로 하고 공백이 포함된 문자열이 저장된다. 3) 크기 구하기: str.size() 혹은 str.length(); 로 구할 수 있다. 4) 출력: cout charater; 하면 한글자씩 char형 배열에 저장된다. 반복문으로 공백 전까지 입력받을 수도 있다. 3) 크기 구하기: strlen(character); 로 구할 수 있다. 4) 출력: cout

▶ DP(Dynamic Programming)? : 큰 문제를 작은 문제로 나눠서 푸는 알고리즘. : 분할정복 알고리즘과 비슷. 분할정복은 작은 문제가 한 번씩 나오지만, DP는 작은 문제가 여러번 반복되어 나온다는 차이가 있다. [DP의 특징 2가지] 1) Overlapping Subproblem: 부분 문제가 겹친다. 2) Optimal Substructure: 최적 부분 구조를 가진다. * Overlapping Subproblem? Overlapping Subproblem의 대표적인 예로 피보나치 수를 구하는 방법을 들어보자. 피보나치 수는 다음과 같이 표현할 수 있다. F0 = 0 F1 = 1 Fn = Fn-1 + Fn-2(n>=2) => 0, 1, 1, 2, 3, 5, 8, 13, ... 위의 ..