supin2 [백준] 13414번 : 수강신청 문제 푼 날짜 : 2021-11-01 문제 링크 : 처음엔 입력값을 vector에 넣어주다가, find 함수를 이용하여 vector에 존재하는 값이 들어오면 기존의 값을 erase해주는 방식으로 구현했다. 하지만, 시간초과가 떴다. (웬만하면 find는 쓰면 안될 것 같다...) 모든 입력값을 vector에 넣어준 다음, vector의 마지막 값부터 탐색하며 set을 이용하여 이미 넣어준 값... 백준cppsupin2cpp [백준] 10819번 : 차이를 최대로 문제 푼 날짜 : 2021-09-18 문제 링크 : 간단한 백트래킹 문제였다. 순열을 구현하여 간단히 해결해줄 수 있었다. next_permutation을 이용해서도 구현해 보았다. 더 익숙해질 때까지... 백준supin2cppcpp [백준] 5567번 : 결혼식 문제 푼 날짜 : 2021-09-29 문제 링크 : bfs 또는 dfs로 풀 수 있는 문제였다. 상근이와 동기들의 관계를 인접리스트로 나타내었고, 상근이와 친구, 친구의 친구까지 초대하기 때문에 dfs로 그래프를 탐색하다가 깊이가 2일 때(상근이가 0, 상근이 친구가 1, 상근이 친구의 친구가 2) 가지치기를 해주었다. 최근에 bfs를 잘 안써서 그런지 문제를 보자마자 dfs가 먼저 떠올라서... 백준supin2cppcpp [백준] 2580번 : 스도쿠 문제 푼 날짜 : 2021-09-19 문제 링크 : 문제의 제한사항에 아래와 같이 아주 친절하게 백트래킹 알고리즘을 이용하는 문제라고 명시되어있다. 백트래킹 알고리즘으로 풀 수 있는 입력만 주어진다. 사실, 이 문제가 백트래킹으로 분류되어있어서 이미 알고는 있었지만, 모든 문제에 이런 제한사항이 있으면 얼마나 좋을까라는 생각을 잠시나마 해봤다.. 아무튼 스도쿠는 아주 유명한 게임이 때문에 규... 백준supin2cppcpp [백준] 16987번 : 계란으로 계란치기 문제 푼 날짜 : 2021-12-03 문제 링크 : 문제가 이해가 안돼서 푸는 데 좀 오래걸린 문제였다. 백트래킹을 이용하였고, 매개변수로 각 계란의 index값(코드 내의 idx 변수)을 넘겨주었다. 이 때, idx는 손에 쥔 계란의 index를 뜻하며, 마지막 계란을 쥐었을 때 깨진 계란의 개수를 세어주었다. 깰 계란이 없을 때 마지막 계란을 들게하는 것이 포인트였다.(라고 개인적으로 생... 백준supin2cppcpp [백준] 15651번 : N과 M (3) 문제 푼 날짜 : 2021-09-16 문제 링크 : 이번 문제는 문제에서 자기자신을 다시 선택할 수 있어야한다는 조건이 추가되었다. 그래서 에서 숫자를 선택했는지 여부를 나타내는 visited 배열과 이에 해당하는 로직을 삭제하였다. 이렇게 하면 매번 모든 숫자를 탐색할 수 있다. 설명을 좀 이해하기 힘들게 적은 것 같은데, 간단히 말해서 중복순열을 구해준 것이다. 백트래킹에 대한 개념이 점... 백준supin2cppcpp [백준] 17090번 : 미로 탈출하기 문제 푼 날짜 : 2021-10-01 문제 링크 : DP와 DFS를 이용한 그래프 탐색문제이다. 문제에 입력으로 주어진 미로의 모든 위치에서 출발하여 탈출이 가능한지 DFS로 탐색해주었다. 탐색하면서 중요한건 메모이제이션을 활용하는 것이다. 이를 위해 dp 배열을 선언하였고, dp배열이 의미하는 것은 해당 인덱스에서 출발하였을 때 미로를 탈출할 수 있는지이다. (dp[x][y] = 1 일 때... 백준supin2cppcpp [백준] 12847번 : 꿀 아르바이트 문제 푼 날짜 : 2021-10-06 문제 링크 : 슬라이딩 윈도우 알고리즘을 이용하는 문제였다. 코드는 아래의 생각대로 구현하였다. 문제에 주어진 최대 크기의 배열을 선언하고, 입력에 주어진 일급을 순서대로 넣어준다. 준수는 m일 연속으로 일을 해야 하므로 1일부터 일급을 더해준다. 최대 m일 더해줬다면, m일을 초과하는 인덱스부터는 가장 낮은 인덱스의 일급을 빼주고 다음 위치의 일급을 더... 백준supin2cppcpp [백준] 1238번 : 파티 문제 푼 날짜 : 2021-07-07 문제 링크 : 다익스트라를 이용하여 파티가 열리는 X 까지 최단거리를 구하고, 다시 X에서 각자 집까지 돌아오는 최단거리를 구하여 그 두 값의 합이 가장 큰 값을 출력해주었다. 다익스트라 알고리즘에 점점 익숙해져가는 것 같다. 더 심화된 문제를 풀어봐야겠다.... 백준supin2cppcpp [백준] 1916번 : 최소비용 구하기 문제 푼 날짜 : 2021-07-04 문제 링크 : 최단경로 문제 중 다익스트라 알고리즘을 이용하여 풀 수 있는 기본적인 문제이다. 1753번 [최단경로] 문제와 동일하게 구현하였고, 문제에서 주어진 출발 도시(코드 내의 start 변수)에서 다른 도시까지의 최단거리를 구한 다음 도착 도시(코드 내의 end 변수)까지의 최단 거리 값을 출력해주었다. 다익스트라 알고리즘의 기본문제를 풀면서 알... supin2cpp백준cpp [백준] 4485번 : 녹색 옷 입은 애가 젤다지? 문제 푼 날짜 : 2021-07-07 문제 링크 : 이전에 풀어본 다익스트라 문제와 달리 배열을 통해 경로를 탐색하며 다익스트라 알고리즘을 적용시켜야 했다. 구현하는데 있어서 크게 다른 점은 없고, BFS를 이용한 문제를 풀때처럼 상하좌우로 배열을 움직일 때 조건을 체크하는 부분이 추가되었다. 최단경로를 저장하는 배열 또한 2차원으로 지정해 주었고, 방문표시를 위한 배열도 선언해주었다. 문제... supin2백준cppcpp [백준] 10025번 : 게으른 백곰 문제 푼 날짜 : 2021-10-06 문제 링크 : 슬라이딩 윈도우 알고리즘을 이용하는 문제였다. 코드는 아래의 생각대로 구현하였다. 문제에 주어진 최대 크기의 배열을 선언하고, 얼음이 있는 위치에 입력값을 넣어준다. 백곰 앨버트는 자리잡은 곳에서 좌우로 K씩 먹는다고 하였으니, 최초 2*K 만큼 커버할 수 있다. 처음부터 배열의 값들을 더해주다가, 2*K + 1 부터 인덱스가 가장 낮은 위... 백준supin2cppcpp
[백준] 13414번 : 수강신청 문제 푼 날짜 : 2021-11-01 문제 링크 : 처음엔 입력값을 vector에 넣어주다가, find 함수를 이용하여 vector에 존재하는 값이 들어오면 기존의 값을 erase해주는 방식으로 구현했다. 하지만, 시간초과가 떴다. (웬만하면 find는 쓰면 안될 것 같다...) 모든 입력값을 vector에 넣어준 다음, vector의 마지막 값부터 탐색하며 set을 이용하여 이미 넣어준 값... 백준cppsupin2cpp [백준] 10819번 : 차이를 최대로 문제 푼 날짜 : 2021-09-18 문제 링크 : 간단한 백트래킹 문제였다. 순열을 구현하여 간단히 해결해줄 수 있었다. next_permutation을 이용해서도 구현해 보았다. 더 익숙해질 때까지... 백준supin2cppcpp [백준] 5567번 : 결혼식 문제 푼 날짜 : 2021-09-29 문제 링크 : bfs 또는 dfs로 풀 수 있는 문제였다. 상근이와 동기들의 관계를 인접리스트로 나타내었고, 상근이와 친구, 친구의 친구까지 초대하기 때문에 dfs로 그래프를 탐색하다가 깊이가 2일 때(상근이가 0, 상근이 친구가 1, 상근이 친구의 친구가 2) 가지치기를 해주었다. 최근에 bfs를 잘 안써서 그런지 문제를 보자마자 dfs가 먼저 떠올라서... 백준supin2cppcpp [백준] 2580번 : 스도쿠 문제 푼 날짜 : 2021-09-19 문제 링크 : 문제의 제한사항에 아래와 같이 아주 친절하게 백트래킹 알고리즘을 이용하는 문제라고 명시되어있다. 백트래킹 알고리즘으로 풀 수 있는 입력만 주어진다. 사실, 이 문제가 백트래킹으로 분류되어있어서 이미 알고는 있었지만, 모든 문제에 이런 제한사항이 있으면 얼마나 좋을까라는 생각을 잠시나마 해봤다.. 아무튼 스도쿠는 아주 유명한 게임이 때문에 규... 백준supin2cppcpp [백준] 16987번 : 계란으로 계란치기 문제 푼 날짜 : 2021-12-03 문제 링크 : 문제가 이해가 안돼서 푸는 데 좀 오래걸린 문제였다. 백트래킹을 이용하였고, 매개변수로 각 계란의 index값(코드 내의 idx 변수)을 넘겨주었다. 이 때, idx는 손에 쥔 계란의 index를 뜻하며, 마지막 계란을 쥐었을 때 깨진 계란의 개수를 세어주었다. 깰 계란이 없을 때 마지막 계란을 들게하는 것이 포인트였다.(라고 개인적으로 생... 백준supin2cppcpp [백준] 15651번 : N과 M (3) 문제 푼 날짜 : 2021-09-16 문제 링크 : 이번 문제는 문제에서 자기자신을 다시 선택할 수 있어야한다는 조건이 추가되었다. 그래서 에서 숫자를 선택했는지 여부를 나타내는 visited 배열과 이에 해당하는 로직을 삭제하였다. 이렇게 하면 매번 모든 숫자를 탐색할 수 있다. 설명을 좀 이해하기 힘들게 적은 것 같은데, 간단히 말해서 중복순열을 구해준 것이다. 백트래킹에 대한 개념이 점... 백준supin2cppcpp [백준] 17090번 : 미로 탈출하기 문제 푼 날짜 : 2021-10-01 문제 링크 : DP와 DFS를 이용한 그래프 탐색문제이다. 문제에 입력으로 주어진 미로의 모든 위치에서 출발하여 탈출이 가능한지 DFS로 탐색해주었다. 탐색하면서 중요한건 메모이제이션을 활용하는 것이다. 이를 위해 dp 배열을 선언하였고, dp배열이 의미하는 것은 해당 인덱스에서 출발하였을 때 미로를 탈출할 수 있는지이다. (dp[x][y] = 1 일 때... 백준supin2cppcpp [백준] 12847번 : 꿀 아르바이트 문제 푼 날짜 : 2021-10-06 문제 링크 : 슬라이딩 윈도우 알고리즘을 이용하는 문제였다. 코드는 아래의 생각대로 구현하였다. 문제에 주어진 최대 크기의 배열을 선언하고, 입력에 주어진 일급을 순서대로 넣어준다. 준수는 m일 연속으로 일을 해야 하므로 1일부터 일급을 더해준다. 최대 m일 더해줬다면, m일을 초과하는 인덱스부터는 가장 낮은 인덱스의 일급을 빼주고 다음 위치의 일급을 더... 백준supin2cppcpp [백준] 1238번 : 파티 문제 푼 날짜 : 2021-07-07 문제 링크 : 다익스트라를 이용하여 파티가 열리는 X 까지 최단거리를 구하고, 다시 X에서 각자 집까지 돌아오는 최단거리를 구하여 그 두 값의 합이 가장 큰 값을 출력해주었다. 다익스트라 알고리즘에 점점 익숙해져가는 것 같다. 더 심화된 문제를 풀어봐야겠다.... 백준supin2cppcpp [백준] 1916번 : 최소비용 구하기 문제 푼 날짜 : 2021-07-04 문제 링크 : 최단경로 문제 중 다익스트라 알고리즘을 이용하여 풀 수 있는 기본적인 문제이다. 1753번 [최단경로] 문제와 동일하게 구현하였고, 문제에서 주어진 출발 도시(코드 내의 start 변수)에서 다른 도시까지의 최단거리를 구한 다음 도착 도시(코드 내의 end 변수)까지의 최단 거리 값을 출력해주었다. 다익스트라 알고리즘의 기본문제를 풀면서 알... supin2cpp백준cpp [백준] 4485번 : 녹색 옷 입은 애가 젤다지? 문제 푼 날짜 : 2021-07-07 문제 링크 : 이전에 풀어본 다익스트라 문제와 달리 배열을 통해 경로를 탐색하며 다익스트라 알고리즘을 적용시켜야 했다. 구현하는데 있어서 크게 다른 점은 없고, BFS를 이용한 문제를 풀때처럼 상하좌우로 배열을 움직일 때 조건을 체크하는 부분이 추가되었다. 최단경로를 저장하는 배열 또한 2차원으로 지정해 주었고, 방문표시를 위한 배열도 선언해주었다. 문제... supin2백준cppcpp [백준] 10025번 : 게으른 백곰 문제 푼 날짜 : 2021-10-06 문제 링크 : 슬라이딩 윈도우 알고리즘을 이용하는 문제였다. 코드는 아래의 생각대로 구현하였다. 문제에 주어진 최대 크기의 배열을 선언하고, 얼음이 있는 위치에 입력값을 넣어준다. 백곰 앨버트는 자리잡은 곳에서 좌우로 K씩 먹는다고 하였으니, 최초 2*K 만큼 커버할 수 있다. 처음부터 배열의 값들을 더해주다가, 2*K + 1 부터 인덱스가 가장 낮은 위... 백준supin2cppcpp