문제 링크 https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 문제 풀이 우선 간단하게 생각하면, 방에 도착하고, 해당 방 내에 있는 스위치를 통해 가능한 모든 방의 불을 키면서 나아가면 된다. 하지만, 아래와 같은 경우에 주의해야한다. Q)만약 bfs를 돌다가 불이 꺼진 방에 도착해서 그 지점의 탐색을 종료했는데, 이후에 불이 켜져서 도달 가능해진다면? 따라서, BFS를 통해 불이 켜진 방을 ..
문제 링크 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 문제 풀이 외부와 2개의 면이 맞닿아 있는 치즈를 매 턴 제거하는 문제이다. 만약 '외부' 지점을 알 수 있다면, 모든 '외부' 지점을 탐색하며 자신의 상,하,좌,우 에 치즈가 있을 경우, 표시를 하여 2번의 표시가 담긴 치즈 블럭이 존재한다면, 2개의 면이 외부에 노출된 것으로 보고 제거하면 된다. 그렇다면 '외부' 지점을 어떻게 알 수 있을까? 이 문제에서 '모눈종이의 ..
문제 링크 https://www.acmicpc.net/problem/17182 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위 www.acmicpc.net 문제 풀이 문제를 유심히 읽어야한다. K 번행성에서 시작해서 모든 행성을 거치는 최단경로를 찾는 것이다. 하지만 주의할 점이 a->b에 경로가 잇더라도, a->c->b와 같이 다른 곳을 거치는 것이 더 빠른 경로일 수 도 있다는 것이다. 따라서 각 정점들간의 최단 거리를 플로이드 와샬을 통해 구하는 것으로 '실제 각 정점간 최단거리' 를 찾은 뒤, 정점 방문 순서의 모든 경우의 수..
17780번 문제 링크 https://www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 문제 풀이 우선, 말이 합쳐진 이후에는 가장 위, 가장 아래 2개의 말만 저장하면 된다. ( 가운데의 말은 아무리 위아래를 바꾸더라도 맨 아래에 와서 움직임에 관여 불가 ) 따라서 각 말이 합쳐질 때마다, 적절한 top&bottom을 유지시킨뒤 움직임을 지시했다. 처음에는 queue를 통한 bfs 탐색으로 수행하고, 말이 합쳐질 경우, queue에 추가하지 않아 분기점을 합..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42895 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제해설 입력으로 N=3 이 주어지면, 사용할 수 있는 숫자는 3,33,333,.....,333333333( 최대 9개의 N사용 가능 ) 이다. 이 숫자들을 통해 사칙연산을 일정 횟수 수행하여 만들어지는 수들을 set에 저장해나간다. 여기서 "몇개의 N" 을 사용해서 구해지는지를 알아야 최소 값을 찾을 수 있기에, "몇개의 N으로 만들어진 수인가?" 에 대해서도 구해야한다. 처음에는 d..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/12952# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제풀이 이 문제는 dfs를 통한 완전탐색 과정에서, 백트래킹으로, 불가능한 트리의 가지를 가지치기 하여 수행 시간을 감소시켜야만 시간초과가 발생하지 않는다. 나는 이를 위해, 퀸이 8방향 모든 칸으로 이동하는 특성 중 좌, 우 모두 이동 가능한 특성을 활용하여 각 dfs(depth) 에서, depth 번째 행에 퀸을 놓을 수 있는 위치를 찾는 것으로 문제를 해결했다. 퀸을 놓을 행은..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/84512 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해설 dfs의 특성을 활용하여 사전순으로 완전 탐색을 진행할 수 있다. 따라서, 탐색 순서에 따라 진행하던 중, 찾고자하는 string이 나오면 해당 string의 순서를 리턴하면 된다. dfs를 통한 사전순 완전탐색으로 순서 계산 #include #include #include using namespace std; string words="AEIOU"; string ans_str..
** 시작하기에 앞서 이번 문제는 문제의 해결보단, Greedy로 오인한 저의 오답에 대한 Trouble Shooting에 가깝습니다. 조이스틱 https://school.programmers.co.kr/learn/courses/30/lessons/42860 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 위 문제에 대한 해설입니다. 우선, 각 문자(' A') 를 지정한 문자로 변환하는 것은 아스키 코드로 변환하면 쉽게 횟수를 찾을 수 있습니다. 저의 경우는 각 문자에 대해 일일이 아스키값을 구해서 계산한 뒤, 변환해야하는 횟수를 구했지만,단순히 [1,2,..
