하서망 블로그

https://www.acmicpc.net/problem/1920이번에 해결한 문제는 Baekjoon의 1920번 "수 찾기" 문제다. 이 문제는 N개의 정수 집합이 주어졌을 때, 주어진 수들이 해당 집합에 존재하는지 확인하는 프로그램을 작성하는 것이다. 문제 자체는 단순해 보였지만, 중간에 실수를 발견하고 해결하는 과정이 있었다. 문제 설명 N개의 정수가 주어진 후, M개의 다른 정수들이 그 N개의 집합에 포함되어 있는지 확인하면 된다. 예를 들어, N개의 정수 집합이 `4, 1, 5, 2, 3`이고, 확인해야 할 수들이 `1, 3, 7, 9, 5`라면, 각 수가 존재하는지 여부를 1 또는 0으로 출력하면 되는 문제다. 처음 작성한 코드처음에는 이 문제를 `set` 자료구조로 쉽게 해결할 수 있다고 생..

진법 변환 진법 변환 기본 코드 while(N>0){ int D=N%B; if(D 'A', 1 -> 'B' //아스키 코드 이용 (char) (변수)+'A' BOJ 11005 코드 #include #include #include using namespace std; int main() { int n, b; vector vec; char c[36]; cin>>n>>b; //숫자+문자열 for (int i = 0; i pow(b,j)){ j++; } //10이 넘어갈 경우 문자열 추가 for (int i = 0; i < 26; i++) { c[i + 10] = 'A' + i; } //본격적인 진법 변..

시간 제한이 엄격한 문제에서는 입출력의 속도가 중요합니다. 입출력을 줄이는 방법은 크게 두가지가 있습니다. 1. 맨 앞에 코드 추가 ios_base::sync_with_stdio 구문은 c의 stdio와 cpp의 iostream을 동기화시켜주는 역할을 하는데, 이 때 iostream과 stdio의 버퍼를 모두 사용하기 때문에 딜레이가 발생합니다. 따라서, ios_base::sync_with_stdio(false); 코드를 작성해줌으로써 동기화를 비활성화시켜줍니다. 이로 인해, c++만의 독립적인 버퍼가 생성되어 c의 버퍼와 병행하여 사용할 수 없게 되지만, 사용하는 버퍼의 수가 줄어들었기 때문에 실행 속도는 빨라지게 됩니다. 알고리즘 문제를 풀 때는 대부분 싱글 쓰레드 환경이기 때문에 해당 코드를 추가해..

배열 원소의 값 == 해당 index의 개수 카운팅 정렬은 배열의 index에 의미를 부여하는 방식 사용하는 이유 : 많은 탐색이 필요한 상황에서 탐색의 횟수를 줄여주기 때문이다. 주로 사용되는 곳 : 무언가를 "기록"할 때, 카운트할 때, 존재를 확인할 때 주로 사용된다. 못 사용하는 경우 : 문자열을 기록할 때, 정수외의 값을 index로 사용할 때 만약 입력이 2,1,4,2,3,5,5,4,4 이라면, cnt 배열은 다음과 같다. cnt[0] cnt[1] cnt[2] cnt[3] cnt[4] cnt[5] 0 1 2 1 3 2 이중 반복을 이용해 중복이 있는 N개의 수를 빠르게 정렬할 수 있다. Ex) https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫..

순열과 조합 개념과 차이점 순열(Permutation) : 순서를 정해서 나열 ex) 1,2,3 중에서 두개를 뽑아 나열할 경우 : {1,2}, {1,3}, {2,3}, {2,1}, {3,1}, {3,2} 조합(Combination) : 순서가 정해지지 않은 집합들의 모음들, 뽑기 ex) 1,2,3 중에서 두개를 뽑을 경우 : {1,2}, {1,3}, {2,3} 차이점 : 순열은 순서가 중요하고 조합은 순서 상관없다. 예를 들어 수열 같은 경우 {1,2} , {2,1} 은 다르지만 조합의 경우 원소가 1,2로 같기 때문에 {1,2} 하나로 생각한다. 순열 구현 1. C++ algorithm 라이브러리의 next_permutation, prev_permutation 사용 *next_permutation ..

블로그 글 쓰는게 정말 오랜만인 것 같네요..! 교환학생 당시에 열심히 블로그 쓰려했지만 너무 많은 여행과 일정으로 잠시 블로그를 접었어요. 교환학생 이야기는 틈나면 다시 작성해보겠습니다. 한국 돌아와서 소마(소프트웨어 마에스트로)에 도전하고자 열심히 알고리즘 공부를 하던 도중 재밌는 사실을 발견해서 기록하고자 블로그를 작성하게 되었습니다. 이분 탐색 기본 문제를 풀이하던 도중, 정렬이 자동으로 되는 set을 사용해서 이 문제를 풀었습니다. 이분 탐색을 공부하고자 해당 문제를 풀었으니 std::binary_search()를 사용했더니 세상에 시간초과가 났습니다. #include #include #include using namespace std; int n; //배열 크기 set s; int m; voi..

안녕하세요. 오늘은 알고리즘 중에서 완전탐색 브루스포스에 대해서 포스팅하겠습니다! 완전탐색은 문제를 해결하기 위해 확인해야하는 모든 경우를 전부 탐색하는 방법입니다. 예를 들어, 4가지 숫자로 이뤄진 금고의 비밀번호를 알고자한다면 0000부터 9999까지 모든 경우의 수를 직접 시도해보는 방법이 브루스 포스 알고리즘입니다. 브루스포스 알고리즘 유형은 보통 다음과 같습니다. N개중 (중복을 허용해서/중복없이) M개를 (순서 있게 나열하기/순서 상관없이 고르기) 15651번은 브루스포스 유형 중 N개중 중복을 허용해서 M개를 순서있게 나열하는 방법입니다. https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다...

백준 출력 관련 문제들(10171[고양이],10172[개],25083[새싹])을 풀다보면 \(역슬래쉬), '(작은 따옴표), "(큰따옴표) 출력이 안되는 에러를 접할 수 있다. 이는 이스케이프 시퀀스(Escape Squence)와 관련이 있다. 이스케이프 시퀀스(Escape Squence) 이스케이프 시퀀스란 백슬래시(\) 뒤에 한 문자나 숫자 조합이 오는 문자 조합이다. 줄 바꿈 문자, 작은따옴표, 또는 문자 상수의 다른 특정 문자를 나타내려면 이스케이프 시퀀스를 사용해야한다. 이스케이프 시퀀스는 주로 탭이나 줄바꿈을 나타낼때 사용되지만 인쇄할 수 없는 문자인 ', ",\ 를 표현하기 위해 사용되기도 한다. 이스케이프 시퀀스의 종류는 다음과 같다. 따라서 \, ', "를 출력하기 위해서는 다음과 같은 ..