본문 바로가기

코테 문제 풀어보기

 (16)
[ 자바 ] - 코테 초심으로.. 코테 공부를 시작한지 3주정도된거같다. 코테 준비하는 글을 찾아보고 아래 쓰신분이 풀어보라는 문제 위주로 풀어보고있엇다. 일단 속도는 신경쓰지지않고 문제푸는 연습부터 하고 있는데 생각보다 쉽지않고 , 응용이 잘되지 않는다.. 완전히 이해하고 푸는거같지도않고 , 한두문제 풀어서 이해할수 있는 개념도 아닌거같아서 , 중간점검겸 다시 앞으로 돌아 가기로했다.. https://covenant.tistory.com/224 코딩테스트 대비를 위한 백준 문제 추천 코딩테스트 대비를 위한 백준 문제 추천 끝 없는 훈련만이 실전에서 흐트럼없이 정답을 향해서 움직일 수 있습니다. (Photo by Specna Arms on Unsplash) 작년 한 해 수많은 코딩테스트를 직접 경험하고 covenant.tistory.co..
[ 자바 ] 경로찾기 & 최단거리 - 2 경로 찾기 & 최단거리 -1 에서 목적지로 도달하지못할 경우와 , 계속해서 q가 쌓여 루프를 도는 문제를 해결하지못하였다. 문제를 해결하지못하여 결국 검색을 통해 찾아보았다 정답을 보면 각 경로를 구할때 무조건 큐에 쌓는것이아니라 특정 조건을 만족할때에만 큐에 쌓도록 하였는데 그 조건은 다익스트라 메소드에 시작점에서 각 정점까지 최소거리일때만 큐에 쌓는 방식을 사용한다. 이렇게되면 큐가 무한정 쌓이지않는다. 그리고 시작점에서 각 정점을 담는 배열을 Integer.MAX_VALUE로 선언한후 진행하기때문에 도착지점까지 가지못할경우 Integer.MAX_VALUE 값이 반환되고 , 이값을 최종도착지 판단 유무에 사용할 수 있다. 정답 코드 package com.myproject.CodeTest; import..
[ 자바 ] 경로찾기 & 최단거리 - 1 백준 1753번과 최단거리를 구하는 prirority queue를 사용하여 예시 문제는 풀었지만 , 제출 한 결과 8%에서 메모리 초과가 발생하였다. https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 내가 풀려고 했던 방식은 시작점부터 모든 경로를 하나씩 탐색하는데 , priority queue를 사용하여 거리가 낮은거 우선으로 꺼내서 탐색하는 방식이다. import java.io.BufferedRea..
[ 자바 ] - 방향 있는 최단거리 정말 많이나오는 문제인가보다 . 처음으로 어떤 회사 코테를 봤는데 최단거리문제가 나왔다. 최단거리 관련 공부를 전혀하지 않은입장에서 당연히 못풀었다. 그때 나온 문제는 시작점에서 목적지까지 갈때 최단거리를 구하는 방법이였는데 dfs방식을적용했더니 ㅋㅋ 최단거리를 못찾앗다. 일단 최단거리 문제 유형이 여러가지인데 , 이 문제는 단방향으로 가는 최단거리이다 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 다른거 참고안하고..
[ 자바 ] - 동전1 , 동전2 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 일단 결과는 둘다 실패이다. 동전1은 시간초가 , 동전2는 틀린답... 반례를 찾는중이다. 동전 1과 동전2의 차이는 동전1은 경우의수를 찾는것이고 , 동전2는 최소한의 값을 찾는부분이다. 동전 1 로직을 힘들게 힘들게 짯는데 ... 재귀함수를 사용하여 완전탐색하는 로직이라 시간이너무올래걸리는듯하다 동전1을 약간 변형하여 동전2에 사용하였다. 코드설명은 받은 동전을 배열에 담고 , 받은동전당 k 까..
[ 자바 ] - dfs , bfs 그래프 문제를 처음 접하게되었다... 어렵드라.. 간단하게 dfs와 bfs 방식을 공부하고 , 기본 형태의 코드를 보면서 어떻게 동작하는지 봤다. https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 그리고 실제로 첫번째 문제를 풀어보았다. https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ ..
[ 자바 ] - 사탕게임, 빗물 특별한 알고리즘이 들어갔다기 보다는 문제를 잘 이해하고 코드로 잘 구현하면 되는 문제였다. 일단 문제도 이해하기 힘들었고, 설마 그많은 경우를 다 검사해봐야 하는 생각에 자꾸 다른방법을 찾다가. 그냥 경우에수를 모두 찾아보자고 생각을 바꿔 진행하였다. 문제의 요점은 가로 세로 바둑판에 바로옆이나 아래 글자가 다른 글자이면 서로 위치를 교환하고 그때 반복해서 문자가 많이 오는 횟수를 찾으라는것이다. EX) AAB BBC CCD [0,0] 은 [0,1]과는 바꾸지못하고 , [1,0]과는 교환할수있다. 교환 했을때 AAA,BBB,CCC와같이 연속한 문자가 가장 많이 올때 몇번 오는가 이다. 결국 [1,2]와 [2,2]를 교환했을떄 [2,0][2,1][2,2] 가 CCC임으로 여기서 가장 높은 점수는 3점이된다..
[ 스택 ] - 괄호의값 2504 번 문제는 스택을 활용하는 문제라고해서 풀어보았다. 처음에 스택을 안쓰고 정규식을 써서 하다가 실패... 코딩하면서 스택을 구현해본적이있나 싶을정도로 사용해보지않은 자료구조였다. 기본적으로 컴퓨터관련 시험을 봐보셨으면 들어봤을만한 LIFO 개념이 나온다 쉽게말하면 컨테이너에 짐을쌓는데 안에서부터 차곡차곡쌓다보니 꺼낼때는 겉에꺼 부터 꺼낸다는 개념이다 규칙은 아래에 써어놯고 아래 써놓은대로 구현하였다. 하지만 놓친부분이 )) 이나 ((]) 이런 문자가들어왔을때 상황을 처리해놓지 않아서 (EmptyStack) 과 43%에서 계속 틀렸다. 급하게 풀어보느라 로직이 깔끔하지못하지만 좀더 간단하게 다시 풀어보기싶다. 이문제가 너무 어렵다면 9012 를 먼저 풀어보는것도 나쁘지않다 https://www.a..

티스토리툴바