본문 바로가기

BOJ

Baekjoon 17136 색종이 붙이기 2019. 6. 2. Link https://www.acmicpc.net/problem/17136 소스결과 1988 KB / 36 ms 언어 C++ 17 출처 Baekjoon 분류 브루트 포스 설명 10 x 10 의 판에 1 이 적힌 부분을 덮기 위해 필요한 색종이의 수를 구하여라. 삽질에 삽질에 삽질을 했던 문제. 타임아웃 문제를 해결해야 했던 문제도, 그리디로 처리해 오답이 나온 경우도 있었다. 타임아웃의 경우는 한 위치에서 5x5 색종이가 놓는게 가능하다 할 때 이 위치는 4,3,2,1 이 가능하기때문에 모든 경우에 다 대입하는 방법이었는데 시간도 오래 걸릴 뿐 더러, 굳이 할 필요가 없는 문제였다. 그리디로 처리한 경우는 예제중 한 경우도 통과 못했었다. 정답은 타임아웃 경우를 조금 수정한 방법이었는데. 색종이를 놓을..
Baekjoon 14500 테트로미노 2019. 6. 2. Link https://www.acmicpc.net/problem/14500 소스결과 2476 KB / 48 ms 언어 C++ 17 출처 Baekjoon 분류 브루트포스 설명 1x1 정사각형 4개로 이루어진 테트로미노를 n x m 크기의 종이에 최대한 배치 할 때, 테트로미노가 놓인 칸의 수의 합을 출력해준다. 일단 이 문제를 보았을 때 떠올린 방법은 나올 수 있는 모든 경우의 수를 배열에 넣어 배치하는 방법밖에 안떠올랐다. 이 후, 다른 해답들을 보면서 DFS로 이 문제가 해결 가능하다는 것을 알았다. 문제에서 주어진 도형을 회전과 대칭을 이용해서 나올 수 있는 경우의 가지수는 총 19가지. 19가지의 방법의 가로, 세로크기가 각각 다 다르기 때문에 각각의 경우를 19칸 배열에 저장하고, 각각의 경우를..
Baekjoon 1543 문서 검색 2019. 6. 2. Link https://www.acmicpc.net/problem/1543 소스결과 1988 KB / 0 ms 언어 C++ 17 출처 Baekjoon 분류 그리디 알고리즘, 문자열 처리, 탐색 설명 영어로만 이루어진 문서가 주어질 때 검색하고 싶은 단어가 중복되지 않게 몇번 등장하는지 알아보자. 문제의 난이도에 비해 정답률이 낮은게 의문이었다. 아마 원인은 String 클래스의 find 함수나 indexOf 함수를 이용하며 생기는 검색 속도 문제일꺼 같다. 이번 문제는 String 클래스의 find와 indexOf 함수를 합쳐놓은(?) 방식으로 풀었다. 알고리즘 1. 총 문자열과, 검색할 문자열을 입력 받는다. 2. 0번 인덱스부터 문자열을 비교한다. 2-1. 현재 탐색하는 문자열의 위치와, 탐색할 문자..
Baekjoon 1761 정점들의 거리 2019. 4. 22. Link https://www.acmicpc.net/problem/1761 소스결과 6504 KB / 668 ms 언어 C++ 17 출처 Baekjoon 분류 LCA 설명 가중치가 있는 트리가 주어질 때 두 정점 사이의 가중치의 합을 출력한다. 기존 LCA문제에서 가중치가 추가된 LCA문제. 단지 루트 노드가 지정이 되지 않았기에 어느 노드를 기준으로 깊이를 설정해도 상관은 없다. 가장 일반적이게 1번 노드를 기준으로 깊이를 지정했다. 두 정점이 주어졌을 때 두 정점의 깊이를 맞추는 과정에서도 가중치의 합을 구해야 하는 것을 조심 해야한다. 두 정점의 깊이가 일치해 졌다면 같은 공통 조상까지 찾아가면서 가중치의 합을 구하면 최소 거리가 된다. 알고리즘 1. 간선과 가중치 정보를 입력 받는다. 2. 임의의..
Baekjoon 11437 LCA 2019. 4. 22. Link https://www.acmicpc.net/problem/11437 소스결과 7400 KB / 816 ms 언어 C++ 17 출처 Baekjoon 분류 LCA 설명 1을 루트로 하는 트리가 주어질 때 두 정점의 가장 가까운 공통 조상의 번호를 출력한다. LCA를 처음 공부할 때 개념을 잡기 좋은 문제라고 한다. 다른 블로그를 돌아다니면서 개념을 익힐 때 왜 깊이를 DFS로 설정해 주는지 의문을 가졌었다. 예제를 직접 노트로 옮겨보니 바로바로 이어져서 입력과 동시에 깊이와 부모를 설정해 줬는데 제출을 하니 바로 시간초과에 걸렸었다. TC로 들어오는건 꼭 1이 있는 트리에 이어져서 들어오는게 아니라 나눠져 들어오기 때문에 깊이와 부모 설정에 문제가 생겨 높이를 맞추는 과정에서 무한루프에 빠지게 됬었..
Baekjoon 1967 트리의 지름 2019. 4. 21. Link https://www.acmicpc.net/problem/1967 소스결과 2700 KB / 4 ms 언어 C++ 출처 Baekjoon 분류 BFS, 트리 설명 트리의 최대 지름을 출력해주자. 어떤 경우가 트리의 지름이 최대가 되는지를 생각하는 것이 가장 어려운문제. 질문 게시판에서 해답을 얻었던 문제. 루트노드에서 갈 수 있는 최장 거리 노드는 무조건 리프노드가 된다. 그렇다면 최장 거리에 있는 리프노드를 기준으로 가장 멀리 있는 다른 노드를 찾는다면 최장 지름을 얻을 수 있다. 해당 아이디어만 있으면 됬던 문제. 떠올리지 못했던 것이 조금 아쉽다. 알고리즘 1. 노드와 간선 정보를 입력 받는다. 2. 1번 노드(root Node)를 기준으로 가장 멀리있는 노드를 구한다. 3. 구해진 노드를 ..
Baekjoon 2206 벽 부수고 이동하기 2019. 4. 21. Link https://www.acmicpc.net/problem/2206 소스결과 16516 KB / 52 ms 출처 Baekjoon 언어 C++ 17 분류 BFS 설명 벽을 한번 부술 수 있는 상태에서 0,0 에서 n,m 으로 갈 수 있는 최단 거리를 출력해주자. 과거에 비슷한 유형의 문제를 푼 적이 있다. 방문 체크를 할 때 벽을 부순 상태에 따라서 사용해야 하는 방문체크 변수가 다르다. 같은 위치에서 벽을 부수고 왔거나 부수지 않고 온 경우에 따라 도착거리가 달라 질 수 있기 때문이다. 그 부분을 분리해서 진행하면 생각보다 간단한 문제가 된다. 알고리즘 1. 가로, 세로 크기와, 맵 정보를 받는다. 2. 현재 위치에서 상,하,좌,우로 이동하는 경우를 판별한다. 2-1. 다음 위치가 맵 범위에 속하..
Baekjoon 17144 미세먼지 안녕! 2019. 4. 18. Link https://www.acmicpc.net/problem/17144 소스결과 1992 KB / 60 ms 언어 C++ 17 출처 Baekjoon 분류 시뮬레이션 설명 미세먼지와 공치청정기가 있는 환경에서 미세먼지가 확산과 이동이 t번 반복 후 남아있는 미세먼지를 출력하자. 미세먼지가 퍼지는 방법, 공기청정기를 기준으로 공기의 이동까지 크게 예외를 생각할 부분이 없다. 미세먼지 확산 시 상하좌우를 확인 후, 미세먼지의 감소 양이 정해지고 상하좌우를 확인해 확산 할 수 있는 부분만 확산 하기 때문에 같은 코드가 두번 사용되는게 아쉬웠다. 미세먼지가 순차적으로 퍼지는게 아니라 동시에 퍼지기 때문에 이전 값을 기준으로 다음 값을 갱신해야한다. 즉 맵 전체를 복사하는 과정이 반복마다 필요하다. 공기청정기..

티스토리툴바