백준 9633 알고리즘 연습해당 문제는 백트래킹을 사용하여 푸는 문제다.가능한 모든 경로를 찾아봐야하지만 일반적인 dfs로 푼다면 시간초과가 되기 때문에중간 중간 확인을 하면서 문제와 맞지 않는 경우들은 모든 경로를 찾을 때 포함되지 않도록 하는 것이다.백트래킹을 사용
백준 2178번 연습각 4방향으로 갈 수 있다고 가정한 상태로 bfs를 통한 완전탐색으로 문제를 풀이했습니다. 탐색과정에서 이미 들렀던 곳은 다시 방문하는 일을 방지 했으며, 마지막 도착지점에 도착시에 가장 작은 값이 출력될 수 있도록 코드를 짰습니다.시간 복잡도에서
백준 1149 RGB거리 dp 알고리즘을 활용한 풀이법해당 문제는 dp 알고리즘을 활용하여서 계산의 반복을 줄이면서 최소값을 찾는 문제이다. 처음에는 완전탐색을 이용해서 풀으려고 했지만 시간복잡도가 너무 많아질 것 같아서 포기했다. 그래서 백트래킹 알고리즘도 생각은 해
백준 14502 연구소 문제를 풀어보았습니다.언어는 python입니다.우선 combinations 을 통해서 벽을 3개 세울 수 있는 모든 경우의 수를 구한 다음 반복문을 통해서 미리 벽을 세우고 bfs로 바이러스들이 전부다 퍼져나갔을 때 추가된 바이러스의 개수를 구합
백준 1987 알파벳 문제를 풀어봅시다!파이썬 코드이 문제가 복잡하다고는 느끼지 않지만 시간초과에 걸리지 않게 하기 위해 많이 노력을 했습니다.. 제가 생각한 알고리즘내에서는 일반적으로 알고리즘만 짜면 시간초과가 계속 나더라고요.. 그래서 구글링을 하던 도중파이썬의 모
백준 1753번 최단경로 문제를 풀어보겠습니다.파이썬!이 문제는 경로마다 cost가 존재하고 cost를 최소화하는 경로를 찾는 문제입니다.이렇게 경로가 있고 경로에 cost가 있다면 다익스트라 알고리즘 혹은 플루이드 워셜 알고리즘을 이용하죠!!이 문제는 최종적으로 st
백준 9261번 LCS 문제입니다.https://www.acmicpc.net/problem/9251파이썬 풀이LCS 알고리즘 & 다이나믹 프로그래밍이 문제는 LCS 알고리즘을 활용하여 푸는 문제이다. LCS는 다이나믹 프로그래밍 알고리즘으로부터 기인하는데 중간
백준 14503번 로봇청소기https://www.acmicpc.net/problem/14503PYTHON이번 문제는 주어진 규칙이 있는 로봇청소기를 구현하는 문제였습니다. 코드의 길이와 깔끔함에 있어서는 다양하게 차이가 나겠지만 구현하는 일은 조건을 상세하게
백준 1759번 암호만들기를 풀어보겠습니다.https://www.acmicpc.net/problem/1759파이썬 코드조건 & 구현암호는 3글자 이상이다.암호는 모음 1개, 자음 2개 이상을 꼭 포함해야한다.가능한 암호는 알파벳 순서대로 구성되어야 한다.가능한
백준 2206번 벽 부수기 문제입니다.https://www.acmicpc.net/problem/2206파이썬생각보다 까다로웠습니다. 처음에는 벽이 있는 곳을 모두 리스트에 저장한 후 1개의 벽을 지우고 bfs를 통해서 가장 최소값을 찾는 방법을 했습니다. 그런
https://www.acmicpc.net/problem/2580스도쿠 문제는 구현하는 것은 어렵지 않다고 생각한다. 조건에 맞추어서 작성하면 되는데 시간초과가 나는게 문제라고 생각한다.이 문제 풀이는 dfs를 이용한 풀이로 다양한 경우의 수를 탐색하면서 스도
https://www.acmicpc.net/problem/14499이 문제는 주사위의 동서남북 방향에 대한 것만 헷갈리지 않으면 쉽게 풀 수 있습니다.주사위가 동서남북 방향에 따라서 굴려질때마다 방향 및 각각의 숫자가 바뀌기 때문에 주의해야합니다. 저는 주사위
https://www.acmicpc.net/problem/11054부분수열 문제에서 다이나믹프로그래밍을 사용하는 것이 아직 익숙하지 않다.고민했었던 풀이방법을 소개해보자면각 넘버 리스트에서 바이토닉 수열에서 가장 큰 값이 될 수 있는 값을 지정하고 전부 다 구
https://www.acmicpc.net/problem/14890이 문제는 구현에 중점을 둔 문제였던것 같습니다. 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.경사로를 놓을
https://www.acmicpc.net/problem/1005이 문제를 처음보고 생각났던 것은 다음과 같다.다익스트라?BFS? DFS?열심히 코드를 짜고 제출했으나 '틀렸습니다.'가 나왔다.반례를 생각해보니 건물이 지어지는 관계를 순서대로 주지 않는 경우가
출처 : https://www.acmicpc.net/problem/1238파티 문제는 cost에 따른 최단 거리를 구하는 문제이다. 따라서 다익스트라 알고리즘을 사용하여 문제를 해결했다.특이했던 점은 정해진 장소에 갔다가 다시 본인의 집으로 돌아와야 한다는 것
출처 : https://www.acmicpc.net/problem/1937처음에는 bfs를 이용하여 경로를 탐색하려고 했지만 최장 길이를 구하는 문제이기에 실패했습니다. visited라는 리스트를 두고 하더라도 bfs를 통한 탐색이 최장 생존 경로를 보장해주지
출처 : https://www.acmicpc.net/problem/1717저는 이 문제를 파이썬의 딕셔너리 자료형을 이용해서 풀었습니다.info_dic을 통해서 각 숫자가 들어가 있는 집합의 index를 저장set_dic을 통해서 각 set_dicindex의
출처 : https://www.acmicpc.net/problem/1197이 문제에서는 최소 신장 트리 알고리즘이 사용된다. 그중에서도 프림알고리즘을 활용하여 문제를 풀었다.프림 알고리즘을 전개할 때 우선순위 큐를 활용하여 간선의 가중치의 최소를 선택할 수 있
출처: https://www.acmicpc.net/problem/1520완전탐색만 이용해서 풀기에는 시간복잡도가 너무큽니다.. 지수로 커지기에..그리하여 dfs로 우선 되는 경로를 찾고 dp를 활용해서 값들을 저장하기로 했습니다.dfs를 통해서 되는 경로를 한
문제 : https://www.acmicpc.net/problem/16236아기상어가 식성이 좀 까다롭습니다.다음 조건을 이용하여 문제를 풀어야합니다.거리가 가장 가깝고, 거리가 같다면 가장 위쪽, 왼쪽에 있는 것을 먹습니다.자신보다 작은 물고기만 먹을 수 있
문제: https://www.acmicpc.net/problem/2252줄 세우는 알고리즘은 줄을 잘 세우다가도 root의 순서가 바뀌어버리면 밑에 따라오던 자식 노드들까지 순서가 바뀌는 경우가 생긴다.따라서 일반적인 리스트를 따라서 문제를 적용하기 보다는 그
문제 : https://www.acmicpc.net/problem/14500이 문제는 각 모양의 회전과 대칭을 모두 고려하여 최종합의 최댓값을 측정해야합니다.그렇기에 각 모양의 대한 회전 및 대칭을 모두 구현을 해야합니다. 저 같은 경우에는 각 경우를 모양으로
문제 : https://www.acmicpc.net/problem/2667아파트의 정보가 담긴 배열을 입력을 통해서 받는다. 그 이후에는 bfs 알고리즘을 활용하여 탐색을 해주면 된다.이때 아파트끼리 상하좌우로 움직여서 갈 수 있다면 이웃이며 하나의 단지로 명
문제 바로가기파일 합치는 문제는 각각 주어진 데이터를 '어떠한 형태로 쪼개는가'가 중요한 문제이다.각각의 데이터를 받았을 때 재귀함수를 통해서 각각의 쪼개는 방식에 따라서 전부 구해보고 그중에서 최솟값을 선택하도록 알고리즘을 구성했다.하지만 바로.. 시간초과사실 쪼개는
문제 바로가기이 문제는 각 구역에서 다른 구역으로 가는 최단 거리를 구하는 것입니다.해결하기 위해서는 각 구역끼리 서로 구분할 수 있어야합니다.Board 배열을 만들고 각 구역별로 넘버링을 다르게 붙였습니다.완전 탐색을 통해서 각 출발지로부터 다른 구역까지의 거리를 모
문제 바로가기처음에는 최소거리에 사용될 치킨집을 먼저고르는 작업을 했었습니다.따라서 각 치킨집의 좌표를 구하고 반복문을 통해서 집에서 각 치킨집까지의 거리의 누적합을 구하고 우선순위 큐를 활용하여 가장 적은 거리를 가진 치킨집만 활용하도록 했습니다.그러나..누적합으로
백준 10026번 적록색약 문제 바로가기 코드 문제 해결 반복적인 코드를 피하기 이 문제는 주어진 color의 배열을 통해서 각 구역을 나누는 문제라고 할 수 있습니다. 이때 적록색약인 사람은 R, G를 구분 못하고 같은 것이라 생각하며 일반 사람들은 R,
문제 바로가기palindrome : 회문 또는 팰린드롬은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열 등이다. 보통 낱말 사이에 있는 띄어쓰기나 문장 부호는 무시한다.주어진 질문에 따라서 각각 대답을 모두 해주면 된다. 이때 질문에 들어온 것을
문제 바로가기이 문제는 트리가 주어지고 각 트리를 연결하는 간선의 가중치가 있는 모습이다.여기서 한 노드에서 다른 노드까지(거쳐가도 된다) 최대 가중치의 합을 구하는 문제이다.처음에는 이 문제를 DFS 탐색을 통해서 해결하려고 했다. 주어진 트리의 모든 노드에서 출발하