알고리즘/BOJ(백준)87 [ BOJ / 완전탐색 ] 알파벳 1. 문제 1987번: 알파벳 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 www.acmicpc.net 2. 소스코드 - visited 처리를 처음엔 string으로 route를 기록하고 find로 찾았더니 시간초과가 났다. - 그래서 visited[ 현재 문자 - 'A' ] 형식으로 수정. - 문제를 잘못 읽어서 총 알파벳 종류가 C개인 줄로 알았는데, C개가 아니다. 직접 세야하고, 이를 이용해 백트래킹을 해주면 시간을 조금 줄일 수 있다. - 나머지는 무난한 DFS 코드. - 소스코드 #include #include #include #def.. 2020. 7. 21. [ BOJ / Stack ] 후위 표기식2 1. 문제 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이�� www.acmicpc.net 2. 소스코드 - 간단한 후위표기식 문제에서, 치환만 추가된 문제. - 치환을 위해 배열을 하나 생성하고, 해당 배열에 치환 값을 저장했다. - map을 써도 된다. 메모리상으론 map이 더 효율적이다. 소스코드 #include #include #include using namespace std; int n , LUT[92]; double calPost(string str) { int size = str.size(); stack nums.. 2020. 7. 11. [ BOJ / 투포인터 ] 차집합 1. 문제 1822번: 차집합 첫째 줄에는 집합 A의 원소의 개수 n(A)와 집합 B의 원소의 개수 n(B)가 빈 칸을 사이에 두고 주어진다. (1≤n(A), n(B)≤500,000)이 주어진다. 둘째 줄에는 집합 A의 원소가, 셋째 줄에는 집합 B의 원소가 www.acmicpc.net 2. 소스코드 - 교집합을 구하는 문제와 해결방법이 동일하다. 2020/07/08 - [PS/구름] - [ 투포인터 ] 교집합 찾기 - 둘 다 정렬 후, 투포인터 알고리즘을 이용한다. - 초기 세팅으로 A, B 두 배열을 오름차순으로 정렬한다. ( 1, 2, 3, 4 ..... ) 1) A-B 연산을 한다고 하면, A의 배열 끝에 도달할때까지 알고리즘을 수행한다. 2) 포인터A와 포인터B을 0으로 초기화 한다. 포인터 A.. 2020. 7. 9. [ 프로그래머스 / String ] 문자열 압축 소스코드 1. 문제 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자 programmers.co.kr 2. 소스코드 - 꼼꼼히 풀면 쉬운문제. 물론 나는 해맸다. - 문자열의 최대 길이는 1000이다. 문자열은 최대 절반 길이까지만 압축이 가능하므로, 최대 500회를 비교해야한다. 1번 비교하는데 약 1000회라고 하면, 500 x 1000 = 50만 연산이 필요하다. 이 정도면 단순 for문으로도 널널하게 수행될 것이라 예상함. - substr을 쓰는게 편했다. - 압축되는 수 만큼, 숫자를 문자앞에 붙여줘야하는데 ( 예, 5abc ) 이를 처.. 2020. 6. 26. 이전 1 2 3 4 ··· 22 다음