백준128 [백준 1926/c++] 그림 BFS 의 대표 기본 문제 칠해졌는지 아닌지를 판단하기 위해 2차원 보드에 값을 넣어 확인하고 이전에 방문 여부를 위해 보드 크기만큼의 visited 배열을 만들어 확인, 이동 가능 하다면 그 좌표를 큐에 넣고, 방문제크 한 후 큐에서 좌표를 하나씩 빼가며, 뺀 것을 체크할 현재 좌표라 하고, 현재 좌표에 이동가능한 상하좌우 범위를 2개의 배열을 사용해서 이동 후의 4개의 좌표 값을 구현, 이동 후의 좌표 값이 범위 밖이거나, 칠해지지 않았는지의 예외 조건이 아니라면 그 예상 좌표를 방문처리하고 큐에 넣어 계속 진행해나간다 그림의 수는 전체 2차원 보드를 이중 for문으로 하나씩 돌며, 칠해졌는데 방문하지 않은 것들을 위의 과정으로 체크해나가면서 파악하면 된다. 칠해진 영역의 수는 BFS 중에 큐에 들어.. 2022. 8. 7. [백준 1406/c++] 에디터 임의의 위치에 삽입과 삭제가 잦은 경우, 시간복잡도 상의 이득을 위해 연결 리스트의 자료구조를 생각해보아야 한다 연결리스트는 양 끝을 제외하고는 이전 주소 값과 다음 주소 값을 가지는 노드를 가진 구조이다 C++ 의 STL list 를 이용해서 풀면 상대적으로 구현이 편하다 https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.. 2022. 8. 6. [백준 10816/c++] 숫자 카드 2 숫자 카드 풀을 배열로 설정하면 배열 크기만 1000만이 넘게 되는데 너무 큰 크기의 배열은 컴파일러가 프로그램의 실행을 막게되어 실패가 뜬다 따라서 배열로 카운트 하면 안되고, map 을 사용해서 풀면 되는 문제이다 수가 워낙 크니 입출력 속도 향상을 위해 ios_base::sync_with_stdio(false)를 넣어주자 + 다른 사람들의 풀이를 보니 카드의 수를 벡터에 넣고 정렬 후 upper_bound, lower_bound 함수를 써서 인덱스 차이로 해당 카드의 개수를 파악하는 방법을 많이 쓰더라 멋진 아이디어다! 근데 나는 그 함수 첨들었고... 내 풀이가 더 쉬운 것 같다 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가.. 2022. 8. 5. [백준 9663/c++] N-Queen 백트래킹 심화 문제. 푸는 방법은 2가지가 자주 쓰인다 첫번째로, 조건을 판단할 함수를 만드는 방법 퀸은 위 아래 대각선에 영향을 주므로 퀸의 위치들을 배열에 넣은 후 배열을 돌며 놓을 수 있는지 여부를 판단할 함수를 만들어서 푸는 방법 퀸의 위치를 나타내는 배열을 나타낼 시 배열 내 요소의 인덱스를 열로, 요소의 값을 행으로 나타내서 2차원 배열이 아닌 1차원 배열만으로 퀸의 위치를 표현 가능하다 간단하지만, 배열을 돌며 여부를 체크해야 하므로, 시간복잡도가 추가로 O(n) 가 소모된다 두번째로, 함수대신 퀸이 영향력을 줄 수 있는 라인들을 배열로 저장해서 이전의 isused 체크처럼 사용하여 퀸을 놓을 수 있는지 체크하여 푸는 방법이다 배열의 크기를 40 으로 설정했는데, 가로가 n칸 일때 열의 인덱.. 2022. 8. 4. 이전 1 ··· 15 16 17 18 19 20 21 ··· 32 다음