본문 바로가기
반응형

Algorithm66

[백준/1918] 후위표기식 ( java ) www.acmicpc.net/problem/1918 어떤 표기식보다 후위표기식을 그나마 가장 안다고 생각했는데 알고보니 제대로 안 것이 아니였다. ;; 연산자 우선순위에 따라서 결과값이 바뀌는 것인데, 제대로 고려하지 못했다. 따라서 연산자 우선순위를 고려하여서 수정하였다. 먼저 괄호가 있는 경우와 없는 경우로 나누어야 한다. 괄호가 있는 경우는 쉽다. 괄호가 끝나면 연사자를 stack으로 출력하면 된다. 왜냐하면 괄호는 하나의 연산단위로 계속 묶어주기 때문이다. 하지만 괄호가 없는 경우를 고려해야 한다. 이때 연산자 우선순위를 따져준다. 핵심은, 연산자를 계속 stack에 저장하면서 이전 stack값과 비교하는데, 현재의 자신보다 이전 연산자 우선순위가 같거나 높으면 출력한다. 예를 들어 stack의 .. 2021. 1. 10.
Union-Find(유니온-파인드) 유니온-파인드는 disjoint sets라는 서로소 집합을 구하는 문제입니다. 서로소 집합이 용어는 어렵지만 공통 원소가 없는 집합들을 뜻합니다. 다음 그림을 보면 8개의 원소가 있고 서로소 집합은 3개입니다. 다음과 같은 유형에서 사용하면 됩니다. (물론 DFS/BFS로도 풀이가 가능합니다!) * 연결 정보가 주어졌을 때 2개의 원소는 서로 같은 집합에 속해 있는가? * 연결 정보가 주어졌을 때 독립적인 섬의 갯수는 몇개인가? Union-Find 관련 문제는 해당 원소들의 부모 정보들을 저장, 비교, 업데이트를 통해서 해결합니다. 따라서 각각 원소들의 부모 정보에 대해서 특별히 신경써주시면 됩니다. Union(결합시키다) : 해당 원소들의 parent를 비교하고 하나로 합칩니다. Find(찾다) : 해.. 2020. 11. 25.
1783 : 병든 나이트 ( 백준 / java ) www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net *해결 과정 이 문제는 이동 칸수가 특이합니다. 결론적으로 오른쪽으로만 이동하는 구조입니다. 이 구조를 이용해서 문제를 풀어야합니다. 배열은 최대 각 길이가 20억이 될 수 있기 떄문에 배열을 만들면 터지게 됩니다. 그래서 얼마나 많이 오른쪽으로 잘 이동할 수 있는지 확인합니다. N,M과의 관계를 천천히 살펴봅니다. n=1 : 이동 불가이므로 1을 반환 n=2 : 2,3만 이동 가능하므로 최대 4번 이동 가능 m 2020. 11. 10.
연습문제 : 최고의 집합 ( 프로그래머스 / java ) *해결 과정 처음에는 이 문제를 중복 조합으로 접근하였습니다. 혹시 문제가 해결되지 않은 상태에서 이 글을 보신다면 간단하게 접근하여 다시 생각히시기 바랍니다. 아래 간단한 테스트 케이스도 첨부합니다. 힌트는 최대한 공평하게 수를 분배하는 것입니다!! 저도 갈피를 잡지 못해 다른 글을 참고하였고 다시 풀어서 맞았습니다. 참고로 효율성도 요구하는 문제이기 때문에 O(N)시간에 처리가 가능해야 합니다. *테스트케이스 n = 3 / s = 8 / 답 [2,3,3] n = 3 / s = 7 / 답 [2,2,3] n = 4 / s = 14 / 답 [3,3,4,4] 나머지가 있는 경우, 없는 경우 등등 많은 경우들을 나누어서 풀어보았습니다. 그렇게 조건을 걸어서 풀었더니, 제대로 풀리지 않았고 재귀를 생각하였습니다.. 2020. 11. 10.
깊이/너비 우선 탐색(DFS/BFS) : 네트워크 ( 프로그래머스 / java ) programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr *해결 과정 해당 문제는 결론적으로 최적화된 풀이법은 union이라고 합니다. 하지만 저는 문제 유형처럼 DFS나 BFS를 활용하는 방법을 생각했습니다. 그렇게 BFS를 이용하기로 했습니다. 내가 임의로 시작한 0번 노드와 연결되어있는 노드들을 BFS로 쭉 검사하면 됩니다. BFS 함수 한번으로 해결하는 것이 아니라 일단 검사 자체는 주어진 n개를 모두 하는게 핵심입니다.. 2020. 11. 7.
깊이/너비 우선탐색(DFS / BFS) : 단어변환 ( 프로그래머스 / java ) programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr * 해결과정 프로그래머스 레벨별 풀이는 모두 유형을 제공하고 있습니다. 이미 힌트를 얻는다는 점에서 해결책을 떠올리는 과정은 성장할 수 없으나 연습하기는 좋습니다. 이 문제는 DFS, BFS 모두로 해결이 가능한 문제입니다. 그 중에 저는 DFS로 풀었습니다. DFS로 풀 때 항상 주의해야 할 것이 있습니다. 종료조건, 반복내용 + .. 2020. 11. 7.
10799 : 쇠막대기 ( 백준 / java ) www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net * 풀이 과정 이 문제는 괄호에 관한 문제이기 때문에 stack을 이용해야겠다는 생각을 했습니다. 그리고 막대를 자르는데, 계층마다 수가 늘어나기 때문에 '('가 증가할 때마다 변수를 같이 증가시켰습니다. 혹시 여러분 예시문제 2개가 제대로 맞지 않는다면 '()' '(())' '(()())' 와 같은 비슷하지만 간단한 케이스를 만들어보고 한번 테스트해보기 바랍니다. 테스트를 만들어서 반례를 찾는 것도 실력입니다. 가끔 너.. 2020. 11. 7.
4963 : 섬의 개수 ( 백준 / java ) www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net *해결 과정 BFS를 통해서 섬을 계속 확인하면서, visited를 이용해 섬을 방문했는지 안했는지 확인합니다. 특히, 상 하 좌 우 4방향을 살피는 것 뿐만 아니라 대각선도 포함하기 때문에 같이 세주어야 합니다. import java.util.*; public class Main { static int N; static int M; static int[][] array; static boolean[][].. 2020. 11. 7.
20 : Valid Parentheses ( leetcode / java ) * 해결 방법 마찬가지로 괄호는 stack에 관한 문제입니다. 단, 이 문제에서는 괄호 모양이 3개가 있습니다. 이 괄호모양이 유효한지 확인해야 합니다. 정상적인 괄호라면, ')' '}' ']'가 나올 때 stack.peek()이 해당 괄호와 맞는 모양이어야 한다는 것입니다. 따라서 그것을 체크해주면서 하나씩 풀이하면, O(N)에 확인이 가능합니다. import java.util.*; class Solution { public boolean isValid(String s) { Stack stack = new Stack(); for(int i=0;i 2020. 11. 3.
반응형

티스토리툴바