Algorithm
Leetcode - Gas Station
Leetcode - Gas Station
2024.03.02Problem There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations. Given two integer arrays gas and cost, return the starting gas station's index if you ..
Leetcode86. partition list (kotlin)
Leetcode86. partition list (kotlin)
2023.04.22https://leetcode.com/problems/partition-list/ Partition List - LeetCode Can you solve this real interview question? Partition List - Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the no leetcode.com Given the head of a linked list and a value x, partition..
Leetcode79. Word Search (w. kotlin)
Leetcode79. Word Search (w. kotlin)
2023.04.16Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once. Example 1: val board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]] val word = "SEE" Output: true..
순열(Permutation) 구하기 with kotlin
순열(Permutation) 구하기 with kotlin
2022.11.261, 2, 3 이라는 배열이 주어졌을때 해당 element 에 대해서 permutation 을 구한다고 가정해봅시다. 경우의 수는 총 6 가지 입니다 6개의 경우의 수가 나온는 것을 증명 하려면 첫번째 자리수에 올수 있는 것들은 총 [1, 2, 3] 세가지 중 하나 입니다. 두번째 자리수에 올수 있는 것들은 첫번째 를 제외한 총 두가지 중 하나 입니다. 세번째 자리수에 올수 있는 것들은 첫번째 두번째를 제외한 총 한가지 입니다. 3 * 2 * 1 = 6 경우의 수를 구하는 대표적인 방법은 backtracking 입니다. 해당 Tree 를 코드로 구현해보면 다음과 같습니다. fun solution(nums: IntArray): Unit { val endpoint = nums.size val result =..
Leet code 3 — Longest Substring Without Repeating Characters
Leet code 3 — Longest Substring Without Repeating Characters
2022.10.01Given a string s, find the length of the longest substring without repeating characters. Example 1: Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. Example 2: Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1. Example 3: Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Notice that the ans..
합이 같은 부분집합(DFS : 아마존 인터뷰) - (golang)
합이 같은 부분집합(DFS : 아마존 인터뷰) - (golang)
2022.05.28문제 풀이 해당 문제는 subset(부분집합) 을 만들어서 전체 배열의 원소의 합을 2로 나누었을 때 부분집합 의 합과 똑같으면 YES 다르면 NO 를 출력 하는 방식으로 접근 해보았다. 먼저 부분집합을 만드는 방식에 있어서 해당 원소를 부분집합으로 포함 할지 안할지 이렇게 2진 트리로 재귀호출을 할수 있다. func SameSumSubSet(depth, sum int) { SameSumSubSet(depth+1, sum+array[depth]) SameSumSubSet(depth+1, sum) } depth 와 함께 sum 이라는 변수를 재귀호출 로 넘김으로써 depth 가 N 과 같아졌을때 총합 / 2 와 비교하기 위해서 사용한다. 첫번째 재귀 호출은 해당원소를 부분집합으로 사용하는 재귀호출이고 두번..
[백준] 9663번 : N-Queen - Golang
[백준] 9663번 : N-Queen - Golang
2022.05.22https://st-lab.tistory.com/118 [백준] 9663번 : N-Queen - JAVA [자바] www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하.. st-lab.tistory.com 해당 블로그를 참조하여 문제를 해결 하였습니다. 처음에는 2차원 배열을 사용하여 문제를 해결 하려고 하였는데 DFS 의 특성상 깊이를 행 for 문을 사용하여 열을 검사하는 방식으로 풀면 1차원 배열로도 해당 문제를 풀수 있엇습니다. package main import ( "bufio" "fmt" "math" ..
Easy - 9 . is palidrome (with golang)
Easy - 9 . is palidrome (with golang)
2022.04.21Given an integer x, return true if x is palindrome integer. An integer is a palindrome when it reads the same backward as forward. For example, 121 is a palindrome while 123 is not. Example 1: Input: x = 121 Output: true Explanation: 121 reads as 121 from left to right and from right to left. Example 2: Input: x = -121 Output: false Explanation: From left to right, it reads -121. From right to l..
백준 - 좌표정렬하기 11650번 (정렬) with golang
백준 - 좌표정렬하기 11650번 (정렬) with golang
2021.10.04좌표 정렬하기 1 초 256 MB 55178 26613 20212 48.139% 문제 2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. 출력 첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다. 예제 입력 1 5 3 -1 4 2 1 2 1 3 1 3 예제 출력 1 복사 1 -1 1 1 2 2 3 3 3 4 해결방법 package main import (..
백준 4948번: 베르트랑 공준 - golang
백준 4948번: 베르트랑 공준 - golang
2021.09.22베르트랑 공준 시간 제한메모리 제한제출정답맞은 사람정답 비율 1 초 256 MB 45249 18591 15172 41.757% 문제 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다. 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23) 자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 ..
로또의 최고 순위와 최저 순위 - programmers (golang)
로또의 최고 순위와 최저 순위 - programmers (golang)
2021.09.06문제 설명 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위당첨 내용 1 6개 번호가 모두 일치 2 5개 번호가 일치 3 4개 번호가 일치 4 3개 번호가 일치 5 2개 번호가 일치 6(낙첨) 그 외 로또를 구매한 민우는 당첨 번호 발표일을 학수고대하고 있었습니다. 하지만, 민우의 동생이 로또에 낙서를 하여, 일부 번호를 알아볼 수 없게 되었습니다. 당첨 번호 발표 후, 민우는 자신이 구매했던 로또로 당첨이 가능했던 최고 순위와 최저 순위를 알아보고 싶어 졌습니다. 알아볼 수 없는 번호를 0으로 표기하기로 하고, 민우가 구매한 로또 번호 6개가 44, 1, 0, 0, 31 25라고 가정해보겠습니다..
Go - 부분집합 (MS 인터뷰 문제: DFS 완전탐색)
Go - 부분집합 (MS 인터뷰 문제: DFS 완전탐색)
2021.09.05package main import "fmt" var n int var ch [11]int func solution(L int) { if L == n + 1 { for i := 1; i