algorithm 썸네일형 리스트형 [리트코드(LeetCode)] 238. Product or Array Except Self - Python leetcode.com/problems/product-of-array-except-self/ Product of Array Except Self - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com - 를 학습하면서 수록된 코드를 참고하였습니다. - 풀이 문제 제약 상 나눗셈을 사용할 수 없게되어 있었다. 현재 index의 왼쪽 원소들의 곱과 오른쪽 원소들의 곱을 구해 두 값을 곱하는 방법을 이용하였다. 먼저 nums[i]의 왼쪽에 있는 값들의 곱을 output[i.. [리트코드(LeetCode)] 15. 3Sum - Python leetcode.com/problems/3sum/ 3Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com - 를 학습하면서 수록된 코드를 참고하였습니다. - 풀이 1. 부르트 포스로 계산 -> 타임아웃 발생 for문을 3번 사용해서 풀이하는 단순한 방법으로 O(n^3)의 시간복잡도를 가지는 방법이다. for 문을 들어가서 해당 인덱스가 가리키는 리스트의 값이 바로 이전 원소 값과 동일하다면 continue 시켜줘서 중복을 제거한다. 리트코드에서 이 방법은 타.. [리트코드(LeetCode)] 42. Trapping Rain Water - Python leetcode.com/problems/trapping-rain-water/ Trapping Rain Water - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com - 를 학습하면서 수록된 코드를 참고하였습니다. - 풀이 1. 투 포인터를 이용 두 개의 포인터가 각각 리스트의 좌, 우에서 시작한다. 현재 포인터가 가리키고 있는 인덱스를 left, right에 저장하고, 포인터가 지나왔던 자리 중 가장 높았던 값을 left_max, right_max에 저장한다. 두.. [백준 14466] 소가 길을 건너간 이유 6 (Java) 문제 링크 : www.acmicpc.net/problem/14466 14466번: 소가 길을 건너간 이유 6 첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. www.acmicpc.net 풀이 소의 위치를 시작점으로 하여 BFS를 통해 목초지를 탐색하되, 다리가 존재하는 경우는 탐색하지 않도록한다. 탐색이 끝나고 다른 소 위치에 대한 방문 여부를 체크하는데 이 때 방문이 되지 않은 경우는 다리를 지나지 않으면 만날 수 없다는 것을 의미하기 때문에 해당 경우를 모두 찾으면 된다. 2차원 int 배열 map은 BFS탐색을 할 목초지로 소 위치.. [백준 1800] 인터넷 설치 (Java) 문제 링크 : www.acmicpc.net/problem/1800 1800번: 인터넷 설치 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차 www.acmicpc.net 풀이 이분 탐색 + 다익스트라 응용 문제로 개인적으로 많이 어렵게 느껴졌던 문제였다. (나중에 다시 한 번 풀어볼만한 문제) 참고한 블로그에 설명이 잘 나와 참고하여 풀었다. [참고] - batory.tistory.com/371 - justicehui.github.io/usaco/2019/07/12/BOJ1800/ 코드 import java.io.Buffe.. [백준 16639] 괄호 추가하기 3 (Java) 문제 링크 : www.acmicpc.net/problem/16639 16639번: 괄호 추가하기 3 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 풀이 dfs로 완탐하는 방식으로 시도하다가 경우가 너무 많아서 자력으로 풀지 못했다. 다른 분의 블로그를 참고하여 해결할 수 있었다. DP 방식을 통해 풀이가 가능했는데, 2차원 배열을 생성하고 i번 째부터 j번 째 숫자들을 포함한 연산 결과들의 최솟값, 최댓값을 구했다. 최종적으로 최댓값을 구하는 것이지만, 연산 숫자가 음수 * 음수 인 경우 최댓값의 후보가 될 수 있기 때문.. [백준 17780] 새로운 게임 (Java) 문제 www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 풀이 크게 체스판에 대한 데이터, 체스말(Node)에 대한 데이터, 쌓여있는 체스말에 대한 데이터를 어떻게 저장할 것인지 고민했다. - 체스판에 대한 데이터(빨, 파, 흰)는 2차원 int 배열로 입력 받는 그대로 저장한다. - 체스말에 대한 데이터는 x, y좌표 값과 방향 값을 필드 데이터로 갖는 Node 객체를 생성해 ArrayList에 저장하였다. (방향 별 이동을 쉽게 하기 위해 dir_x, dir.. [백준 15591] MooTube (Silver) (Java) www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 풀이 그래프 문제라고 2차원 배열을 사용하면 시간 초과가 발생한다. 불필요한 연결을 탐색하기 때문에 ArrayList를 담는 배열을 만들어 입력 받은 연결만 탐색하도록 구현하였다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; impor.. 이전 1 2 3 4 ··· 6 다음
