본문 바로가기

알고리즘

 (87)
프로그래머스, 섬 연결하기 프로그래머스, 섬 연결하기 🪴 문제 https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🪴풀이 모든 노드를 방문한다. 최소 비용으로 통행하고자 한다. 최소신장 트리 문제이다. 프림 알고리즘, 크루스칼 알고리즘 🪴프림 알고리즘 어떠한 노드에서 출발해도 상관없다. 왜냐하면, 결국 모든 노드를 이어줄 것이기 때문! 우선순위 큐 자료구조를 이용해 최소 비용으로 갈 수 있는 모든 간선 정보를 비교해 방문한 적 없는 노드를 방문한다. 노드 수 n개, 간선수 ..
백준, 효율적인 해킹 백준, 효율적인 해킹 🪴 문제 https://www.acmicpc.net/problem/1325
백준, 단지 번호 붙이기 백준, 단지 번호 붙이기 🪴 문제 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 🪴 분류 pass 🪴 풀이 기본적인 dfs 문제로 풀면 된다. 상하좌우 1이고 방문한적 없는 경우 방문해줘야 한다. 방문표시를 하지 않을 경우 카운트할때 문제가 생길 뿐 아니라, 무한재귀에 빠질 수 있으니 방문표시를 해줘야 한다! 붙일 번호를 매개변수로 같이 넣어주는게 핵심! 최대한 상수 설정, global 설정해서 풀었다. cnt 는 번호 붙일 번호이고, inne..
프로그래머스, 표현 가능한 이진 트리 프로그래머스, 표현 가능한 이진 트리 🪴 문제 https://school.programmers.co.kr/learn/courses/30/lessons/150367 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🪴 분류 accepted 🪴 풀이 10진수를 2진수로 바꾼뒤. 포화 이진 트리의 갯수만큼 맞춰 더미 노드를 채워줬다. 이진 트리의 레벨에 따른 포화 이진트리 갯수는 그림을 그리며 규칙을 찾았다. level1 : 노드 1개 level2 : 노드 3개 level3 : 노드 7개 level4 : 노드 15개 leveln : 노드 2의 n승 -1 개 그리고..
백준 17406 배열 돌리기 4 백준 17406 배열 돌리기 4 🪴 문제 https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 🪴 분류 accepted 3시간동안 풀었다. 2시간 반 코드 & 디버깅, 30분은 문제 잘못이해한거 고쳤다. 이 문제 반복 + 비슷한 유형 반복해 30분내로 풀 수 있도록 해야겠다! (비슷한 유형 문제로는 프로그래머스, 나선형 어쩌구.. 떠오른다.) 🪴 문제풀이 문제 대충 읽고 회전 연산 들어오는 순서대로 회전하고 행 최소값을..
백준, 사다리 조작(combinations 활용) 백준, 사다리 조작 combinations 활용 풀이 2023.10.13 - [알고리즘] - 백준, 사다리 조작 백트래킹 말고 조합 라이브러리 활용해서 풀어봤다. ❓ 풀이 사다리가 설치가 안된 모든 위치를 list에 저장 이중 1,2,3개의 조합을 뽑아 사다리를 설치 즉, 사다리를 설치할 수 있는 모든 조합에 사다리를 설치 후, 원하는 값 구할 수 있는지 확인 📜 제출 코드 C, M, R = map(int, input().split()) regions = [[False for _ in range(C+1)] for _ in range(R)] for _ in range(M): r, c = map(int, input().split()) regions[r-1][c] = True # 사다리 정보를 받고 도착지 r..
백준, 사다리 조작 백준, 사다리 조작 ❓문제https://www.acmicpc.net/problem/15684 15684번: 사다리 조작사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선www.acmicpc.net ✅ 분류 accepted ❓ 풀이사다리를 1개 설치할 경우, 모든 경우 탐색 사다리를 2개 설치할 경우, 모든 경우 탐색 사다리를 3개 설치할 경우, 모든 경우 탐색 만약, 사다리 3개 설치하고도 원하는 결과를 얻을 수 없는 경우 -1 return 현재 위치에서 사다리 설치가능하면 설치 원하는 값 얻을 수 없으면 설치를 취소하고 설치 가능한 다음 위치를 탐색해야 한다. 즉,..
프로그래머스, 여행경로 프로그래머스, 여행경로 ❓문제 https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ❓분류 accepted 개발자 친구의 도움을 받았다. 수많은 코드들을 봐도 이해가 안됐는데, 설명들으니 이해된다. 설명 들은 다음 날 스스로 풀어봤다! 시간이 지난 뒤 다시 풀어봐야 할 문제~ 모든 티켓을 사용해야 한다는 점이 문제의 풀이법을 생각하는데 핵심! ❓ 접근 방법 티켓의 사용여부를 체크해가며 모든 항공권을 사용하는 경로를 저장한다. 만약 해당 항공권을 사용..
백준, 뱀 백준, 뱀 ❓문제 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net ❓분류 : pass!!! 예전에 정답코드를 보고도 이해하지 못했던 문제였는데 스스로 풀어서 기쁘다! ❓ 풀이 이 문제의 핵심은 뱀의 길이를 늘렸다 줄였다 할 수 있다는 점이다. 가장 처음 발자취를 남긴 뱀의 위치(꼬리)를 없애줘야 하기 때문에 순서가 중요! 그리고 FIFO해줘야 하므로 QUEUE를 사용해야한다. 나는 추후 이동 방향을 결정하는 정보(3 L, 8 D)도 큐를 활용했다. 📜..
프로그래머스, 게임 맵 최단거리 프로그래머스, 게임 맵 최단거리 문제 https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분류 level2 accepted 풀이 최단거리 = BFS, 큐 활용 문제 ❌ 나의 풀이 def bfs(R, C, r,c, maps): dr = [-1,0,1,0] dc = [0,1,0,-1] queue = [(r, c, 1)] # row, cloumn, distance while queue: cur_r, cur_c, distance = queue.pop(0) ..

티스토리툴바