173만명의 커뮤니티!! 함께 토론해봐요.
미해결
자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
안녕하세요 혼자 푸는 중에 주어진 테스트케이스는 통과했으나 오답이 나왔습니다. 질문에 들어와보니 테스트케이스가 여러개라는데 제 눈에는 문제에있는 한가지 테스트 케이스만 보여서요 다른 테스트 케이스는 어디서 볼 수 있나요?
미해결
자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 이런식으로 해도 괜찮을까요? function handleCheck(sH, tH) { for (const [key, value] of tH) { //sH에 tH에 있는 값이 없으면 false return if (!sH.has(key)) return false //값이 같지 않으면 false return if (value !== sH.get(key)) return false } return true } function solution(s, t) { let answer = 0; let tH = new Map(); let sH = new Map(); //t for (const x of t) { if (tH.has(x)) tH.set(x, tH.get(x) + 1); else tH.set(x, 1) } //s 윈도우 생성 for (let i = 0; i < t.length - 1; i++) { if (sH.has(s[i])) sH.set(s[i], sH.get(s[i]) + 1); else sH.set(s[i], 1) } for (let i = sH.size; i < s.length; i++) { //윈도우에 추가 if (sH.has(s[i])) sH.set(s[i], sH.get(s[i]) + 1); else sH.set(s[i], 1) //비교, sH랑 tH 사이즈 체크 if (sH.size === tH.size) { //비교, sH랑 tH 값이 맞는지 체크 > 맞으면 카운트+ if (handleCheck(sH, tH)) answer++ } //sH 앞에 값 빼기 //sH 맨 앞 = s에서 현재 index+1 - tH사이즈 let idx = i + 1 - tH.size; //앞에 값 빼기 sH.set(s[idx], sH.get(s[idx]) - 1) //뺀 값이 0이면 삭제 sH.get(s[idx]) === 0 && sH.delete(s[idx]) console.log('----------------------') } return answer; } let a = "bacaAacba"; let b = "abc"; console.log(solution(a, b));
미해결
Do it! 알고리즘 코딩테스트 with C++
퀵정렬 14:38에 32랑 15를 swap 한다고 하셨는데 그 이유를 모르겠어요. 첫번째 정렬에서는 start와 end가 만난 15가 45와 비교해서 45가 더 크기 때문에 15의 오른쪽으로 이동한다는건 알겠는데, 두번째도 똑같이 적용하면 [5, 15, 32, 24, 42]가 아닌가요??
해결됨
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
커뮤니티에 저와 비슷한 고민을 하신 분이 계셨습니다만 아직 답변이 안 달려 있어 질문 드립니다. https://www.acmicpc.net/source/share/d1985da707194375bba36ee00db6226e 왜 틀린건지 잘 모르겠습니다. ㅠㅠ
해결됨
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
안녕하세요 선생님! 강의 항상 잘 듣고 있습니다. 다름이 아니라 선생님 답안을 참고하여 코드를 작성하고 제출하였는데 4%에서 틀리게되어 고치고 다시 제출하였더니 맞았지만 어느부분이 왜 틀렸는지 잘 모르겠습니다... 제가 의심가는 부분은 최대 component 숫자를 업데이트하는 부분(ret2)인데 고치기 전 코드와 고치기 후 코드가 저에겐 같아보여서요. 참고로 틀린 코드 내에 ret1과 id의 역할은 거의 같습니다. (맞은 코드에서 하나로 고침) 한번 봐주시고 왜 틀렸는지 알려주시면 감사하겠습니다 (_ _) 틀린 코드 - http://boj.kr/cb8d5a12b7d049788680dc1601edd57b 맞은 코드 - http://boj.kr/d5a147432b404ec4b3a73ab3f2dbda25
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
안녕하세요 예제는 잘 통과하는데 제출하면 틀렸다고 나오는데 반례를 못찾겠어요ㅠㅠ아래는 모음과 자음이 3번연속으로 반복되는지 확인하기 위한 코드인데 맞는지 의심이 됩니다! if (isVowel(s[i - 1]) == isVowel(s[i])) { cnt++; } else { cnt = 1; } http://boj.kr/5dd372c77cac4654bd661ebeb5d37f34
미해결
파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
안녕하세요 초급 코딩테스트 강좌 너무 잘 보았습니다. 반복해서 복습하니 이해가 너무 잘되고 코드가 잘짜지더라구요!! 최고입니다!! 혹시 이번 강좌의 정답 코드도 따로 모여있는 파일이나 깃헙 레포지토리가 있을까요 ?!
미해결
코딩테스트 실전 모의고사(with C++) : 대기업 대비
import sys N, D, K = map(int, input().split()) bits = [2 ** i for i in range(16)] st = [0 for i in range(N)] res = 0 def and_calc(a, b): if a & b == b: return 1 return 0 def DFS(L, S, bit): global res if L == K: temp = 0 for i in range(len(st)): temp += and_calc(bit, st[i]) res = max(temp, res) return for i in range(S, D + 1): DFS(L + 1, i + 1, bit + bits[i]) return for i in range(N): # N input_value = list(map(int, sys.stdin.readline().split())) for bit in range(len(input_value)): if bit == 0: continue st[i] += bits[input_value[bit] - 1] DFS(0, 0, 0) print(res) 영상과 유사하게 구현을 했는데도 시간 초과가 나서요.. 어디가 문제인지 잘 모르겠습니다.. 파이썬이라서 그런건지.. 😢
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
안녕하세요 큰돌쌤! 문제를 풀다가 막혀서 질문드립니다! http://boj.kr/54155bff977f43b3a75c1a59fc22430d 저는 ‘dp[현재위치][이동시간] = 모금액’ 이렇게 두고 활용했는데 1퍼 진행되고 틀렸습니다. 어떤 부분이 잘못되었는지 가르쳐주실수 있나요?
미해결
입문자를 위한 코딩테스트 핵심(이론과 문제풀이) [Python]
안녕하세요 강사님. 덕분에 조금씩 강해지는걸 느낍니다. 다 강사님 덕분입니다. 다름이 아니라 문제 정답코드에서 cnt = 1 과 nums.sort() 라인이 바뀌어야 하지않나 의문을 제시해봅니다. 정렬을 해주는 이유가 이미 앞에서 중복검사를 한 값을 뒤에서 또 한번 검사하게 하지 않게하기 위함인데, cnt 를 먼저 1 로 초기화준 다음에 sort() 를 진행하게 되면 nums[0] 이었던 값이 나중에 또 중복검사되는 변수가 생기지 않나요? 해당 문제처럼 개수를 카운트하는 문제는 상관없지만, 만약에 uniq 한 값을 배열을 리턴받아 사용하는 문제가 된다면 문제가 있을 것 같습니다. 혹시 제가 놓치고있는 부분이나 잘못생각하고있는 것일까요? 답변부탁드리겠습니다!! uniq 한 배열을 리턴받아 사용하는 경우로 가정하고 테스트를해보면 아래와 같이 나옵니다. nums.sort() 가 나중에 올 경우 nums.sort() 가 먼저 올 경우
해결됨
코딩테스트 [ ALL IN ONE ]
class Node { let value: String var prev: Node? var next: Node? init(value: String, prev: Node? = nil, next: Node? = nil) { self.value = value self.prev = prev self.next = next } } class BrowserHistory { var head: Node? var current: Node? init(_ homepage: String) { let newNode = Node(value: homepage) self.head = newNode self.current = newNode } func visit(_ url: String) { self.current?.next = Node(value: url, prev: self.current) self.current = self.current?.next } //..생략 } 강의를 듣던중 의문이 생겨서 질문남깁니다. visit시에 참조가 새로운 노드로 변경되기 때문에 그 이전에 current뒤에 존재하는 Node들은 뒤에 몇만개가 있더라도 맨앞에 있던 노드의 참조를 가르키는 곳이 없기 때문에 모두 메모리에서 가비지 컬렉터에 의해 메모리에서 지워진다라고 말씀하셨는데, 뒤에 1개의 Node가 있는 경우는 그렇지만 Doubly Linked List의 경우 그 뒤에 Node들의 prev로 그 이전 Node들을 가르키고 있어 참조하는 곳이 최소 1개 이상은 존재하게 되어 메모리에서 할당해제가 되지 않을 것이라고 생각했습니다. 따라서 visit당시에 뒤에 있는 Node들도 메모리에서 할당해제가 되게끔 리스트의 끝까지 돌면서 Node의 next만 지워주고 테스트해보자고 생각해서 아래와 같이 코드를 수정하였습니다. func visit(_ url: String) { var tmp = self.current while tmp?.next != nil { var before = tmp tmp = tmp?.next before?.next = nil } self.current?.next = Node(value: url, prev: self.current) self.current = self.current?.next } 이를 LeetCode의 결과로 확인해보니 물론 속도는 5ms 줄었지만, 메모리 4MB정도 줄일 수 있었습니다. Swift의 경우 가비지 컬렉터가 아닌 ARC가 컴파일 타임에 Reference Count를 확인하기 때문에 그 동작 방식에서의 차이에서 비롯된 차이인지 궁금합니다. 가비지 컬렉터에서는 실제로 위의 같은 경우에도 메모리 할당 해제가 되는건가요??
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
안녕하세요 선생님, 아래와 같이 http://boj.kr/fb635eced5da4486b8668d07bf1d4370 a[m-i] = 0; <-- 효율성을 위해 이 코드를 넣었는데 틀렸다고 해요 그런데, 위의 코드를 넣지 않고 마지막 ret / 2 를 통해서 잡아주면 맞았다고 하네요.. http://boj.kr/9a9b8fac99914ffdbfe06fcc4d5a8157 그냥 넘어가도 될것 같긴 한데.. 너무 궁금하네요,,, 찾는데 오래걸리고 혹여 바쁘시다면 꼭 봐주시지 않으셔도 괜찮습니다!
해결됨
코딩테스트 [ ALL IN ONE ]
디코를 사정이 있어 나가게 되어 다시 초대받을 수 있는지 궁금합니다.
미해결
파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
안녕하세요 강사님. 문제를 보고 dfs 구현이 더 맞다고 생각하여 다음과 같이 dfs 방식으로 접근해서 해결했는데, bfs 방식으로 푸는 것이 더 옳바른 방향인가요? 복잡도 등의 측면에서 강사님의 풀이가 더 좋을까요? import sys sys.stdin = open('in5.txt','r') def dfs(y,x): global cnt # 현재 섬 방문 표시 후 # 주변에 섬 더 있는지 탐색 arr[y][x] = 0 for i in range(8): nx = x + dx[i] ny = y + dy[i] if 0<=ny<=(N-1) and 0<=nx<=(N-1) and arr[ny][nx] == 1: dfs(ny,nx) if __name__ == '__main__': # 입력정보 저장하기 N = int(input()) # 격자판 크기 arr = [list(map(int,input().split())) for _ in range(N)] # 맵 정보 # 상하좌우대각선 탐색 변수 dx = [0,1,0,-1,-1,1,1,-1] dy = [-1,0,1,0,-1,-1,1,1] cnt = 0 # 섬 갯수 저장 # 맵 전부 탐색 for i in range(N): for j in range(N): # 만약 섬이 발견되면 dfs로 넘겨주기 if arr[i][j] == 1: dfs(i,j) cnt += 1 print(cnt)
해결됨
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. http://boj.kr/b5a0d399c3344237a51a700bfb633b2a 와 같이 작성을 했는데 다양한 예제들을 넣어도 답이 뜨지만 틀린 이유를 잘 모르겠습니다. 편하실때 반례 한번만 부탁드리겠습니다.
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
http://boj.kr/d7d5278a96d845ffb969a50d47df2264 안녕하세요 선생님! 테스트 케이스는 모두 통과했지만 2%에서 시간초과가 발생합니다 어떻게 해야 시간초과를 해결할 수 있을지 도움을 주시면 감사할 것 같아요! 물을 녹이기 전에 백조끼리 서로 만날 수 있는지를 check_swan을 통해 확인하고 만나지 못할 경우에 물을 녹이고 나서 ret을 증가시키고 있습니다 선생님께서 말씀하시는 flood fill은 적용하지 않고 일반적인 bfs 방식을 이용해서 풀었습니다.
해결됨
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. http://boj.kr/f07cde0329cb43428b1b40bb4960eb2f 위와 같이 풀이를 했는데 반례를 도저히 모르겠어서 질문남깁니다.
해결됨
코딩테스트 [ ALL IN ONE ]
먼저 제가 짠 시간초과 난 소스코드는 다음과 같습니다 from collections import deque class Solution(object): def numIslands(self, grid): m = len(grid) # row n = len(grid[0]) # col visited = [] ans = [[False] * n for _ in range(m)] # ans의 용도가 뭐지? cnt = 0 def bfs(x, y): q = deque() # 사전 세팅 q.append((x, y)) visited.append((x,y)) dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] while q: cur_x, cur_y = q.popleft() # (0,0) for i in range(4): next_x = cur_x + dx[i] next_y = cur_y + dy[i] if next_x >= 0 and next_x < m and next_y >= 0 and next_y < n: if grid[next_x][next_y] == "1" and (next_x, next_y) not in visited: q.append((next_x, next_y)) visited.append((next_x, next_y)) ans[next_x][next_y] = True # 완전탐색 for i in range(m): for j in range(n): if grid[i][j] == "1" and (i, j) not in visited: bfs(i, j) cnt += 1 return cnt grid = [ ["1", "1", "0", "0", "0"], ["1", "1", "0", "0", "0"], ["0", "0", "1", "0", "0"], ["0", "0", "0", "1", "1"], ] sol = Solution() print(sol.numIslands(grid)) # O/P: 3 발상은 비슷한 것 같은데, 기억에서는 ans를 저렇게 작성한 것 같아서 위와 같이 초기화를 했지만 ans의 용도를 몰랐고 bfs 템플릿을 참고해서 visited.append()로 방문한 정점을 추가했습니다. 그런데 이렇게하면 테스트케이스 48/49에서 시간초과가 났습니다. 왜 그런지 알 수 있을까요?
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
코드 질문은 아니고 시간 복잡도 관련해서 질문이 있습니다. 처음 문제를 봤을 때, 저도 조합을 떠올려서 이중 for문을 사용하여 문제를 풀어볼까 했었는데, 그러면 코드의 시간 복잡도가 O(n^2)이니까, n = 15000일 경우 연산 횟수가 대략 15,000 * 15,000번 이기 때문에 시간 초과가 날 거라고 생각해서 다른 방법을 계속 생각했는데요... 결국 못 풀어서 문제 해설을 보니 처음 생각했던 그 방법이여서 조금 당황스러웠습니다. O(n^2)정도 시간복잡도를 가진 알고리즘이 떠올랐을 땐, 그냥 시간 초과 신경 안 쓰고 문제 풀이를 이어나가도 되는건가요?
해결됨
2주만에 통과하는 알고리즘 코딩테스트 (2024년)
안녕하십니까 코딩센세 훗날 일본 개발자 취업을 희망하는 코린이 입니다. 저번 시간에도 궁금한 점이 있어서 질문 드렸지만, 오늘도 어김없이 궁금한 점이 생겨서 이렇게 게시판에 글을 작성합니다. 3번 문제는 숙제로 주셨지만, 컨셉만 도출하고 코드는 30분 이상 걸리도록 구현을 못하여 강의록의 솔루션 코드를 이해하고 있는 중입니다. 서론은 이만하고 바로 본론으로 들어가겠습니다. 본론에 해당 부분은 질문의 내용입니다. 솔루션 코드를 해석하는 중에 # 정답 합치기 부분에 질문이 있습니다. 그 부분은 바로 maxPoint[1] - maxPoint[0] + 1 코드가 왜 필요한지 입니다. 아마도 추정컨대 높은 기둥이 넓이를 구해서 더해주는 연산으로 보입니다만, 항상 밑변이 1이라는 문제의 가정이 있었는데도 answer += 1*maxHeight 또는 answer += maxHeight가 오답인 근거를 듣고 싶습니다! 바쁘신 와중에도 답변에 신경써주셔서 감사드립니다.
