본문 바로가기

알고리즘22

[JAVA] 기둥과 보 설치( 프로그래머스 kakao 2020 공채) 제약 사항이 너무 많다... 보자마자 빡시게 구현하겠구나 생각했다. 이런 문제 풀 때 가장 중요한 점은 잔머리 굴리면 안된다. 있는 그대로 모든 조건 활용해서 구현해야 한다.. 1) 격자 설정하기 (먼저 2차원 격자를 설정해서 문제를 풀어야 하는데 이 부분에서는 문제 내용을 어떻게 표시할지 본인만의 방법으로 생각해내야 한다.) n x n 격자지만 사실은 0을 포함하고 있기 때문에 길이는 n+1 이다. 기둥을 표시할 격자 gidung 과 보를 표시할 격자 boo 를 boolean 2차원 배열로 설정했다. 한편 문제에서 주어진 대로 (1,0) 이라는 좌표에 대해 생각해보자. (1,0) 을 좌표 그대로 생각하면 x좌표가 1 이며 y좌표가 0 인점이 떠오를 것이다. 하지만, 이를 2차원 컴퓨터 배열로 생각하면 .. 2020. 8. 21.
[JAVA] 메모리 사용량과 시간을 줄이는 간단한 아이디어 문제는 백준 2573번 문제로 진행했다. https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 � www.acmicpc.net 1. 문제 풀이 1) 2차원 배월의 모든 원소가 0인가? 그렇다면 6)으로 간다. 그게 아니라 하나라도 0보다 큰 수가 있다면 2)번으로간다. 2) answer 를 1증가 시킨다. 3) 2차원 배열을 1년이 지난 배열로 만든다. 4) bfs를 이용해 영역의 수를 카운트하고 2이상이면 ok에 표시하고 6)번으로 간다. 5) 2)반복한다. 6) ok가.. 2020. 8. 20.
[JAVA] 토마토 (백준 7569) 이 문제는 2차원이 아니라 3차원으로 bfs푸는 것이다. 또한 익기 시작하는 지점이 정해진 것도 아니며 여러개가 있을 수도 있고 없을 수도 있다. 관건은 모든 토마토가 익었는지 확인하는 것과 모두 익었다면 며칠이 걸리는지 구하는 것이 핵심이다. 본인이 접근한 방법대로 2층짜리 3x3 토마토상자가 있다고 가정하고 풀어보는 예시를 보자. 예) (z,x,y) 에서 z 는 높이이며 , x 는 가로, y는 세로다. x,y,z 모두 0부터 시작한다. 시작전 ( 0초 ) 큐에 남은 좌표 : (0,1,1) 1층 0 0 0 0 1 0 0 0 0 2층 0 0 0 0 0 0 0 0 0 1초후 큐에 남은 좌표: (0,0,1) , (0,1,0), (0,2,1) , (0,1,2) 1층 0 2 0 2 1 2 0 2 0 2층 0 0.. 2020. 8. 15.
[JAVA] 촌수 계산 (백준 2644) dfs,bfs 문제가 제일 재밌는거 같다. 출발지와 목적지를 정하고 가는 데 몇군데를 거치느냐를 따지면 된다. 예를 들어, 7번 목적지에서 3번으로 갈려면? 최소 3번만에 갈 수있다. dfs로 위의 로직을 구현한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main{ static int n; static int st,ed; static int answer=-1; public static void main(String[] args) throws IOException{ FastScanner fs = new FastScanner.. 2020. 8. 14.
[JAVA] 맥주 마시면서 걸어가기 (백준 9205) 풀이) 맥주는 20병 들고 있고 50미터마다 1병씩 소모된다면 한번에 이동할 수 있는 최대 거리는 1000이다. 그래서 거리가 1000이하인 노드들을 모두 방문해 보면서 그곳이 도착지점인지만 확인하면 된다. 위와 같이 지도가 있을 때 1000 보다 큰 간선은 제거해준다. 그러면 이제 bfs로 탐색해서 도착지에 도착할 수있는지 점검하면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main{ static int testCase,storeCnt; static Pos[] posList; public static void mai.. 2020. 8. 13.
[JAVA] 괄호 추가하기 (백준 16637) 아직까지 문자하나하나 다루는 거랑 알고리즘 할때, 컬렉션을 다루는 스킬이 많이 부족함을 느낀다. 매일 하나씩 풀다보면 적응 되겠지... dfs로 간단하게 풀수있다. a + b - c 가 있다면 1) a+b 하고 넘기기 2) a+ (b-c) 하고 넘기기 그림으로 설명하면 아래와 같다. import java.io.*; import java.util.*; public class Main { static int n; static int answer = -(int)Math.pow(2,31); static ArrayList nums = new ArrayList(); static ArrayList ops = new ArrayList(); public static int cal(int a,int b,char op){ .. 2020. 8. 10.
[PYTHON] 삼성 기출 풀이 모음 & 역량테스트 합격 후기 https://github.com/hangeulisbest/samsung_algorithm hangeulisbest/samsung_algorithm 삼성 기출 알고리즘 파이썬 풀이 모음. Contribute to hangeulisbest/samsung_algorithm development by creating an account on GitHub. github.com 위 문제를 모두 풀어보고 삼성 SW역량테스트를 통과하였다. 29문제 정도 풀면서 느낀점은 문제 대부분이 구현문제라서 대비하면서 구현실력이 증가한거 같다. 디피문제처럼 아이디어를 요구하는 문제는 나오지 않는것 같다. 또한 시뮬레이션 문제가 많아서 bfs,dfs 문제를 연습하기가 좋다. 2020. 8. 9.
[JAVA / PYTHON] 연구소 3 (백준 17142) - 삼성기출 자바로 bfs,dfs 문제를 풀어본적이 없어서 간단한 bfs 문제를 풀어보려고 시도했다. 이전에 삼성 sw 역량테스트를 준비하면서 파이썬으로 쉽게 풀었지만 이제는 자바에 익숙해 지고 싶어서 자바로 풀어보았다. 자바로 풀면서 놀랐던것은 왜 순열과 조합과 관련한 라이브러리가 없는 걸까... 물론 분명히 있을거 같은데 본인이 못찾는 것일 수도 있다. 귀찮지만 직접 조합을 구현했다. 조합은 dfs로 구현하였다. 문제를 푸는 알고리즘은 그림으로 표현하겠다. 위와 같은 연구소 배열이 있다고 하자. 값이 2인것은 바이러스가 놓일 수 있는 위치다. 바이러스가 놓인 위치가 아니다. 이 중에서 2개를 활성화 한다고 하면 활성화 한곳은 0 으로 바꾸고 visited 에서 해당위치에 1로 바꿔준다. 또한 비활성화한 곳은 -1.. 2020. 8. 1.
[JAVA] 괄호변환 (kakao 2020) 위 문제는 알고리즘을 다 제공하였다. 그대로 구현만 하면 되는 아주 심플한 문제다. 여기서 String 을 자바로 어떻게 다룰 것인지가 문제인데 예를 들어 String p = "maple Story" 라는 String 이 있을 때, 각각의 char에 접근하는 방법은 몇가지 있는데 1. charAt으로 접근하는 방법 for(int i=0;i 2020. 7. 31.

티스토리툴바