본문 바로가기

Algorithm

 (55)
[BeakJoon 1285] 동전 뒤집기 안녕하세요. 오늘은 백준 1285번 동전 뒤집기라는 문제를 풀어보겠습니다. 문제는 https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net 위 링크에서 보실 수 있습니다. 문제를 요약하면 다음과 같습니다. 초기 상태가 주어졌을 때, 행 혹은 열 단위로 뒤집기를 수행합니다. 그 결과 뒷면이 보이는 수가 가장 적은 경우를 찾는 문제입니다. 저는 처음 이 문제를 보았을 때 인풋의 범위를 보고 당연히 완전 탐색을 해야지라고 생각을 했는데, 문제는 종료 조건..
[BaekJoon 14319] 종이조각 안녕하세요. 오늘은 백준 14319번 종이조각이라는 문제를 풀어보도록 하겠습니다. 해당 문제는 아래의 링크에서 확인하실 수 있습니다. https://www.acmicpc.net/problem/14391 14391번: 종이 조각 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, www.acmicpc.net 우선 문제를 살펴보면 인풋의 범위가 매우 작습니다. 4x4까지이기 때문에 완전 탐색으로 충분히 풀리는 문제입니다. 또한 이 문제가 완전탐색에 적합한 이유는 가로 방향과 세로 방향밖에 없습니다. 즉 저희가 흔히 생각하는 이런 모양이나 이런 모양은 나오지 않습니다. ..
[BaekJoon 3015] 오아시스 재결합 안녕하세요. 오늘은 백준 3015번 오아시스 재결합이라는 문제를 알아보겠습니다. 해당 문제는 https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 아래의 링크에서 확인하실 수 있습니다. 문제를 보시면, 시간제한이 1초이고, N의 범위가 500000입니다. 따라서 위 문제는 O(N^2)의 알고리즘으로 해결할 수 없으며, 기본적으로 현재를 기준으로 과거의 값을 돌아보는 형식의 로직이기 때문에 Stack을 사용하는 문제임을 추측할 ..
[BaekJoon 15684] 사다리 조작 안녕하세요. 이번 포스팅에서는 백준 15684번 사다리 조작이라는 문제에 대해 포스팅을 해보겠습니다. 해당 문제는 https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 이 링크에서 참고하실 수 있습니다. (문제가 너무 길어요 ㅜㅜ) 그렇다면 문제를 읽으셨다고 가정하고, 이 문제를 조금 단계별로 구조화해보겠습니다. 1. 사다리를 배열에 적절히 매핑하기 2. 경우의 수 구하기 3. 모든 경우의 수에 대하여 탐색 1. 사다리를 배열에 적절히 매핑하기 사..
[Algorithm] DFS, BFS 정리 안녕하세요. 이번 포스팅에서는 코딩 테스트의 단골 주제라 할 수 있는 DFS, BFS를 정리해보는 시간을 갖도록 하겠습니다. DFS, BFS는 그래프 탐색 알고리즘의 일종입니다. 그래프란 정점들과 그 정점들을 연결하는 간선으로 이루어진 자료구조입니다. 1. 깊이 우선 탐색, DFS (Depth First Search) 한 정점으로부터 시작하여 리프 노드(더 이상 갈 수 있는 연결된 노드가 없는 노드)까지 탐색을 한 뒤, 최초의 갈림길을 만날 때까지 역행하여 다른 길을 탐색합니다. 위와 같은 그래프가 있다고 해보겠습니다. 깊이 우선 탐색, 너비 우선 탐색은 기본적으로 탐색입니다. 즉 모든 노드를 탐색하는 것에 가장 큰 의의가 있습니다. 따라서 왼쪽부터 갈지, 오른쪽부터 갈지 즉 어떠한 노드를 시작으로 다음..
[BaekJoon 2852] NBA 농구 안녕하세요. 오늘은 백준 2852번 NBA 농구라는 문제를 가져왔습니다. 문자열, 구현 쪽 문제입니다. 문제는 다음과 같습니다. Team 1이 골을 넣었는데, 만약에 Team 2가 다음 골을 넣었으면 Team 1이 이기고 있던 시간에 Team 2가 방금 골 넣은 시간 - Team 1 이 마지막으로 넣은 시간을 더해주면서 문제를 해결하면 됩니다. 간단하게 제가 푼 소스코드를 먼저 살펴보겠습니다. #include using namespace std; int n, team; int score[3]; string winning[3]={"00:00", "00:00", "00:00"}; string last_goal, inp; string calc(string cur, string last) { int cur_h=..
[BaekJoon 4659] 비밀번호 발음하기 오늘은 오랜만에 재미있는 문제가 있어서 한번 가져와 보았습니다. (코딩 테스트 준비 재밌....) 바로 백준 4659 비밀번호 발음하기라는 문제입니다. 저번 학기에 제가 본 코딩 테스트 결과를 보았을 때 확실히 제가 문자열 부분이 조금 약한 듯해서 관련 문제를 여러 개 풀어보고 있습니다. 여담은 여기까지 하고 문제를 읽어볼게요! 해당 문제는 이 링크에서 확인하실 수 있습니다. 솔직히 분류는 문자열이긴 한데, 단순 구현 문제와 비슷합니다. 제가 문제를 보고 떠오른 생각은 다음과 같습니다. 1. c++ string.find() 메소드를 확인해서 a, e, i, o, u 가 있는지 없는지 확인 2. 1에서 하나라도 존재한다면, 이제 for loop를 돌며 연속하는 3개의 자음이 있는지, 3개의 모음이 있는지 ..
[C++/Algorithm] 투 포인터, 구간 합 이해하기 만약에 문제에서 연속된 데이터 구간을 처리하기를 원한다면 투 포인터 혹은 구간 합을 활용하여 O(n)의 시간 복잡도로 해결할 수 있습니다. 1. 투 포인터 {1, 2, 3, 2, 5} 의 배열이 있고, 연속된 수열의 합이 5인 수열의 개수를 묻는 문제가 있을 수 있습니다. 이러한 문제는 시간에 제한이 없다면 간단하게 for 루프를 중첩시켜 O(n^2)에 해결하는 방법이 있을 수 있습니다. 하지만 인풋 사이즈와 시간 제한으로 인해 O(n^2)의 알고리즘을 사용할 수 없는 경우라면 어떻게 해야 할까요? 그림과 같이 첫 점을 가리키는 두개의 포인터를 선언했다고 가정해 볼게요. 이 상태에서 합이 5 이상이 될 때까지 sum이라는 변수에 값들을 더해주며 End pointer를 우측으로 이동하여 줍니다. 자 Sum..

티스토리툴바