알고리즘

[C++] 백준 14503번 로봇 청소기

구현 / 시뮬레이션 문제. 구현하는 문제는 뭔가 테스트 케이스가 많이 필요한 것 같다. 아래 올린 링크에서 테스트 케이스를 보고 나서야 풀 수 있었다. 글 읽기 - [로봇 청소기] 테스트 케이스(반례) 공유합니다. 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net 구현 문제는 뭔가 이해하기도 어렵고, 이해했다쳐도 이걸 코드로 어떻게 짜야할지 잘 생각이 안난다. 무한루프와 틀렸습니다를 거치고 반례를 통해 문제점을 찾은 후에야 맞출 수 있었다. 처음 이 문제를 봤을 때 처음에는 그냥 현재 보는 방향에 따라 모든 조건을 다 걸어주려고 했다. 그런데 이렇게 짜면 예외처리할 상황이 너무 많기도 하고, 코드도 너무 비효율적으로 길어지는 것 같아서 다른 방법을 생각해봤다. 방향이 0, 1, 2, 3으..

[C++] 백준 10026번 적록색약

그래프 탐색 문제. 그래프 탐색 문제는 문제를 잘 이해하고 코드로 잘 구현하면 어렵지 않게 맞출 수 있다. 골드 문제지만, 쉽게 맞출 수 있는 문제였다. DFS로 풀면 최악의 경우 100 * 100번 탐색하므로 10,000번 이므로 시간 내에 완벽하게 풀 수 있다. 문제풀이 어려운 문제는 아니다. 그냥 연결요소의 개수를 구하는 문제인데, 적록색약이 빨간색과 초록색을 같은 색으로 보는 것을 유의하면서 문제해결을 해주면 된다. memset() 메서드를 사용해서 초기화 하기위해 cstring STL을 사용했다. widthHeight : 입력받는 길이 n board 배열 : 입력받는 그리드를 저장하는 char 배열이다. visit 배열 : DFS를 할 때 이미 방문한 곳인지 체크하는 배열이다. normalRes..

[C++] 백준 15686번 치킨 배달

구현 및 브루트 포스(완전 탐색) 문제. 처음에 잘못된 백트래킹과 dfs로 접근해서 시간초과를 많이 냈다. 백준 게시판에서 도움을 얻고, 겨우 풀었다. 처음 이 문제를 봤을 때 백트래킹으로 폐업시킬 치킨집을 정하고 그래프 탐색으로 (처음에는 BFS로 하려 했으나 코드로는 DFS로 했다.) 최단거리에 있는 치킨집의 거리를 다 구해서 더하고 어떤 치킨집들을 폐업시킬 때 최소 거리가 나오는지 구하려 했다. 이 방법은 시간초과가 났고, 게시판을 참고한 결과 다음과 같은 도움을 얻었다. 폐업시킬 치킨집을 고르는 것이 아닌, 그냥 치킨집들 중 어떤 치킨집들을 open할 지 결정하면 된다. 각 집들의 거리와 치킨집들의 거리를 저장해두고 쓰면, 굳이 도시들을 다시 살펴보지 않아도 된다. 이 두개가 이 문제의 keypo..

[C++] 백준 2468번 안전 영역

2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net (문제가 길어서 캡쳐화면 대신 링크로 대체) 그래프 탐색 문제. 그래프 탐색에 브루트 포스(완전 탐색)를 곁들인(?) 문제이다. 문제를 이해하는 것도 어려웠고, 생각해야할 조건들도 까다로웠다. 문제풀이 일단 문제를 잘 해석해보면 연결 요소의 개수(ConnectedComponents)를 구하는 문제라는 것은 알 수 있다. 그리고 고려해야할 사항들이 있다. 물의 높이보다 낮거나 같으면 물에 잠긴다. 모든 도시가 물에 잠기지 않을 수도 있다. (연결 요소의 개수는 최소 0이..

[C++] 백준 11403번 경로 찾기

그래프 이론 문제. i에서 j로 가는 경로가 있다면 인접 행렬(AdjacentMatrixGraph)로 1을 나타내고 없다면 0을 나타내면 된다. DFS나 BFS를 이용해서 인접 행렬을 업데이트 하면 된다. 처음에는 자기 자신은 무조건 방문하므로 1인줄 알았는데, 두번째 테스트 케이스를 보고서 자기 자신을 돌아올 수 있는 경우에만 1이고 시작에만 자기 자신이 있다면 0이였다. DFS, BFS는 구현만 할 줄 알면 쉽게 풀 수 있다. 문제풀이 그래프 이론 문제는 개념만 알고 있으면 문제를 이해하는 것은 쉬우므로 바로 코드해석을 하겠다. 먼저 정점의 개수 vertex변수. 인접한 정점들의 번호를 담을 벡터 adjList, 각 정점마다 어떤 정점들을 갈 수 있는지 정보를 담을 인접행렬 check 2차원 배열을 ..

[C++] 백준 2293번 동전 1

다이나믹 프로그래밍 문제. 처음에 문제에 접근할 때, 재귀함수로 접근하려 했는데 시간제한을 보고 포기했고, 알고리즘 분류를 보고 DP인 것을 봐도 어떻게 풀어야 할 지 감이 잘 오지 않았던 문제. 많이 고민해봤지만 생각하기 어려워서 결국 솔루션을 보고 해결했다. 이런 방법으로 생각할 수도 있구나라고 생각했다. 풀이를 정리할 겸 글을 적는다. 문제 풀이 먼저 DP문제를 풀 때에는 항상 규칙을 찾아야 한다. 어떻게 Bottom Up 방식을 적용할 것인지 생각해야한다. 예시 케이스인 n = 3 / {1, 2, 5}, k = 5일때의 규칙을 찾아 보자면 1 2 3 4 5 6 7 8 9 10 1가지 { 1 } 1 1 1 1 1 1 1 1 1 1 2가지 { 1, 2 } 1 2 2 3 3 4 4 5 5 6 3가지 {..

[C++] 백준 1654번 랜선 자르기

이분 탐색 문제. 이분 탐색 문제이고 실버3 문제임에도 고려해줄 사항이 생각보다 많아서 반례를 한번 찾아보고 풀었다. 처음 문제를 봤을 때 처음에는 우선순위 큐로 만들어서 긴 랜선들을 자르는 식으로 구현해보려고 했다. 그런데 문제 아래에 힌트를 보면 이렇게 나와있었고, 결국 우선순위 큐를 이용하는 그리디 방식의 풀이는 틀렸다는 것을 알게됐다. 랜선 자르기 같은 문제를 예전에 풀었던 적이 있었는데, 이분 탐색으로 풀었던 기억이 있어서 이분탐색으로 시도했고, 몇번 구상해보니 확실히 이분탐색이라는 것을 알게됐다. 문제 풀이 문제가 이분탐색이라는 것을 알게되면 그 뒤로는 간단하다. 나같은 경우는 vector 배열에 담고, algorithm STL에 있는 sort 메서드를 사용해서 정렬해 준 후에 1 ~ [입력받..

[C++] 백준 11057번 오르막 수

다이나믹 프로그래밍 문제. 지난번에 풀었던 쉬운 계단 수 문제와 비슷한 문제였다. [C++] 백준 10844번 쉬운 계단 수 다이나믹 프로그래밍 문제. 생각보다 너무 어려워서 이틀동안 계속 머리에 담아두다가 구글링의 도움을 받고 풀었다. 접근 방법 먼저, N자리 수는 N이 1일때는 1~9 2일때는 다음과 같다. 맨 앞자리 kimyunseok.tistory.com 지난 번에 이 문제를 풀었을 땐 풀기 어려워서 못 풀었었는데 비슷한 이문제는 비교적 쉽게 풀어서 이 때 정리를 나름 잘 한것 같아서 뿌듯했다. 문제 접근 방식 처음에 문제를 보자마자 위에서 설명했듯 쉬운 계단수를 풀었던 기억이 떠올렸다. 다이나믹 프로그래밍이라고 바로 생각했고 마지막 수에 따라 자리수의 마지막 수 이전에 어떤 수가 올 수 있는지 ..

[C++] 백준 1541번 잃어버린 괄호

문자열을 파싱하는 문제. 식을 해석하는 문제는 나같은 경우는 큐 자료구조를 이용해서 많이 푼다. 문제 접근 방식 우선 어떻게 해야 식의 값이 최소가 되는지를 알아보려고 했다. 식에 더하기와 빼기밖에 없으므로, 어떤 경우로 식을 처리를 해야 최소값이 될 수 있을지 혼자 식을 따로 적어서 생각해 보았다. 일단 식의 계산을 맨 앞에 숫자부터 해야된다고 가정할때, 10+20-10-20+30-20 -> 10+20-10-(20+30)-20 다음 식 같은 경우를 만들어서 살펴보았는데 다음과 같은 두 가지 경우를 고려하게 되었다. +의 경우는 그냥 앞에서 계산한다. -의 경우, 바로 뒤의 식이 +이면 +를 먼저 계산한다 (즉, 괄호를 씌워준다.) / 아니라면 그냥 앞에서 계산한다. 이렇게 고려해줄 경우 식의 값이 최소..

[C++] 백준 1904번 01타일

다이나믹 프로그래밍 문제. 점화식이 바로 보여서 쉽게 풀 수 있지만 왜 그렇게 되는지도 생각해서 풀어보았다. 문제풀이 나는 위에 같은 경우로 경우의 수를 나누었다. 그림에 대한 설명을 하자면 N = 1, 1 -> 1개 N = 2, 00, 11 -> 2개 N = 3, 001, 100, 111 -> 3개 N = 4, 0000, 0011, 1001, 1100, 1111 -> 5개 N = 5, 00001, 00100, 10000, 00111, 10011, 11001, 11100, 11111 -> 8개 여기까지만 해도 An = A(n-1) + A(n-2)라는 결과를 얻을 수가 있다. 그러면 왜 그렇게 되는 것일까? An은 A(n-1)에서 한 자리가 추가되는 것이다. 한 자리가 추가되는 것은 무조건 타일 1이 추가..